挖坑法之--快速排序

特点

速度快，耗时小，面对数据量大的题目时可用快排

思路

选取基准数，不断“挖坑、填坑”
使小于基准数的数全在其左边，大于其的数全在右边
最后数组有序

参考链接

具体实现

1. 选择最左端的数为基准数x
   可将其视为一个坑，可以将别的数填入这个坑
2. 从右往左寻找小于x的数y，找到后填入坑，此时原基准数的坑被填，而y处产生新的一个坑，然后从左往右寻找大于基准数x的数，填入y的坑
3. 重复上述步骤2，直到上下界下标重合，将基准数填入重合处
4. 此时，x左端全部小于x，右端全部大于x，对左右两块区域分别重复123，最后数组全部有序

#include<iostream>
using namespace std;
void quick_sort(int *a, int inx_min, int inx_max) {
	if (inx_min < inx_max) {
		int min = inx_min, max = inx_max;//min、max为搜索用的变动的下标上标

		int x = a[min];//x为比较基准

		while (min < max) {
			while (min < max && a[max] >= x) //从右往左搜索第一个小于x的数
				max--;

			if (min < max)//当max标小于min时证明右边数全部大于基准数
				a[min++] = a[max];//将大的数填入坑，然后min++

			while (min < max && a[min] < x)
				min++;
			if (min < max)
				a[max--] = a[min];
		}
		a[min] = x;//最后退出循环时min==max，将x填入最后的坑
		//此时a[min]左边全小于a[min]，右边全大于a[min]

		//递归调用，将两边区域继续排序，直到区域只有一个数
		quick_sort(a, inx_min, min - 1);
		quick_sort(a, min + 1, inx_max);
	}
}
int main() {
	int n;
	int *a=new int[100001];
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	quick_sort(a, 0, n - 1);
	for (int i = 0; i < n; i++)
		if (i == n - 1)cout << a[i];
		else
			cout << a[i] << " ";
	delete a;
}

最后

以上就是合适萝莉为你收集整理的挖坑法之--快速排序的全部内容，希望文章能够帮你解决挖坑法之--快速排序所遇到的程序开发问题。

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