快速排序的优化3: 三路快速排序，C语言实现-向日葵屋

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

在上一节中，我们处理相同的数据的方式是让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;
}

运行结果：

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