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

创始人

2025-05-30 03:40:41

0次

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

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

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

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

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

代码实现:

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

代码实现:

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

代码实现:

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

递归函数实现:

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

快排效率实测:

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

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

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

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

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

🤓冒泡排序的算法思想:

N个元素的数组则进行N-1趟排序
每一趟排序将数组中的一个元素交换到其最终应该出现的位置(比如将第n大的数交换到数组下标为N-n的位置)
算法图解：
🤓代码实现:
void swap(int* e1, int* e2)
{assert(e1 && e2);int tem = *e1;*e1 = *e2;*e2 = tem;
}void BubbleSort(int* arr, int size)
{assert(arr);int turns = 0;								//记录排序的趟数int flag = 0;								//flag用于标记数组是否已经有序while (turns < size - 1)                    //n个元素要完成n-1趟冒泡排序(将n-1个较大元素依次置于数组后缀){flag = 1;for (int i = 0; i < size - turns - 1; ++i)//内层循环可以完成一个元素的排序(将最大元素交换到数组size-turns-1的位置){if (arr[i] > arr[i + 1]){swap(&arr[i], &arr[i + 1]);       //将较大的元素向后交换flag = 0;}}if (flag)								  //flag为1说明数组已经有序{                        break;                                //数组已经有序则可以结束循环}++turns; //继续下一趟排序}
}
冒泡排序算法的复杂度计算公式(最坏情况下)是一个等差数列求和式,因此其时间复杂度为O(N^2)(这里只考虑最坏的情形)
冒泡排序的单趟排序:
for (int i = 0; i < size - turns - 1; ++i)//内层循环可以完成一个元素的排序(将最大元素交换到数组size-turns-1的位置)
{if (arr[i] > arr[i + 1]){swap(&arr[i], &arr[i + 1]);       //将较大的元素向后交换flag = 0;                         //标记出数组无序}
}
冒泡排序的单趟排序会把前(size-turns)个元素中的最大值交换到(size-turns-1)的位置(增加数组的有序后缀长度)
冒泡排序单趟排序关注的是数组无序前(后)缀中的最值,这一点限制了算法优化的思路

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

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

🤓利用双指针算法来设计单趟排序过程以达到以下目的:在数组中选取一个key元素,将比key小的元素交换到key元素的左边,将比key大的元素交换到key元素的右边
🤓由于key元素左边的子数组每个元素的值都比key元素小,key元素右边的子数组每个元素的值都比key元素大,因此经过单趟排序后,key元素就被交换到了其在有序序列中最终应该出现的位置),同时,左右子数组我们可以分开完成排序(这一点非常关键).图示:😉(算法的具体实现后面再深究)😉
🤓根据单趟排序过程确定的key元素的最终位置(比如上图中的数组下标为5的位置)为分割点,将数组分为左右子数组(子数组中不包含key元素):
🤓在子数组中我们分别再进行单趟排序,并以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指向子数组最后一个元素)
下文所谓的指针都指代数组下标
单趟排序算法实现思想:

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

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

单趟排序实现的方法二:挖坑法
算法接口首部：
int PartionV2(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
left和right是待处理的子数组的下标区间(我们取开区间,即left指向子数组第一个元素,right指向子数组最后一个元素)
单趟排序算法实现思想:

选择arr[left]作为key元素(key变量存储key元素的值)
以left指向的位置作为初始坑位(坑位下标用hole变量来记录)
right指针向前遍历寻找比key小的数,找到后将right指向的元素交换到坑位上,将right下标值赋给hole(更新坑位)
left指针向后遍历寻找比key大的数,找到后将left指向的元素交换到坑位上,将left下标值赋给hole(更新坑位)
重复上述迭代过程直到left指针和right指针相遇
left指针和right指针相遇后,将key元素放到相遇位置处完成单趟排序(此时保证了两指针相遇的位置之前的元素都比key小,相遇位置之后的元素都比key大)
同样地,算法流程中相当于用left下标来维护由比key小的元素构成的数组前缀,用right下标来维护由比key大的元素构成的数组后缀
算法gif:
代码实现:
int PartionV2(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
{assert(arr);int key = arr[left];                    //取数组左端元素为keyint hole = left;						//取数组左端位置为初始坑位while (right > left){while (right > left && arr[right] >= key)  //right下标寻找比key小的值{--right;}swap(&arr[hole], &arr[right]);             //将right位置的变量放到hole位置上hole = right;							   //更新坑位while (right > left && arr[left] <= key)   //left下标寻找比key大的值{++left;}swap(&arr[hole], &arr[left]);			   //将right位置的变量放到hole位置上hole = left;							   //更新坑位}arr[left] = key; //right和left相遇后,将key放到相遇位置                return left;     //返回数组分割点
}
理解了该种算法后,可以将hole变量省略掉
选择arr[left]作为key元素同样一定要先让right指针向前找比key小的值

单趟排序实现的方法三:快慢指针法
算法接口首部：
int PartionV3(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
left和right是待处理的子数组的下标区间(我们取开区间,即left指向子数组第一个元素,right指向子数组最后一个元素)
单趟排序算法实现思想:

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

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

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

每经过一次单趟排序,就可以将数组中选定的key元素交换到其在有序序列中最终应该出现的位置(同时该位置前的所有元素都比key小,该位置后的所有元素都比key大)比如:
因此最终key元素所在的位置就可以将数组分割为两个不包含key元素的子数组(两个子数组在后续的排序过程中互不关联),对于左右两个子数组我们又可以以相同的方式继续分割,形成分治递归,直到数组被分割为多个(原数组元素个数为N)只有单个元素构成的子数组,排序就完成了(此时所有元素都被交换到了其在有序序列中最终应该出现的位置)
快排递归函数首部 :
void QuickSort(int* arr, int left,int right)
调用时传入待排序的数组区间[left,right];
递归函数实现:
int PartionV3(int* arr, int left, int right);
void QuickSort(int* arr, int left,int right)
{assert(arr);if (left >= right)						     //子数组只剩一个元素时(或left和right错开时)停止递归{return;}int breakpoint = PartionV3(arr, left, right);//找到数组分割点(同时也完成了一个元素的排序)//左右子数组分治递归QuickSort(arr, left, breakpoint - 1);     //处理左子数组QuickSort(arr, breakpoint + 1, right);    //处理右子数组
}int PartionV3(int* arr, int left, int right)//完成1个元素的排序,同时分割数组
{assert(arr);int key = left;							//取子数组最左边元素为keyint slow = left;						//slow从left开始  int fast = left + 1;					//fast从left+1开始遍历数组while (fast <= right){if (arr[fast] < arr[key])			//fast找到比key小的值{++slow;				   			//slow指向下一个位置if (slow != fast)				//fast和slow相等没必要交换{swap(&arr[slow], &arr[fast]);//交换slow和fast所指向的值}}++fast;							 //fast遍历数组}swap(&arr[key], &arr[slow]);         //最后交换key和slow所指向的变量return slow;  						 //返回slow位置下标
}
注意递归出口的控制和递归调用的传参方式
快排时空复杂度分析(所处理的数组为逆序数极大的乱序数组的情形)

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

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

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

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

快排效率实测:
让快排和希尔排序并驾齐驱,排序两个相同的由100万个随机数构成的数组:
int main()
{srand((unsigned int)time(0));const int N = 1000000;int* arr1 = (int*)malloc(sizeof(int) * N);int* arr2 = (int*)malloc(sizeof(int) * N);int* arr3 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){arr1[i] = rand();arr2[i] = arr1[i];arr3[i] = arr1[i];}int begin2 = clock();ShellSort(arr2, N);int end2 = clock();printf("ShellSort:%d\n", end2 - begin2);int begin3 = clock();QuickSort(arr3, 0,N-1);int end3 = clock();printf("QuickSort:%d\n", end3 - begin3);
}

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

未经进一步优化的快速排序在处理有序(或接近有序)的序列时,其时间复杂度会升阶为O(N^2),其原因分析如下:
在快速排序的单趟排序中,我们总是选取arr[left]作为key元素,因此在处理有序(或接近有序)的序列时,key元素的最终位置在大多数情况下不变,因此整个递归过程中数组被逐步划分的过程的图示为:

划分层次的数量级同时也是递归的深度,因此在处理有序(或接近有序)的序列时,未经优化进一步的快排还会大量消耗系统栈空间,存在着栈溢出的风险
所以快排单趟排序的key元素的选取方式还有待优化,下篇文章再详细讨论。