快速排序的优化4: 双基准三路快速排序，C语言实现

客官°小女子只卖身不卖艺 2023-03-01 13:57 10阅读 0赞

在堆排序 (见本章第三节) 的改进中，我们发现如果把标准的二叉堆改成三叉堆、四叉堆可以提高堆的效率。特别是四叉堆是所有堆中效率最高的堆。改进的思路：增加子节点的个数，可以降低堆的高度，所以可以提高堆的效率。同样的，如果快速排序可以把数组分成三段，同样可以减少划分的次数，提高算法的效率。  
我们对快速排序算法进行改进：分别选取数组两端的元素作为基准 (要求standard1 ≤ standard2)，把 ≤ standard1的数放在数组最左边，把 ≥ standard2的数放在最右边，把介于两个基准数之间的数放在中间。用这种方式可以把数据分成三段。如下图所示。在这个过程中，我们不刻意去寻找两个基准数的准确位置，只把这两个基准数放在各自合适的区域即可。可以预见：standard1一定在最左边的区域里，standard2一定在最右边的区域里。用这种方式，数组被分成三段，中间一段也会有大量不相同的数据。把数据分成这样三部分之后，分别对这三部分进行递归排序即可。从n个数据开始进行递归，理论上只需要log3N次递归就可以完成递归。所以时间复杂度的下限为O(N \* log3N)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
时间复杂度的计算方式参考：https://www.jianshu.com/p/93ce432262f0  
T(n) = 3 \* T(n / 3) + n //first divide  
= 3 \* (3 \* T(n / 9) + n / 3）+ n //second divide (= 32 \* T(n / 9) + 3 \* n)  
= 3 \* (3 \* (3 \* T(n / 27) + n / 9) + n / 3) + n //third divide (=33 \* T(n / 27) + 3 \* n)  
= …  
= 3m + m \* n //Mth divide，第m次划分

由于3m = n, 所以m = log3N,  
所以 T(n) = N + N \* log3N = N \* (log3N + 1) = N \* log3N。

用这种方式进行排序时，如果待排序的数组中的所有元素都相等，则所有元素都会被划分到左边部分，这个子数组的长度与原数组一样，所以在递归排序时会陷入无限递归。我们参考1.2节的办法：让i和j指针轮着移动即可，这样i和j可以在数组的中间相遇。这个解决方案会把这个数组等分成两部分，也就是算法将退化成普通的快速排序，时间复杂度为O(N \* logN)。事实上，只要两个基准数相等，且都是最大值的时候都会导致这个问题。这个退化并不会明显降低排序效率。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]  
如果待排序的数据是升序 (降序) 的，则快速排序会退化成冒泡排序，用随机选择的一个元素作为基准可以有效的解决这个问题。这个策略用在这里也一样有效。而且用了这个策略之后，可以把数组分成三段，然后分三次递归排序。这个效率将会比三路快速排序更高。

对比原始的快速排序、三路快速排序、双基准的三路快速排序：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 2]从表格可以看到，当500万个数据都是随机值时，三种方式消耗的时间都差不多。当数据有序 (升序、降序或相等) 时，原始的快速排序就退化成冒泡排序了 (运行时间 > 60 秒)。当数据是按照升序或降序排列时，三路快速排序消耗的时间分别是21秒和12秒，而双基准三路排序消耗的时间分别是16秒和7秒，分别降低了24%和42%。由此可见，把数组分成三份后继续排序的方式是非常有效的。当所有的元素都相等时，三路快速排序消耗的时间非常短，这和它的机制相关，实际上三路排序对这些数据根本就没有进行排序。但即使是这种情况，双基准三路排序消耗的时间也仅仅是3秒，并不比三路快速排序慢太多。

伪代码教程：https://www.cnblogs.com/linuxAndMcu/p/11242905.html  
这个排序的伪代码如下：

