快速排序（Quick Sort）—挖坑填数法

前面的博文讲了冒泡排序、选择排序、插入排序，今天我们谈谈快速排序！
快速排序的基本思想是：
1．先从序列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。（分区的方式多样，但一定要保证基准数左边的数比它大（小），右边的数比它小（大））
3．再对左右区间重复第一步、第二步，直到各区间只有一个数。

快速排序的关键点（一定要理解）：
1、 如何确定基准数？
一般情况下，选取当前数组的第一个数。
2、如何找到比基准数大（小）的数？（假设从小到大排序）
先从后往前找比基准数小的数；再从前往后找比基准数大的数；（注意次序不能颠倒）
3、找到的数如何放，才能实现比基准数大和小的数分别在基准数的两边？
采用挖坑填数法，具体过程如下：
①每次把基准数所在的位置看成一个坑位A，定义两个变量：left和right分别指向数组的左端和右端。
②从后往前扫描数组，当发现有值小于基准值时，将当前值填到坑位A中，同时当前值所在的位置看成新的坑位B；
③从前往后扫描数组，当发现有值大于基准值，将当前值填到坑位B中，同时当前值所在的位置看成坑位A；
不停的重复第②~③步的操作，直到left>=right相遇，表示这一轮的内循环比较结束，
将基准值填到left（right）指向的坑位中，就完成了本轮的排序；
4、以基准值为分割点，将当前的数组为两个小的数组，依次从第1步递归循环操作；

为了便于学者深入理解，举例：[14, 18, 11, 30, 28,4 ]进行从小到大的排序

整个过程中涉及三个参数：当前基准数num，left，right; （left,right分别代表当前数组的左右端位置）
第1轮：基准数num=14

①交换前的数据：[14, 18, 11, 30, 28,4 ] 当前坑位[0]，left=0，right=5
②从right=5的位置开始从后往前，找到比14小的第一个数4，此时的left=0，right=5，满足left<right，把4填到当前的坑位[0]；
交换后的数据：[4, 18, 11, 30, 28,4] 当前坑位[5] （4原来的下标位置）
③从left=0的位置开始从前往后，找到比14大的第一个数18，此时的left=1，right=5，满足left<right，把18填到当前的坑位[5]，
交换后的数据：[4, 18, 11, 30, 28,18]当前坑位[1]（18原来的下标位置），
④从right=5的位置开始从后往前，找到比14小的第一个数11，此时的left=1，right=2，满足left<right，把11填到当前的坑位[1]
交换后的数据：[4,11,11,30,28,18]当前坑位[2]（11原来的下标位置）
⑤从left=1的位置开始从前往后，找到比14大的第一个数30，此时的left=3，right=2,
由于left>right，内循环结束，将基准值14放在最后一个坑位[2]的位置。
交换后的数据：[4,11,14,30,28,18]

第1轮结束。（14左边的数都比14小，14右边的数都比14大）

以基准数14为分割点，用{ }划分。表示如下：[{4,11},14,{30,28,18}]，

（一）先对14左边的子数组{4,11}进行递归快速排序：
第2轮：基准数num=4（14左边的子数组{4,11}）

①交换前的数据：[{4,11},14,{30,28,18}]当前坑位[0], left=0，right=1（因为当前数组为{4,11}）；
②从right=1的位置从后往前，直到right=0也没有找到比4小的数，此时的left=0,right=0，由于left等于right，内循环结束，将基准值4放在最后一个坑位[0]的位置。
③交换后的数据为：[4,11,14,18,28,30]

第2轮结束。（4左边的数都比4小，4右边的数都比4大）

以基准数4为分割点，用{ }划分。表示如下：[4,{11},14,30,28,18]，

第3轮：基准数num=11（4右边的子数组{11}）

①交换前的数据：[4,{11},14,30,28,18]当前坑位[1], left=1，right=1（因为当前数组为{11}）；
由于left等于right，内循环结束，将基准值11放在最后一个坑位[1]的位置。
③交换后的数据为：[4,11,14,18,28,30]
第

第3轮结束。（11左边的数都比11小，11右边的数都比11大）

（二）先对14右边的子数组{30,28,18}进行递归快速排序：
第4轮，基准值num=30（14右边的子数组{30,28,18}）

