快速排序

快速排序是霍尔(Hoare)于1962年提出的一种二叉树结构的交换排序方法。快速排序是一种常用的排序算法，其基本思想是通过选择一个元素作为"基准值"，将待排序序列分割成两个子序列，其中一个子序列的元素都小于等于基准值，另一个子序列的所有素都大于基准值。然后对这两个子序列分别进行递归排序，最后将排好序的子序列合并起来，即可得到完整的有序序列。

思想

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

霍尔版本

霍尔版本单趟排序代码实现

定义两个下标left和right。假设keyi在最左边，那么右边先走。当右边找到比keyi小的就停下。然后左边开始走，当左边找到比keyi大的就停下。交换左右的值。然后直到左右指针碰面，那么将left和keyi的值交换。

void QuickSort(int* arr,int begin, int end)
{
   int left = begin;
    int right = end;
    int keyi = left;
    while (left < right)
    {
        //右边先走
        while (left < right && arr[right] >= arr[keyi])
        {
            right--;
        }
        while (left < right && arr[left] <= arr[keyi])
        {
           left++;
        }
        Swap(&arr[left], &arr[right]);
    }
    Swap(&arr[keyi], &arr[left]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

霍尔版本排序代码实现

当单趟排序把第一个keyi的数据放到它应该蹲的位置时，此时数组就可以分成三个部分，分别是[begin,keyi-1],keyi,[keyi+1,end]。此时依据二叉树的递归分治的思路将子区间的数据再次选左边为keyi来进行单趟排序，直到子区间不存在。最后就能够将数据排序。

针对已有序数组的优化

针对已经有序数组的排序，上面的代码有一个致命的问题。即未优化的快排最坏的情况下时间复杂度为O(N^2)。当数据量大的时候，还会有因为递归而栈溢出的问题。下面介绍第一种优化的方式，即随机数选keyi。

随机数选keyi

通过取数组长度的随机数做keyi，可以在一定程度上避免了完全有序或者接近有序的情况下快速排序的时间复杂度问题。下面简单看一下处理的方式

三数取中

通过最左边、最右边和中间位置的值作比较，取中间值来做下标keyi。这样在一定程度上可以优化有序或局部有序情况下，快速排序效率下降的问题。

挖坑法

挖坑法单趟排序代码实现

由于霍尔大佬的方法比较晦涩难懂，所以就有了我们现在要介绍的挖坑法。挖坑法顾名思义就是根据快排思想下的优化出来的一个版本。先假设key在最左边的数，所以坑位在左边。那么从右边开始走，当碰到比key小的就把它放到坑中，并且将坑位改变到停下的位置。左边同理。

void QuickSort1(int* arr, int begin, int end)
{
    int left = begin;
    int right = end;
    随机选key
    通过随机数来选择key，优化了顺序和逆序的情况下的时间复杂度
    //int randi = left + (rand() % (right - left));
    //
    //Swap(&arr[randi], &arr[left]);

    //三数取中优化
    int ret = GetMidNum(arr, left, right);
    if (left != ret)
        Swap(&arr[ret], &arr[left]);

    //左边做key
    int key = arr[left];
    int hole = left;
    while (left < right)
    {
        //右边先走
        while (left < right && arr[right] >= key)
        {
            right--;
        }
        //右边比key小就把它填到坑里，并改变坑位
        arr[hole] = arr[right];
        hole = right;
        while (left < right && arr[left] <= key)
        {
            left++;
        }
        //左边比key大就把它填到坑里，并改变坑位
        arr[hole] = arr[left];
        hole = left;
    }
    //最后坑位就是key应该蹲的位置
    arr[hole] = key;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

挖坑法代码实现

前后指针法

前后指针法单趟排序代码实现

实现思路如下：首先定义两个指针prev和cur。以最左边作key，cur找小，当cur指向的内容比key小，++prev，prev的值和cur值交换位置（位置重合可以不交换）。当cur找到的值比key大时，++cur。这种方法的大体情况分为两种，一、prev紧跟cur。二、prev和cur直接间隔这一段比key的值。那么此时比key大的值会逐步往后翻，比key小的值会逐步往前甩。

前后指针法代码实现

小区间优化

我们知道快速排序其实就是运用了二叉树结构分治的思想来进行排序的。在二叉树这种结构中，当高度为h时，我们考虑最优情况下（满二叉树），最后一层的结点就是2^(h-1)个。占据整棵树的一半。倒数第二层的结点个数为2 ^ (h-2)个，占整棵树结点的25%。其实只要消灭了倒数三层的递归其实就可以在大体上减少递归带来的损耗，提高效率，并且可以让栈区空间的损耗降低。在一个局部有序的小区间内进行优化，我们可以选择的排序有很多种。但是，根据我们前面所学知识我们可以发现，其实使用堆排序和希尔排序相对于小区间优化的优势并没有很明显。前者需要建堆，后者需要根据gap来进行预排序。选择插入排序来小区间优化其实是最适合的。因为在局部有序的区间内，插入排序的效率是最高的。

快速排序非递归实现

利用栈来存需要递归的区间，然后根据栈后进先出的性质来模拟递归的顺序。把区间化成子区间进行继续排序。直到区间不存在或区间只有一个数就停止将区间的下标入栈。

快速排序的特性总结

一、快速排序是一个综合性能较好和使用场景比较广泛的排序。
二、快速排序的时间复杂度为O(NLogN)。

在最好情况下，快速排序的时间复杂度为O(nlogn)。当待排序的序列能够均匀地分成两个子序列时，每次分割操作都能将序列大致平分，此时递归调用层数为logn，每层需要的比较次数为n，因此总比较次数为O(NLogN)。在最坏情况下，快速排序的时间复杂度为O(n ^ 2)。当待排序的序列已经有序或基本有序（例如，序列已经是升序排列，但选择的基准值总是最小或最大元素），每次分割操作只能切割出一个子序列，递归调用的层数为n，每层需要的比较次数为n，因此总比较次数为n ^ 2。然而，通过随机选择基准值或使用三数取中法等优化方法，可以减少最坏情况发生的可能性，从而提高了快速排序的平均性能。在实际应用中，快速排序通泛使用。
三、快速排序是一个不稳定的排序。

代码获取