flag ←1
    
    //myQuickSort is a two standards, three-way quick sorting algorithm 
    //arr is array, low is index of first number in arr, high is last index
    myQuickSort(arr, low, high) 
    	if low ≥ high //exit of quickSort
    		return
    	i ← low
    	j ← high
    	cur ← i 
    	
    	randomIndex = rand() % (high - low + 1) + low
    	arr[low] <-> arr[randomIndex]
    	
    	randomIndex = rand() % (high - low + 1) + low
    	arr[high] <-> arr[randomIndex]
    		
    	if arr[low] > arr[high] //make sure arr[low] ≤ arr[high]
    		arr[low] <-> arr[high]
    		
    	standard1 ← arr[low] //take arr[low] as standard1
    	standard2 ← arr[high] //take arr[high] as standard2
    		
    	while cur ≤ j  
    		do
    		if flag = 1 //Use flag to control i and j in turn  
    			if arr[cur] ≤ standard1 //put number smaller than standard1 at left of arr
    				then arr[cur] <-> arr[i]
    				i ← i + 1
    				cur ← cur + 1
    			else if(arr[cur] ≥ standard2) //put number bigger than standard2 at right of arr
    				then arr[cur] <-> arr[j]
    				j ← j - 1 
    			else //put number between standard1 and standard1 in middle of arr 
    				cur ← cur + 1
    		
    		else //if flag = 0
    			if arr[cur] ≥ standard2
    				then arr[cur] <-> arr[j] 
    				j ← j - 1
    			else if arr[cur] ≤ standard1 
    				then arr[cur] <-> arr[i]
    				i ← i + 1
    				cur ← cur + 1
    			else 
    				cur ← cur + 1
    		flag ← not flag //Reverse flag
    		end
    	
    	//arr was splitted into three subarrays
    	call myQuickSort(arr, low, i - 1) //Recursively sort subarrays
    	call myQuickSort(arr, i, j) //Recursively sort subarrays
    	call myQuickSort(arr, j + 1, high) //Recursively sort subarrays

