快速排序、归并排序、计数排序-二、快速排序

时间：2025-05-14 11:09:35

算法介绍

快速排序是一个很有名的排序算法，被C和C++都采用为库函数中标准排序算法的底层代码，快速排序顾名思义它确实很“快”，效率很高。历史上于1962年由Hoare首先提出，是一种基于二叉树结构的交换排序算法，后续有许多大佬对这个算法有过优化，基于其根本思想有多种不同的实现方法。快速排序的根本思想是：任取待排序元素序列的中的某元素作为基准值，按照该基准值将待排序集合分割为两个子序列，每个子序列均大于或小于基准值，然后将每个子序列看作单独的序列重复该操作，直到所有元素都排列在相应位置上为止。这个算法的唯一特殊之处在于如何找基准值，快速排序有多种版本也是区别在于如何更好的取这个基准值，如最开始的Hoare版本和后来更好一些的lomuto前后指针法。但整体这个算法依旧是非常高效的算法。下面我来一一具体阐述。

递归实现

  • Hoare版本算法

    • Hoare版的算法逻辑：
      Hoare版的算法中利用递归实现分割子序列，而找基准值的方法是：直接取最左边的数据令为基准值，取剩下的序列的最左右的值作为一个 “指针”（看作指向这个数据的下标）从左右往中心遍历数组，对于排升序的情况：左“指针”找比基准值小的数据，右“指针”找比基准值大的数据，各自找到之后，将左右指针对应的数据作交换，两“指针”按原路线继续往下遍历，当左指针>右指针时，把基准值对应数据和右指针作交换，完成分割。接下来就是递归，重复操作直至完成排序。
    • Hoare代码实现
    int Findkey(int* arr,int left,int right)//额外写一个找基准值的函数，完成找基准值和分割序列的工作
{
	int key = left;
	++left;//左右两侧开始遍历
	while(left <= right)//开始调整序列分割
	{
		if(left<=right && arr[left] < arr[key])//还是排升序，这是在确定左右要交换的数据
		{
			left++;
		}
		if(left<=right && arr[right] > arr[key])
		{
			right--;
		}
		if(left<=right)
		{
			swap(&arr[left++],&arr[right--]);//交换完之后记得继续往下遍历
		}
		swap(&arr[right],&arr[key]);//最后交换基准值完成分割
	}	
	return right;//right下标才是作分割的位置
}
void Quicksort(int* arr,int left,int right)//这里主函数参数不同了，要取序列左右下标值完成分割
{
	if(left >=  right)
	{
		return;
	}
	int key = Findkey(arr,left,right);//找基准值的下标
	Quicksort(arr,left,key - 1);//从key这里开始分割
	Quicksort(arr,key + 1,right);
}

  • lomuto前后指针法

    • 算法逻辑
      lomuto前后指针法基于快速排序的根本思想，提出了一种新的找基准值的方法：创建前后指针，从左往右找比基准值小的进行交换（升序情况），使得比基准值小的都排在基准值的左边。比如我们创建两个“指针”，一个prev，一个cur，先找最左边的作为基准值，prev等于最左端的下标，cur初始时比prev要大一，让cur在前面“探路”找比基准值要小的数据，找到之后，先将prev加1，再将prev和cur指针对应的数据交换，然后让cur继续往前走，没有找到就往前走直到找到为止。最后就得到了分割好的两个子序列，继续递归重复这个操作，快速排序就完成了。

    • lomuto前后指针实现

    void Findkey(int* arr,int left,int right)
{
	int key = left;
	int prev = left + 1,cur = prev + 1；
	while(cur <= right)
	{
		if(arr[cur] < arr[key] && ++prev != cur)//相等的话就是自己跟自己调位置，没必要
		{
			swap(&arr[prev],&arr[cur]);
		}
		cur++;
	}
	swap(&arr[key],&arr[prev]);
	return prev;
}
void Quicksort(int* arr,int left,int right)
{
	if(left >=  right)
	{
		return;
	}
	int key = Findkey(arr,left,right);
	Quicksort(arr,left,key - 1);
	Quicksort(arr,key + 1,right);
}

  • 时间复杂度分析
    快速排序的原理是每次找基准值同时遍历对应的序列完成调整，然后是分割递归，其实这跟归并的时间复杂度计算情况有点类似，每次递归的时间复杂度是O(N)，递归还是O(logN)，所以时间复杂度还是O(N*logN)。

