思想:
从后往前找比基准小的数字,找到往前挪
从前往后找比基准大的数字,找到往后挪
思路演绎:
原始数据:9 3 12 6 7 10 5 8 21 4
temp:=9; //temp为基准,存放第一个数据
3 12 6 7 10 5 8 21 4
low high
第一趟:9>3,从后面High位置开始找比9小的数字,放在low位置
4 3 12 6 7 10 5 8 21
low high
high位置空出来,因此从前往后找比9大的数字放在High位置,low++
4 3 6 7 10 5 8 21 12
low high
low位置空出来,从High位置开始查找比9小的数字,high--
4 3 8 6 7 10 5 21
low high
high位置空出来,因此从前往后找比9大的数字放在High位置,low++
4 3 8 6 7 5 10 21
low high
low位置空出来,因此从后往前找比9小的数字放在low位置,high--
4 3 8 6 7 5 10 21
low high
此时,high=low,将temp的值放入该位置
4 3 8 6 7 5 9 10 21
上述为快速排序的一次划分,此时基准temp(9)抵达它应在位置。
为达到数据完整排序的目的,需在一次划分的基础上,返回此时low的位置,然后进行左右分别递归调用,从而实现排序。
空间复杂度:O(logn) //即递归的次数,每次都是/2。不是O(1)
时间复杂度:O(nlog2n) //一次划分是O(n),递归调用是O(nlog2n),可参照下面代码辅助理解
完全有序时,时间复杂度O(n^2) //举例为从小到大的数据,每个数据均需从后往前遍历一遍找比它小的数据,最后都是在low==high位置停止遍历。也可以从递归角度理解,每次切割数据时都不是/2,而是约等于切割1:n。
稳定性:不稳定
特点:越有序越慢,越无序越快
缺点:越有序越慢,空间复杂度大,不稳定。之所以叫快速排序,是从平均性能而言,快排最佳。
当数据趋于基本有序时,快速排序会退化为选择排序。
代码:
-
- //一次划分
- int Partition(int* arr, int low, int high)//int返回下标
- {
- int temp = arr[low];
- while (low < high)
- {
- //从后往前找比基准temp小的数字
- while (low
temp) - {
- high--;
- }
- //找到比基准temp小的数字后,将赋值到low位置
- if (low < high)
- {
- arr[low] = arr[high];
- }
- //从前往后找比基准temp大的数字
- while (low < high && arr[low] <= temp)
- {
- low++;
- }
- //找到比基准temp大的数字后,将赋值到High位置
- if (low < high)
- {
- arr[high] = arr[low];
- }
- }
- arr[low] = temp;
- return low;
- }
- //快速排序,递归实现
- void Quick(int* arr, int low, int high)
- {
- int par= Partition(arr, low, high);//par=一次归并后low的位置
- if (low < par - 1)//左边数据超过一个
- {
- Quick(arr, low, par - 1);//左递归
- }
- if (par + 1 < high)//处理右边
- {
- Quick(arr, par + 1,high);//右递归
- }
- }
- //因为该函数参数的问题,无法直接递归调用,因此增加Quick函数
- void QuickSort(int* arr, int len)
- {
- Quick(arr, 0, len - 1);
- }
-
- void Show(int* arr,int len)
- {
- for (int i = 0; i < len; i++)
- {
- printf("%d ", arr[i]);
- }
- }
- int main()
- {
- int arr[] = { 6,4 ,7,8,10,-5,90,34,55};
- Show(arr,sizeof(arr) / sizeof(arr[0]));
- printf("\n ");
- QuickSort(arr, sizeof(arr) / sizeof(arr[0]));
- Show(arr, sizeof(arr) / sizeof(arr[0]));
- }
-
运行结果: