八大排序算法之快速排序(上篇)(未经优化的快排)-Toy模板网

这篇具有很好参考价值的文章主要介绍了八大排序算法之快速排序(上篇)(未经优化的快排)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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)作为key
	while (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];                    //取数组左端元素为key
	int hole = left;						//取数组左端位置为初始坑位
	while (right > left)
	{
		while (right > left && arr[right] >= key)  //right下标寻找比key小的值
		{
			--right;
		}
		arr[hole] = arr[right];                    //将right位置的变量放到hole位置上
		hole = right;                              //更新坑位						   
		while (right > left && arr[left] <= key)   //left下标寻找比key大的值
		{
			++left;
		}
		arr[hole] = arr[left];                     //将right位置的变量放到hole位置上
		hole = left;                               //更新坑位					   
	}
	arr[left] = key; //right和left相遇后,将key放到相遇位置                
	return left;     //返回数组分割点
}
选择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;							//取子数组最左边元素为key
	int 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;							//取子数组最左边元素为key
	int 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元素是数组中的最大或最小值,数组的划分也会出现上图中的情形,可见为了保证快排的效率,key元素最好取数组中接近中位数的元素(保证数组每次划分都接近二等分,这样递归时才能保证递归的深度尽可能小(可以借助二叉树的结构来理解这一点,相同结点数目下,满二叉树的高度最小))

所以快排单趟排序的key元素的选取方式还有待优化,下篇文章再详细讨论。