深圳幻海软件技术有限公司 欢迎您！
更多

八大排序算法之快速排序(上篇)(未经优化的快排)

2023-03-25

key 数组 left
目录一.关于快速排序的总体算法思想1.冒泡排序(交换排序)(以排升序为例)2.快速排序的总体思想简介(以排升序为例) 二.快速排序单趟排序的算法接口设计(以排升序为例)单趟排序实现的方法一:hoare版本(左右指针法)代码实现: 单趟排序实现的方法二:挖坑法 代码实现:

目录

一.关于快速排序的总体算法思想

1.冒泡排序(交换排序) (以排升序为例)

2.快速排序的总体思想简介(以排升序为例) 

二.快速排序单趟排序的算法接口设计(以排升序为例)

单趟排序实现的方法一:hoare版本(左右指针法)

代码实现: 

单趟排序实现的方法二:挖坑法

 代码实现:

单趟排序实现的方法三:快慢指针法

代码实现:

三. 快速排序的实现(待进一步优化的版本)(排升序)

递归函数实现:

快排时空复杂度分析(所处理的数组为逆序数极大的乱序数组的情形)

快排效率实测:

四.未经进一步优化的快速排序的缺陷

一.关于快速排序的总体算法思想

🤓我们先总览一下快速排序的思想,再去了解其中的细节:

  • 快速排序是基于对交换排序(冒泡排序)的优化而产生的高效排序算法
  • 其基本思想是利用分治递归算法将交换排序的时间复杂度(O(N^2))降阶为O(NlogN)

1.冒泡排序(交换排序) (以排升序为例)

🤓冒泡排序的算法思想:

  • N个元素的数组则进行N-1趟排序
  • 每一趟排序将数组中的一个元素交换到其最终应该出现的位置(比如将第n大的数交换到数组下标为N-n的位置)
  • 算法图解：

🤓代码实现: 

  1. void swap(int* e1, int* e2)
  2. {
  3. assert(e1 && e2);
  4. int tem = *e1;
  5. *e1 = *e2;
  6. *e2 = tem;
  7. }
  8.  
  9.  
  10. void BubbleSort(int* arr, int size)
  11. {
  12. assert(arr);
  13. int turns = 0;//记录排序的趟数
  14. int flag = 0;//flag用于标记数组是否已经有序
  15. while (turns < size - 1)                    //n个元素要完成n-1趟冒泡排序(将n-1个较大元素依次置于数组后缀)
  16. {
  17. flag = 1;
  18. for (int i = 0; i < size - turns - 1; ++i)//内层循环可以完成一个元素的排序(将最大元素交换到数组size-turns-1的位置)
  19. {
  20. if (arr[i] > arr[i + 1])
  21. {
  22. swap(&arr[i], &arr[i + 1]);       //将较大的元素向后交换
  23. flag = 0;
  24. }
  25. }
  26. if (flag)  //flag为1说明数组已经有序
  27. {                        
  28. break;                                //数组已经有序则可以结束循环
  29. }
  30. ++turns; //继续下一趟排序
  31. }
  32. }

  • 冒泡排序算法的复杂度计算公式(最坏情况下)是一个等差数列求和式,因此其时间复杂度为O(N^2)(这里只考虑最坏的情形)
  • 冒泡排序的单趟排序: 
    1. for (int i = 0; i < size - turns - 1; ++i)//内层循环可以完成一个元素的排序(将最大元素交换到数组size-turns-1的位置)
    2. {
    3. if (arr[i] > arr[i + 1])
    4. {
    5. swap(&arr[i], &arr[i + 1]);       //将较大的元素向后交换
    6. flag = 0;                         //标记出数组无序
    7. }
    8. }

    冒泡排序的单趟排序会把前(size-turns)个元素中的最大值交换到(size-turns-1)的位置(增加数组的有序后缀长度)

  • 冒泡排序单趟排序关注的是数组无序前(后)缀中的最值,这一点限制了算法优化的思路

  • 1962年Hoare大神运用双指针算法重新设计了交换排序的单趟排序,并运用分治递归实现代替了嵌套循环实现,完成了交换排序的终极优化🧐🧐