总的来说，这是在三路快速排序的基础上发展的一种排序算法：双基准三路快速排序。这种方式采用两个基准，在排序过程中，该算法不刻意为这两个基准元素寻找正确的位置，整个数组被分成三部分，然后分别进行递归排序。双基准三路排序的效率是很高的，它的平均时间复杂度为O(N \* log2N)，最差的时间复杂度为 O(N2)，空间复杂度为O(log3N) ~ O(N)，它仍旧是不稳定的排序方法。双基准三路快速排序的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int flag = 1;
    int size = 0; //数组的大小 
    int arr [5000000]; //500万个数据的数组
    
    int getRandom(int m) //获得随机值
    {
        
    	return rand()%m; //把随机数控制在0~m-1之间
    }
    
    void swap(int i, int j) //交换
    {
        
    	int temp = arr[i];
    	arr[i] =  arr[j];
    	arr[j] = temp;
    }
    
    //三个参数：待排序的数组，待排序的最左边，最右边下标 
    void quickSort(int arr[], int low, int high) //三路快速排序 
    {
        
    	if(low >= high) //递归的出口 
    	{
        
    		return;
    	}
    	
    	//要求i及i左边的元素比num1小，j及j右边的元素比num2大 
    	int i = low; 
    	int j = high;
    	int cur = i; //cur用来遍历数组arr 
    	
    	//rand()%m; //把随机数控制在0~m-1之间
    	//所以下面这个语句的意思是把随机数控制在low ~ high之间 
    	int randomIndex = rand()%(high - low + 1) + low;
    	swap(low, randomIndex); //交换首元素和随机位置的数据 
    	
    	randomIndex = rand()%(high - low + 1) + low;
    	swap(high, randomIndex); //交换尾元素和随机位置的数据 
    
    	//要求从小到大排序，所以首元素一定要比尾元素小
    	if(arr[low] > arr[high])
    	{
        
    		swap(low, high);
    	}
    	
    	int num1 = arr[low]; //取最左边的元素作为基准1
    	int num2 = arr[high]; //取最右边的元素作为基准2
    		
    	//当前cur下标还没有与j相遇时继续循环
    	//也就是与基数相等的数据刚好跟大于基数的数据接触时停止循环 
    	while(cur <= j)  
    	{
        
    		if(flag) //用flag控制轮流移动i和j两个指针
    		{
        
    			if(arr[cur] <= num1)
    			{
        
    				swap(cur, i);
    				i++;
    				cur++;
    			}			
    			else if(arr[cur] >= num2) 
    			{
        
    				//大于基数的数据都放在最右边，从右往左放置
    				swap(cur, j); //把下标为cur的值与j交换 
    				j--; //从右往左放置，所以j--
    			}			
    			else //把数据大小在两个基数之间的数据放在中间 
    			{
        
    				cur++; //只需要移动cur，不需要移动i和j
    			}
    		}
    		else
    		{
        
    			//大于基数的数据都放在最右边，从右往左放置
    			if(arr[cur] >= num2) 
    			{
        
    				swap(cur, j); //把下标为cur的值与j交换 
    				j--; //从右往左放置，所以j--
    			}
    			else if(arr[cur] <= num1)
    			{
        
    				swap(cur, i);
    				i++;
    				cur++;
    			}
    			else //把数据大小在两个基数之间的数据放在中间 
    			{
        
    				cur++; //只需要移动cur，不需要移动i和j
    			}
    		}
    		flag = !flag; //反转flag的值
    	}
    	
    	//数组arr分为三段：小于基准1的数，大于基准1并小于基准2的数、大于基准的数。
    	//分别再对这三段数组进行递归排序。 
    	quickSort(arr, low, i - 1); //左边一段数组继续递归排序，左边一段数组的终点是i - 1 
    	quickSort(arr, i, j); //中间一段继续递归排序 
    	quickSort(arr, j + 1, high); //右边一段数组继续递归排序。右边一段数组的起点是j + 1 
    }
    
    int main()
    {
        
    	size = sizeof(arr) / sizeof(int);
    	
    	for(int i = 0; i < size; i++)
    	{
        
    		//arr[i] = 0; //全部为相同数据 
    		//arr[i] = i; //升序 
    		//arr[i] = size - i; //降序
    		//arr[i] = getRandom(10); //大量重复 
    		arr[i] = getRandom(100000); //很少重复 
    		//arr[i] = i % 2 == 0 ? 1 : 0; //锯齿形数据 
    	}
    	
    	time_t t1, t2; //计算排序时间 
    	t1 = time(0);
    	quickSort(arr, 0, size - 1); //三路快速排序。n个元素，最右边的下标是n - 1 
    	t2 = time(0);
    	
    	printf("%d个数据，ddo0三路快速排序耗时：%d秒\r\n", size, t2 - t1);
    	return 0;
    }

我们花了很大的篇幅介绍快速排序和它的各种改进方式，读者可以体会一下这个过程，对提高对代码的理解很有帮助。最后说明一下，这个排序算法的复杂度的下限为O(N \* log3N)，突破了教科书上的O(N \* log2N) 的理论下限。在JDK7中就采用双基准三路快速排序作为默认的排序方法。双基准三路快速排序仍然可以继续改进：把与基准相等的元素放在一起，这样就不需要对这些元素排序了。这个改进就交给读者自己完成吧。在实际使用时，我们选用优化3或优化4算法 (三路快速排序算法，或双基准三路快速排序算法) 即可。  
最后，我们说一下快速排序的思想：它是用递归和分治的思想设计的排序算法。我们在学习递归和动态规划时候就学过，动态规划是不能用于折半/加倍的情况的。所以快速排序不能用动态规划实现。在网上也能找到用迭代方法实现的快速排序算法，但它不是用动态规划实现的。它是利用了栈的一些性质，有兴趣的读者自己去找吧。快速排序的思想在线性查找中也有讨论，详情见“扩展篇”章节。

ps：这次的文章跟之前不太一样，多了性能测试，以及伪代码。另外，时间复杂度的下限为O(N \* log3N)，我对这个这个论断不是太有把握。希望有人能指出错误。谢谢。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230208/0dee13720a054fd7955dba4e698345f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200727123639355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200727123724161.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc=,size_16,color_FFFFFF,t_70