C++快速排序超详细讲解-牛翰网

一、快速排序原理

快速排序（QuickSort）是一种基于分治法的高效排序算法。它的基本思想是通过一个称为“基准”（pivot）的元素将数组划分为两部分，一部分的所有元素都比基准小，另一部分所有元素都比基准大，然后递归地对这两部分进行同样的操作，直到整个数组有序。

二、快速排序标准代码

void quick_sort(int q[], int l, int r)
{
	if (l >= r) return; //递归停止条件
	int i = l - 1, j = r + 1, x = q[l + r >> 1]; //设定指针,基准
	while (i < j)
	{
		do i++; while (q[i] < x); //q[i]大于等于基准时,指针i停止
		do j--; while (q[j] > x); //q[j]小于等于基准时,指针j停止
		if (i < j) swap(q[i], q[j]); //判断是否i<j,交换i,j对应的数组元素
	} // 结束时数组被分为 >=x,<=x 的两部分
	quick_sort(q, l, j); //继续分直到分到一到两个元素此时数组有序
	quick_sort(q, j + 1, r);
}

三、代码解析

我们以一个简单的例子帮助我们了解快速排序

1.排序的数组以及需要排序元素的范围，无返回值

void quick_sort(int q[], int l, int r)

2.递归结束的条件：元素剩一个或空

if (l >= r) return;

3.设定变量，其中 i, j 为两个指针分别减 1 加 1 是为了下一步的 do while 循环，x 即为“基准”（pivot) 用来将列表分为 <=x 和 >=x 的两部分，x 是随机的，这里取了数组中间的一个元素，l + r >> 1相当于 (l + r)/2 (pivot:q[2] = 4)向下取整(提高了效率)

int i = l - 1, j = r + 1, x = q[l + r >> 1];

	5	3	4	1	2
i $\rightarrow$	0	1	2	3	4	$\leftarrow$ j

4.while循环实现了遍历、比较、交换的功能，先使 i 指针递增直到 i 所对应的元素 >=x 停止,接下来使 j 指针递减直到其对应的元素 <=x 停止

while (i < j)
{
	do i++; while (q[i] < x);
	do j--; while (q[j] > x);
	if (i < j) swap(q[i], q[j]);
}

5	3	4	1	2
i(>=4停止)				j(<=4停止)

交换之后开启下一次循环

2	3	4	1	5
<4	<4	i(>=4停止)	j(<=4停止)	>4

满足 i<j 交换

2	3	1	4	5
<4	<4	j(<=4停止)	i(>=4停止)	>4

不满足 i<j 不交换,此时整个 while 循环结束,注意此时 j(包含)往左为 <=4 部分,j + 1 及其往右为 >=4部分

5.接下来就是递归了,每次运行分将数组为左<=右的两部分,我们只需将左右两部分分别执行函数程序得到直到剩两个或一个元素,此时数组便有序了

quick_sort(q, 0, 2);

2	3	1	4	5
<4	<4	j(<=4停止)	i(>=4停止)	>4

x(pivot)=3

2	3	1
<3	i(>=3停止)	j(<=3停止)

2	1	3
<3	j(<=3停止)	i(>=3停止)

quick_sort(q, 0, 1);

x(pivot)=2

2	1
i(>=2停止)	j(<=2停止)

1	2
j(<=2停止)	i(>=2停止)

剩一个元素时,执行递归停止程序:

if (l >= r) return;

数组中最初的“左”部分就变为

而最初的“右”部分:x(pivot)=4

4	5
i(>=4停止)j(<=4停止)	>5

if (i < j) swap(q[i], q[j]);

不满足 if 条件以及 while 条件,while 循环停止,依旧选择了 j 为分界点分到一个元素时结束递归

此时代码全部有序

quick_sort(q, l, j); 
quick_sort(q, j + 1, r);

6.总结

快速排序利用两个指针对数组的元素进行比较交换进行部分排序，再利用递归整体排序

四、使用while循环的快速排序

1.代码

代码1.由快排代码等价转化而来

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l, j = r, x = q[l + r >> 1];
    while (i < j)
    {
        while (q[i] < x) i++;
        while (q[j] > x) j--;
        if (i < j)
        {
            swap(q[i], q[j]);
            if (i + 1 < j - 1)
            {
                i++;
                j--;
            }
            else
            {
                i++;
                j--;
                while (q[i] < x) i++;
                while (q[j] > x) j--;
                break;
            }
        }
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

代码2.效率提高版

void quick_sort(int q[], int l, int r) {
	if (l >= r) return;
	int x = q[l + r >> 1];
	int i = l, j = r;
	while (i <= j) { // 注意：这里应该是 i <= j 而不是 i < j
		while (q[i] < x) i++;
		while (q[j] > x) j--;
		if (i <= j) {
			swap(q[i], q[j]);
			i++;
			j--;
		}
	}
	quick_sort(q, l, j);   
	quick_sort(q, i, r);   
}

2.代码2解析

1.因为没有 do 过程,所以指针起始位置直接设在了 0 和 -1 的位置,

if (l >= r) return;
int x = q[l + r >> 1];
int i = l, j = r;

5	3	4	1	2
i $\rightarrow$				$\leftarrow$ j

2. while 循环中的 while 循环先判断是否满足条件,满足的话指针加/减 1,这样停止时依旧是对应元素 >=x 或 <=x 时的指针,

while (i <= j) 
{ 
	while (q[i] < x) i++;
	while (q[j] > x) j--;
	if (i <= j)
    {
		swap(q[i], q[j]);
		i++;
		j--;
	}
}

5	3	4	1	2
i(停)				j(停)

换过之后+=或–

2	3	4	1	5
	<4	i(停)	j(停)

交换，++/–

2	3	1	4	5
		j	i

不满足 i<=j while 循环结束.

关于 i<=j 的条件判断,我们给出新的案例

3	2	1
i(停)		j(停)

交换之后 ++/–

1	2	3
	i(停) j(停)

注意此时并没有返回(return),

递归代码:分别以 j 和 i 作为分界点

quick_sort(q, l, j);   
quick_sort(q, i, r);

而如果条件判断为 < 的话 i=j 时就会造成下一次递归多了一个元素,

而标准代码的运行过程到此处后结束,以 j 和 j+1 为分界点不会造成此问题.

因此再进行一次循环

1	2	3
j		i

而此时元素 2 的位置是 i,j同时停过的位置即为基准 x,而i,j也会再下一次++/–后停止,所以我们可以直接将元素 2 所对应的数组位置固定不动,将元素 2 左右的数组递归处理.

quick_sort(q, l, j);   
quick_sort(q, i, r);

五、总结

使用 while 循环会比 do while 多一层内层循环,所以 do while 循环效率更高,建议只用 do while 循环.

到此这篇关于C++快速排序的文章就介绍到这了,更多相关C++快速排序内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！

来源链接：https://www.jb51.net/program/337774ahj.htm

本站所有资源来自于网络，仅供学习与参考，请勿用于商业用途，否则产生的一切后果将由您(转载者)自己承担！
如有侵犯您的版权，请及时联系3500663466#qq.com(#换@)，我们将第一时间删除本站数据。

THE END

智能工控智能开发硬件开发
# C++# 排序 # 快速

目录