非递归实现

快速排序的实现是从最开始的序列开始调整分割，然后从左至右对分割出来的每个序列再次分割调整，具有一定的顺序性才能正确完成排序。递归是存在顺序的，它先递推再回归，那么如果不用递归实现，那么就可以利用栈这个数据结构，每一次将分割出来的两个序列的左右边界入栈，然后取栈顶取到要调整分割的序列边界，不断重复直到调整完成。
现在我们来实现一下这个代码，由于要使用栈这个数据结构，在C语言阶段还需要额外实现栈这个数据结构然后利用栈的各种操作来完成算法，这里作者直接默认包含了一个栈相关操作的头文件，是跟我之前那篇栈文章的实现代码，大家如果不知道可以去看看 ^ V ^

#include"Stack.h"

void Quicksort(int* arr,int left,int right)
{
	ST st;//创建一个栈
	STinit(&st);
	STPush(&st,left);
	STPush(&st,right);
	while(!STEmpty(&st))
	{
		int end = STTop(&st);//取栈顶两次，拿到左右边界，记得先取的是右边界
		STPop(&st);
		int begin = STTop(&st);
		STPop(&st);
		int key = begin;//在[begin,end]里调整分割
		int prev = begin,cur = prev + 1;//用一下lomuto前后指针法
		while(cur <= end)
		{
			if(arr[cur] < arr[key] && ++prev != cur)
			{
				swap(&arr[cur],&arr[prev]);
			}
			cur++;
		}
		swap(&arr[prev],&arr[key]);
		key = prev;
		//把左右序列都入栈，注意先右后左入栈，这样就先取到左序列开始调整
		if(key + 1 < end)//确保有效序列
		{
			STPush(&st,key + 1);
			STPush(&st,end);
		}	
		if(begin < key - 1)
		{
			STPush(&st,begin);
			STPush(&st,key - 1);
		}
	}
	STDestroy(&st)
}

算法的一种优化—三路划分法

  • 快速排序算法性能的探讨
    快速排序效率的关键影响因素就是key这个基准值，每一趟排序之后，key对于序列的分割如果是基本二分居中，那么效率将会最大化，当然实际中的情况并不太可能每次都二分居中，但有偏差性能也都是可控的，基本没什么波动。但如果是每次都取到最大最小值，那么排序就将变成双层循环，性能快速的退化到O(N^2)，这是很可怕的，另一种情况是数据中存在大量的和基准值相等的数据，那么也相当的影响效率，这里用一种优化算法来处理也就是三路划分法。

  • 算法思想：
    为了让相同值不再影响，我们把相同值放在中间，然后再次划分左右两边的子序列。也就是这里的快速排序不再是仅仅划分两个子序列，而是将数据划分成三个部分。首先基准值key还是默认取最左侧值，类似lomuto前后指针法，定义left变量指向区间最左边，right变量指向区间最右边，cur初始指向left+1的位置。遇到比基准值小的和left交换，left和cur均++，遇到比基准值大的就与right交换，同时仅需right-1（因为cur值从左往右遍历），遇到和基准值相等的就直接让cur往前走。直至完成排序。

  • 代码实现

void Quicksort(int* arr,int n)
{
	if (left >= right)                       
	{
		return;
	}
	int begin = left;
	int end = right;
	int randi = left + (rand() % (right - left + 1));//随机选值作为基准值，减少取到极值的可能性
	Swap(&arr[left], &arr[randi]);
	int key = arr[left];
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < key)
		{
			Swap(&arr[cur], &arr[left]);
			cur++;
			left++;
		}
		else if (arr[cur] > key)
		{
			Swap(&arr[cur], &arr[right]);
			right--;
		}
		else
		{
			cur++;
		}
	}
	Quicksort(arr, begin, left - 1);
	Quicksort(arr, right + 1, end);
}
  • 三路划分法对于数据重复的情况下效率依旧可以保持，但是对于其他情况还是一般，总体来说还是只是算法的一种优化，能够应对特殊的情况。但是快速排序依旧不能够完全的凭借本身的算法面对所有问题，所以在C++中，库虽然采用了快速排序作为标准排序算法，但当快速排序的递归进程过深（即时间复杂度快速升高，性能退化）的时候会自动的转向堆排序完成排序任务。当然，现实情况中肯定不会时刻都在处理特殊情况，它毋庸置疑还是一个非常强大的排序算法。

相关文章