快速排序的优化3: 三路快速排序，C语言实现

浅浅的花香味﹌ 2023-03-01 12:50 11阅读 0赞

在上一节中，我们处理相同的数据的方式是让i和j轮流移动。其实如果把与基准相同的数据统一集中放置，那么这些数据就不需要再次排序了，这样就可以让算法进行的更快。具体的做法是这样：用一个cur游标遍历要排序的数组，把数据分为三类：比基准小的数，与基准相等的数，比基准大的数。我们在排序过程中，把比基准小的数放在最左边，与基准相等的数放在中间，比基准大的数放在最右边。接下去只需要对左边一段数据和右边一段数据进行递归排序即可，中间一段数据就不需要排序了。这就是三路快速排序。  
另外，当元素个数 < 50时，插入排序比高级排序更快，所以在大量数据的排序过程中，先用快速排序把数组分成多个小数组，然后利用插入排序对小数组进行排序，最后拼接成完整、有序的数组。经过这些优化后，快速排序已经是公认最快的排序方法了，不过快速排序的缺点也很明显：1、它是不稳定的排序方法；2、它的空间复杂度为O(logN) 或O(N)；3、最差的情况下，时间复杂度为O(N \* logN)。在绝大多数可能下，快速排序都不会退化成冒泡排序。当我们不在乎数据的稳定性以及空间复杂度时，快速排序就是最好的排序方法。  
注：排序方法中的“稳定”指的是排序结果稳定，而不是性能稳定。

下面是三路快速排序的代码：

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    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 insertionSort(int left, int right) //插入排序 
    {
        
        for (int i = left + 1; i <= right; i++) 
    	{
        
            int cur = arr[i];
            int j = 0;
            for (j = i - 1; j >= 0 && cur < arr[j]; j--) 
    		{
        
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = cur;
        }
    }
    
    //三个参数：待排序的数组，待排序的最左边，最右边下标 
    void quickSort(int arr[], int low, int high) //三路快速排序 
    {
        
    	if(low > high) //递归的出口 
    	{
        
    		return;
    	}
    	
    	if(high - low < 50) //数据规模很小的时候，可以用插入排序 
    	{
        
    		insertionSort(low, high);
    		return; //不要忘记返回
    	}
    	
    	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); //交换首元素和随机位置的数据 
    
    	int num = arr[low]; //取最左边的元素作为基准 
    	
    	//当前cur下标还没有与j相遇时继续循环
    	//也就是与基数相等的数据刚好跟大于基数的数据接触时停止循环 
    	while(cur <= j)  
    	{
        
    		if(arr[cur] == num) //把与基数相等的数据放在中间 
    		{
        
    			cur++;
    		}
    		
    		//把小于基数的数据都放在左边
    		//左边已经放了与基数相等的数，交换一下，把与基数相等的数放到中间
    		else if(arr[cur] < num) 
    		{
        
    			swap(cur, i); //把下标为cur的值与i交换 
    			cur++;
    			i++;
    		}
    		
    		//大于基数的数据都放在最右边，从右往左放置
    		else //if(arr[cur] > num) 
    		{
        
    			swap(cur, j); //把下标为cur的值与j交换 
    			j--;
    		}
    	}
    	
    	//一轮循环之后，数组arr分为三段：小于基准的数，等于基准的数、大于基准的数。
    	//中间一段数组 (下标：i ~ j) 已经有序了。只需要对左右两段数组继续排序即可。 
    	quickSort(arr, low, i - 1); //左边一段数组继续排序，左边一段数组的终点是i - 1 
    	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个数据，三路快速排序耗时：%d秒\r\n", size, t2 - t1);
    	return 0;
    }

运行结果：

![在这里插入图片描述][2020072610040872.png]  
原始的快速排序算法、优化1算法都很容易退化成冒泡排序。这样的算法就像是定时炸弹，我们不知道它什么时候就炸了 (退化成冒泡排序)，也就是说这两个排序看上去很好，但实际上是不能用的。优化2算法对于人为构造的锯齿形数据也表现牵强。本节的三路快速排序算法在随机数据、升序、降序、大量 (完全) 相同的数据等都有很好的表现，所以它才是我们第一个真正能用的快速排序算法。三路快速排序算法已经很好了，但是这个世界没有最好，只有更好，请看下一节：双基准三路快速排序算法。

[2020072610040872.png]: /images/20230208/6aa8bea775e94c14b3cf5fe2c1d6a32e.png