①交换前的数据：[4,11,14,{30,28,18}] 当前坑位[3]，left=3，right=5（因为当前数组为{30,28,18}）
②从right=5的位置开始从后往前，找到比30小的第一个数18，此时的left=3，right=5，满足left<right，把18填到当前的坑位[3]；
交换后的数据：[4,11,14,{18,28,18}] 当前坑位[5] （18原来的下标位置）
③从left=3的位置开始从前往后，直到left=5也没有找到比30大的数，此时的left=5，right=5，
由于left等于right，内循环结束，将基准值30放在最后一个坑位[5]的位置。
交换后的数据：[4,11,14,18,28,30]

第4轮结束。

以基准数30为分割点，用{ }划分。表示如下：[4,11,14,{18,28},30]

第5轮：基准值num=18（30左边的子数组{18,28}）

①交换前的数据：[4,11,14,{18,28},30]当前坑位[3], left=3，right=4（因为当前数组为{18,28}）
②从right=4的位置开始从后往前，直到right=3都没有找到比18小的数，此时的left=3，right=3，由于left等于right，内循环结束，将基准值18放在最后一个坑位[3]的位置。

第5轮结束

以基准数18为分割点，用{ }划分。表示如下：[4,11,14,18,{28},30]

第6轮：基准值num=28（18右边的子数组{28}）
①交换前的数据：[4,11,14,18,{28},30]当前坑位[4], left=4，right=4，由于left等于right，内循环结束, 将基准值28放在最后一个坑位[4]的位置。
②交换后的数据为：[4,11,14,18,28,30]

第6轮结束

排序后最终的数组为：[4,11,14,18,28,30]

对挖坑填数进行如下总结：三个参数基准数，left（i），right（j）（假设有n个数）
1．i =left; j = right; 将基准数挖出形成第一个坑a[i]。
2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

整个快速排序的时间复杂度仍然是O（n的平方）；
快速排序是一种不稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

为了便于道友们向我咨询问题，特意开设了一个免费的知识星球——CaptianXue，星球提供学习、理财、生活、职场等各类文章和免费答疑！！

完整的代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
void quickSort(int s[], int left, int right) {
	if (left< right) { //只有当left<right的时候才执行快速排序
		int i = left, j = right, x = s[left];//初始值 
		while (i < j) {//只要i<j就一直循环从后往前找，从前往后找； 
			while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
				j--;
			if(i < j)
				s[i++] = s[j];//进行填数 
			while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
				i++;
			if(i < j)
				s[j--] = s[i];//进行填数 
		}
		s[i] = x; //把基准数填入 
		quickSort(s, left, i - 1); //当前基准数左边的子数组递归调用
		quickSort(s, i + 1, right);//当前基准数右边的子数组递归调用
	}
}
int main() {
	int s[]= {14,18,11,30,28,4 };
	printf("原来的数组为:n");
	for(int i=0; i<6; i++)
		printf("%d ",s[i]);
	printf("n");
	quickSort(s,0,5);//调用快速排序的函数，参数为数组名，数组的左端点，数组的右端点
	printf("排序后的数组（从小到大）为:n");
	for(int i=0; i<6; i++)
		printf("%d ",s[i]);
	printf("n");
	return 0;
}

当然，还有一种快速排序，选取当前数组中首，尾，中三个数的中位数，即大小居中的数为基准数。其他的操作过程不变！学者可以自我实现。

更多的排序算法：
sort函数排序 https://blog.csdn.net/weixin_43956598/article/details/90241551
冒泡排序 https://blog.csdn.net/weixin_43956598/article/details/90176251
选择排序 https://blog.csdn.net/weixin_43956598/article/details/90178197
插入排序 https://blog.csdn.net/weixin_43956598/article/details/90181567
快速排序 https://blog.csdn.net/weixin_43956598/article/details/90215135
希尔排序 https://blog.csdn.net/weixin_43956598/articledetails/90234480
堆排序 https://blog.csdn.net/weixin_43956598/article/details/90343547

最后

以上就是聪明荷花为你收集整理的快速排序（Quick Sort）—挖坑填数法的全部内容，希望文章能够帮你解决快速排序（Quick Sort）—挖坑填数法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。