2.快速排序的总体思想简介(以排升序为例) 

  1. 🤓利用双指针算法来设计单趟排序过程以达到以下目的:在数组中选取一个key元素,将比key小的元素交换到key元素的左边,将比key大的元素交换到key元素的右边
  2. 🤓由于key元素左边的子数组每个元素的值都比key元素小,key元素右边的子数组每个元素的值都比key元素大,因此经过单趟排序后,key元素就被交换到了其在有序序列中最终应该出现的位置),同时,左右子数组我们可以分开完成排序(这一点非常关键).图示:😉(算法的具体实现后面再深究)😉
  3. 🤓根据单趟排序过程确定的key元素的最终位置(比如上图中的数组下标为5的位置)为分割点,将数组分为左右子数组(子数组中不包含key元素):
  4. 🤓在子数组中我们分别再进行单趟排序,并以key元素最终位置作为分割点继续分割子数组,于是便形成了递归,递归的过程中数组被逐步拆分的图示:(每一个子数组中都要进行一次单趟排序以确定数组的划分点)(当子数组元素个数为1时划分结束)(这里我们假设每次分割数组时分割点都在数组的中间位置)
  • 🤓假设数组中有N个元素,每一个子数组进行单趟排序的过程中,我们都要遍历一次子数组,根据上图可知,每一个递归层次我们都需要遍历N个元素,而递归层次的数量级为logN,因此相比于冒泡排序,快排的时间复杂度便降阶为O(NlogN).
  • 🤓可见分治思想有时可以将复杂度为N*N的遍历算法降阶为复杂度为N*logN的遍历算法,其原因在于,数组被划分后,左右子数组互不相关,在左右子数组中分别进行单趟操作,需要遍历的元素个数就变少了(无须每次单趟操作都遍历原数组的所有元素)
  • 🤓分治优化的思想在许多其他算法设计中也是十分常见的。

二.快速排序单趟排序的算法接口设计(以排升序为例)

快速排序的单趟排序要达到的目的:

1.将数组中某个元素(key元素)交换到其在有序序列中最终应该出现的位置,即:

  • 单趟排序结束后要保证key元素之前的元素都比key元素小
  • 单趟排序结束后要保证key元素之后的元素都比key元素大

2.单趟排序接口返回key元素最后的位置下标(作为数组分割点)

单趟排序实现的方法一:hoare版本(左右指针法)

  • hoare大神是快速排序发明者🤓🤓🤓🤓
  • 算法接口首部: 
    int PartionV1(int* arr, int left, int right)//完成1个元素的排序,同时返回数组分割点
  • left和right是待处理的子数组的下标区间(我们取开区间,即left指向子数组第一个元素,right指向子数组最后一个元素)
  • 下文所谓的指针都指代数组下标

单趟排序算法实现思想:

  1. 选取arr[left]作为key元素(key变量作为下标指向key元素)
  2. right指针向前遍历寻找比key小的数,找到后停下
  3. left指针向后遍历寻找比key大的数,找到后停下
  4. 交换left和right指向的元素,重复上述迭代过程,直到left指针和right指针相遇
  • left指针和right指针相遇后,将key元素交换到两指针相遇位置(此时保证了两指针相遇的位置之前的元素都比key小,相遇位置之后的元素都比key大)
  • 算法流程中相当于用left下标来维护由比key小的元素构成的数组前缀,用right下标来维护由比key大的元素构成的数组后缀
  • 算法gif:

代码实现: 

  1. //hoare版本的左右指针法
  2. //取数组首元素作为key则必须让右指针先找比key小的变量
  3. //取数组尾元素作为key则必须让左指针先找比key大的变量
  4.  
  5. //left下标用来维护由比key小的元素构成的数组前缀
  6. //right下标用来维护由比key大的元素构成的数组后缀
  7. //以key最终位置为分割点将数组分为两个子数组,前半部分(前缀)数组中每个元素都比key小,后半部分(后缀)数组中每个元素都比key大
  8. int PartionV1(int* arr, int left, int right)   //完成1个元素的排序,同时分割数组
  9. {
  10. assert(arr);
  11. int key = left;   //取子数组首元素(下标为left)作为key
  12. while (right > left)
  13. {
  14. while (right > left && arr[right] >= arr[key]) //right下标寻找比key小的值
  15. {
  16. --right;
  17. }
  18. while (right > left && arr[left] <= arr[key])  //left下标寻找比key大的值
  19. {
  20. ++left;
  21. }
  22. swap(&arr[left], &arr[right]);//交换left和right所指向的元素(将比key小的元素置于数组前半部分,将比key大的元素置于数组的后半部分)
  23. }
  24. swap(&arr[key], &arr[left]);   //right和left相遇后,交换key和left(指向的元素)完成单趟排序
  25. return left;                                       //返回数组分割点下标
  26. }
  • 注意算法的一些细节:
  1. 内层循环一定要加上right>left的条件防止两指针错位
  2. 选择arr[left]作为key元素一定要先让right指针向前找比key小的值,不然会出现以下情况:

单趟排序实现的方法二:挖坑法

  • 算法接口首部： 
    int PartionV2(int* arr, int left, int right)//完成1个元素的排序,同时分割数组

  • left和right是待处理的子数组的下标区间(我们取开区间,即left指向子数组第一个元素,right指向子数组最后一个元素)

单趟排序算法实现思想:

  1. 选择arr[left]作为key元素(key变量存储key元素的值)
  2. 以left指向的位置作为初始坑位(坑位下标用hole变量来记录)
  3. right指针向前遍历寻找比key小的数,找到后将right指向的元素交换到坑位上,将right下标值赋给hole(更新坑位)
  4. left指针向后遍历寻找比key大的数,找到后将left指向的元素交换到坑位上,将left下标值赋给hole(更新坑位)
  5. 重复上述迭代过程直到left指针和right指针相遇
  • left指针和right指针相遇后,将key元素放到相遇位置处完成单趟排序(此时保证了两指针相遇的位置之前的元素都比key小,相遇位置之后的元素都比key大)
  • 同样地,算法流程中相当于用left下标来维护由比key小的元素构成的数组前缀,用right下标来维护由比key大的元素构成的数组后缀
  • 算法gif:

 代码实现:

  1. int PartionV2(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
  2. {
  3. assert(arr);
  4. int key = arr[left];                    //取数组左端元素为key
  5. int hole = left;//取数组左端位置为初始坑位
  6. while (right > left)
  7. {
  8. while (right > left && arr[right] >= key)  //right下标寻找比key小的值
  9. {
  10. --right;
  11. }
  12. swap(&arr[hole], &arr[right]);             //将right位置的变量放到hole位置上
  13. hole = right;   //更新坑位
  14. while (right > left && arr[left] <= key)   //left下标寻找比key大的值
  15. {
  16. ++left;
  17. }
  18. swap(&arr[hole], &arr[left]);   //将right位置的变量放到hole位置上
  19. hole = left;   //更新坑位
  20. }
  21. arr[left] = key; //right和left相遇后,将key放到相遇位置                
  22. return left;     //返回数组分割点
  23. }
  • 理解了该种算法后,可以将hole变量省略掉
  • 选择arr[left]作为key元素同样一定要先让right指针向前找比key小的值

单趟排序实现的方法三:快慢指针法

  • 算法接口首部： 
    int PartionV3(int* arr, int left, int right)//完成1个元素的排序,同时分割数组

  • left和right是待处理的子数组的下标区间(我们取开区间,即left指向子数组第一个元素,right指向子数组最后一个元素)

单趟排序算法实现思想:

  1. 选取arr[left]作为key元素(key变量作为下标指向key元素)
  2. slow初值为left,fast指针从left+1位置开始遍历数组
  3. 若fast指针找到了比key小的元素,则令slow指针向后走一步,并交换slow和fast指针指向的元素
  4. 若fast指针找到了比key大的元素,slow指针不动,fast指针继续向后遍历数组
  • 重复上述迭代过程直到fast指针完成数组的遍历,最后再将key元素交换到slow最终指向的位置上即可
  • 最终从left位置到slow位置的所有元素就是整个数组中比key小的所有元素.
  • 算法gif:

代码实现:

  1. int PartionV3(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
  2. {
  3. assert(arr);
  4. int key = left;//取子数组最左边元素为key
  5. int slow = left;//slow从left开始  
  6. int fast = left + 1;//fast从left+1开始遍历数组
  7. while (fast <= right)
  8. {
  9. if (arr[fast] < arr[key])//fast找到比key小的值
  10. {
  11. ++slow;   //slow指向下一个位置
  12. if (slow != fast)//fast和slow相等没必要交换
  13. {
  14. swap(&arr[slow], &arr[fast]);//交换slow和fast所指向的值
  15. }
  16. }
  17. ++fast; //fast遍历数组
  18. }
  19. swap(&arr[key], &arr[slow]);         //最后交换key和slow所指向的变量
  20. return slow;   //返回数组分割点下标
  21. }
  • 出于对代码简洁性的考虑,后续我们采用快慢指针法实现的单趟排序

三. 快速排序的实现(待进一步优化的版本)(排升序)

  • 每经过一次单趟排序,就可以将数组中选定的key元素交换到其在有序序列中最终应该出现的位置(同时该位置前的所有元素都比key小,该位置后的所有元素都比key大)比如:
  • 因此最终key元素所在的位置就可以将数组分割为两个不包含key元素的子数组(两个子数组在后续的排序过程中互不关联),对于左右两个子数组我们又可以以相同的方式继续分割,形成分治递归,直到数组被分割为多个(原数组元素个数为N)只有单个元素构成的子数组,排序就完成了(此时所有元素都被交换到了其在有序序列中最终应该出现的位置)
  • 快排递归函数首部 : 
    void QuickSort(int* arr, int left,int right)

    调用时传入待排序的数组区间[left,right];

  • 递归函数实现:

    1. int PartionV3(int* arr, int left, int right);
    2. void QuickSort(int* arr, int left,int right)
    3. {
    4. assert(arr);
    5. if (left >= right)     //子数组只剩一个元素时(或left和right错开时)停止递归
    6. {
    7. return;
    8. }
    9. int breakpoint = PartionV3(arr, left, right);//找到数组分割点(同时也完成了一个元素的排序)
    10. //左右子数组分治递归
    11. QuickSort(arr, left, breakpoint - 1);     //处理左子数组
    12. QuickSort(arr, breakpoint + 1, right);    //处理右子数组
    13. }
    14.  
    15.  
    16. int PartionV3(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
    17. {
    18. assert(arr);
    19. int key = left;//取子数组最左边元素为key
    20. int slow = left;//slow从left开始  
    21. int fast = left + 1;//fast从left+1开始遍历数组
    22. while (fast <= right)
    23. {
    24. if (arr[fast] < arr[key])//fast找到比key小的值
    25. {
    26. ++slow;   //slow指向下一个位置
    27. if (slow != fast)//fast和slow相等没必要交换
    28. {
    29. swap(&arr[slow], &arr[fast]);//交换slow和fast所指向的值
    30. }
    31. }
    32. ++fast; //fast遍历数组
    33. }
    34. swap(&arr[key], &arr[slow]);         //最后交换key和slow所指向的变量
    35. return slow;   //返回slow位置下标
    36. }

  • 注意递归出口的控制和递归调用的传参方式

快排时空复杂度分析(所处理的数组为逆序数极大的乱序数组的情形)

  • 在面对逆序数极大的乱序数组时,可以认为每个子数组中key元素都会被交换到数组的中间位置

  • 该种情形下,每次分割数组时,分割点都在数组的中间位置,则递归函数执行时,数组被逐步分割的图示(图中展示了每个函数栈帧所处理的子数组)：

    假设原数组有N个元素,每个子数组都要进行一次单趟排序找分割点(每次单趟排序都要遍历一次子数组),因此对于每一个拆分层次中的每一个子数组,算法的循环执行次数数量级为O(N),而拆分层次(类似于二叉树的高度)数量级为O(logN),此时快排的时间复杂度为O(NlogN).

  • 快排的空间复杂度取决于递归的深度,也就是数组拆分层次的高度,在上述情形下递归深度的数量级为:O(logN),此时快速排序的空间复杂度为O(logN).

快排效率实测:

  • 让快排和希尔排序并驾齐驱,排序两个相同的由100万个随机数构成的数组: 
    1. int main()
    2. {
    3.     srand((unsigned int)time(0));
    4. const int N = 1000000;
    5. int* arr1 = (int*)malloc(sizeof(int) * N);
    6. int* arr2 = (int*)malloc(sizeof(int) * N);
    7. int* arr3 = (int*)malloc(sizeof(int) * N);
    8. for (int i = 0; i < N; ++i)
    9. {
    10. arr1[i] = rand();
    11. arr2[i] = arr1[i];
    12. arr3[i] = arr1[i];
    13. }
    14.  
    15. int begin2 = clock();
    16. ShellSort(arr2, N);
    17. int end2 = clock();
    18. printf("ShellSort:%d\n", end2 - begin2);
    19.  
    20. int begin3 = clock();
    21. QuickSort(arr3, 0,N-1);
    22. int end3 = clock();
    23. printf("QuickSort:%d\n", end3 - begin3);
    24. }

四.未经进一步优化的快速排序的缺陷

  • 未经进一步优化的快速排序在处理有序(或接近有序)的序列时,其时间复杂度会升阶为O(N^2),其原因分析如下:

在快速排序的单趟排序中,我们总是选取arr[left]作为key元素,因此在处理有序(或接近有序)的序列时,key元素的最终位置在大多数情况下不变,因此整个递归过程中数组被逐步划分的过程的图示为:

  • 划分层次的数量级同时也是递归的深度,因此在处理有序(或接近有序)的序列时,未经优化进一步的快排还会大量消耗系统栈空间,存在着栈溢出的风险
  • 类似地,如果key元素是数组中的最大或最小值,数组的划分也会出现上图中的情形,可见为了保证快排的效率,key元素最好取数组中接近中位数的元素(保证数组每次划分都接近二等分,这样递归时才能保证递归的深度尽可能小(可以借助二叉树的结构来理解这一点,相同结点数目下,满二叉树的高度最小))
  • 所以快排单趟排序的key元素的选取方式还有待优化,下篇文章再详细讨论。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览41810 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