快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中，对数组，列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。
 
 
本文首先介绍快速排序的思路，算法的实现、分析、优化及改进，最后分析了.NET 中列表排序的内部实现。
 
 
一 原理
 
 
 
 
快速排序的基本思想如下：
 
 
对数组进行随机化。
从数列中取出一个数作为中轴数(pivot)。
将比这个数大的数放到它的右边，小于或等于它的数放到它的左边。
再对左右区间重复第三步，直到各区间只有一个数。
 
 
 
 
如上图所示快速排序的一个重要步骤是对序列进行以中轴数进行划分，左边都小于这个中轴数，右边都大于该中轴数，然后对左右的子序列继续这一步骤直到子序列长度为1。
 
 
下面来看某一次划分的步骤，如下图：
 
 
 
 
上图中的划分操作可以分为以下5个步骤：
 
 
获取中轴元素
i从左至右扫描，如果小于基准元素，则i自增，否则记下a[i]
j从右至左扫描，如果大于基准元素，则i自减，否则记下a[j]
交换a[i]和a[j]
重复这一步骤直至i和j交错，然后和基准元素比较，然后交换。
 
 
划分过程的代码实现如下：
 
 
/// <summary>
/// 快速排序中的划分过程
/// </summary>
/// <param name="array">待划分的数组</param>
/// <param name="lo">最左侧位置</param>
/// <param name="hi">最右侧位置</param>
/// <returns>中间元素位置</returns>
private static int Partition(T[] array, int lo, int hi)
{
    int i = lo, j = hi + 1;
    while (true)
    {
        //从左至右扫描，如果碰到比基准元素array[lo]小，则该元素已经位于正确的分区，i自增，继续比较i+1；
        //否则，退出循环，准备交换
        while (array[++i].CompareTo(array[lo]) < 0)
        {
            //如果扫描到了最右端，退出循环
            if (i == hi) break;
        }

        //从右自左扫描，如果碰到比基准元素array[lo]大，则该元素已经位于正确的分区，j自减，继续比较j-1
        //否则，退出循环，准备交换
        while (array[--j].CompareTo(array[lo]) > 0)
        {
            //如果扫描到了最左端，退出循环
            if (j == lo) break;
        }

        //如果相遇，退出循环
        if (i >= j) break;

        //交换左a[i],a[j]右两个元素，交换完后他们都位于正确的分区
        Swap(array, i, j);
    }
    //经过相遇后，最后一次a[i]和a[j]的交换
    //a[j]比a[lo]小，a[i]比a[lo]大，所以将基准元素与a[j]交换
    Swap(array, lo, j);
    //返回扫描相遇的位置点
    return j;
}
 
 
划分前后，元素在序列中的分布如下图：
 
 
 
 
二 实现
 
 
与合并算法基于合并这一过程一样，快速排序基于分割(Partition)这一过程。只需要递归调用Partition这一操作，每一次以Partition返回的元素位置来划分为左右两个子序列，然后继续这一过程直到子序列长度为1，代码的实现如下：
 
 
public class QuickSort<T> where T : IComparable<T>
{
    public static void Sort(T[] array)
    {
        Sort(array, 0, array.Length - 1);
    }

    private static void Sort(T[] array, int lo, int hi)
    {
        //如果子序列为1，则直接返回
        if (lo >= hi) return;
        //划分，划分完成之后，分为左右序列，左边所有元素小于array[index]，右边所有元素大于array[index]
        int index = Partition(array, lo, hi);

       //对左右子序列进行排序完成之后，整个序列就有序了
        //对左边序列进行递归排序
        Sort(array, lo, index - 1);
        //对右边序列进行递归排序
        Sort(array, index + 1, hi);
    }
}
 
 
下图说明了快速排序中，每一次划分之后的结果：
 
 
 
 
一般快速排序的动画如下：
 
 
 
 
三 分析
 
 
在最好的情况下，快速排序只需要大约nlgn次比较操作，在最坏的情况下需要大约1/2 n2 次比较操作。 
在最好的情况下，每次的划分都会恰好从中间将序列划分开来，那么只需要lgn次划分即可划分完成，是一个标准的分治算法Cn=2Cn/2+N，每一次划分都需要比较N次，大家可以回想下我们是如何证明合并排序的时间复杂度的。
 
 
在最坏的情况下，即序列已经排好序的情况下，每次划分都恰好把数组划分成了0，n两部分，那么需要n次划分，但是比较的次数则变成了n, n-1, n-2,….1, 所以整个比较次数约为n(n-1)/2~n2/2.
 
 
快速排序平均需要大约2NlnN次比较，来对长度为n的排序关键字唯一的序列进行排序。 证明也比较简单：假设CN为快速排序平均花在比较上的时间，初始C0=C1=0，对于N>1的情况，有： 
 
其中N+1是分割时的比较次数， 表示将序列分割为0，和N-1左右两部分的概率为1/N, 划分为1，N-2左右两部分的概率也为1/N，都是等概率的。
 
然后对上式左右两边同时乘以N，整理得到：
 
 
然后，对于N为N-1的情况：
 
 
两式相减，然后整理得到：
 
 
然后左右两边同时除以N(N+1)，得到:
 
 
可以看到，这是一个递归式，我们将 递归展开得到：
 
 
然后处理一下得到：
 
 
平均情况下，快速排序需要大约1.39NlgN次比较，这比合并排序多了39%的比较，但是由于涉及了较少的数据交换和移动操作，他要比合并排序更快。
为了避免出现最坏的情况，导致序列划分不均，我们可以首先对序列进行随机化排列然后再进行排序就可以避免这一情况的出现。
快速排序是一种就地(in-place)排序算法。在分割操作中只需要常数个额外的空间。在递归中，也只需要对数个额外空间。
另外，快速排序是非稳定性排序。
 
 
 
 
四 改进
 
 
对一般快速排序进行一些改进可以提高其效率。
 
 
1. 当划分到较小的子序列时，通常可以使用插入排序替代快速排序
 
 
对于较小的子序列（通常序列元素个数为10个左右），我们就可以采用插入排序直接进行排序而不用继续递归，算法改造如下：
 
 
private const int CUTTOFF = 10;
private static void Sort(T[] array, int lo, int hi)
{
    //如果子序列为1，则直接返回
    if (lo >= hi) return;
    //对于小序列，直接采用插入排序替代
    if (hi - lo <= CUTTOFF - 1) 
    {
        Sort<int>.InsertionSort(array, lo, hi);
        return;
    }
    //划分，划分完成之后，分为左右序列，左边所有元素小于array[index]，右边所有元素大于array[index]
    int index = Partition(array, lo, hi);

    //对左右子序列进行排序完成之后，整个序列就有序了

    //对左边序列进行递归排序
    Sort(array, lo, index - 1);
    //对右边序列进行递归排序
    Sort(array, index + 1, hi);
}
 
 
2. 三平均分区法(Median of three partitioning)
 
 
在一般的的快速排序中，选择的是第一个元素作为中轴(pivot),这会出现某些分区严重不均的极端情况，比如划分为了1和n-1两个序列，从而导致出现最坏的情况。三平均分区法与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为中轴，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说，主要有两点优势：
 
 
（1） 首先，它使得最坏情况发生的几率减小了。
 
 
（2） 其次，未改进的快速排序算法为了防止比较时数组越界，在最后要设置一个哨点。如果在分区排序时，中间的这个元素（也即中轴）是与最右边数过来第二个元素进行交换的话，那么就可以省略与这一哨点值的比较。
 
 
对于三平均分区法还可以进一步扩展，在选取中轴值时，可以从由左中右三个中选取扩大到五个元素中或者更多元素中选取，一般的，会有（2t＋1）平均分区法（median-of-(2t+1)。常用的一个改进是，当序列元素小于某个阈值N时，采用三平均分区，当大于时采用5平均分区。
 
 
采用三平均分区法对快速排序的改进如下：
 
 
private static void Sort(T[] array, int lo, int hi)
{
    //对于小序列，直接采用插入排序替代
    if (hi - lo <= CUTTOFF - 1) 
    {
        //Sort<int>.InsertionSort(array, lo, hi);
        return;
    }
    //采用三平均分区法查找中轴
    int m = MedianOf3(array, lo, lo + (hi - lo) / 2, hi);
    Swap(array, lo, m);
    //划分，划分完成之后，分为左右序列，左边所有元素小于array[index]，右边所有元素大于array[index]
    int index = Partition(array, lo, hi);

    //对左右子序列进行排序完成之后，整个序列就有序了

    //对左边序列进行递归排序
    Sort(array, lo, index - 1);
    //对右边序列进行递归排序
    Sort(array, index + 1, hi);
}

/// <summary>
/// 查找三个元素中位于中间的那个元素
/// </summary>
/// <param name="array"></param>
/// <param name="lo"></param>
/// <param name="center"></param>
/// <param name="hi"></param>
/// <returns></returns>
private static int MedianOf3(T[] array, int lo, int center, int hi)
{
    return (Less(array[lo], array[center]) ?
           (Less(array[center], array[hi]) ? center : Less(array[lo], array[hi]) ? hi : lo) :
           (Less(array[hi], array[center]) ? center : Less(array[hi], array[lo]) ? hi : lo));
}

private static bool Less(T t1, T t2)
{
    return t1.CompareTo(t2) < 0;
}
 
 
使用插入排序对小序列进行排序以及使用三平均分区法对一般快速排序进行改进后运行结果示意图如下：
 
 
 
 
3. 三分区(3-way partitioning) 快速排序
 
 
通常，我们的待排序的序列关键字中会有很多重复的值，比如我们想对所有的学生按照年龄进行排序，按照性别进行排序等，这样每一类别中会有很多的重复的值。理论上，这些重复的值只需要处理一次就行了。但是一般的快速排序会递归进行划分，因为一般的快速排序只是将序列划分为了两部分，小于或者大于等于这两部分。
 
 
既然要利用连续、相等的元素不需要再参与排序这个事实，一个直接的想法就是通过划分让相等的元素连续地摆放：
 
 
 
 
 
然后只对左侧小于V的序列和右侧大于V对的序列进行排序。这种三路划分与计算机科学中无处不在，它与Dijkstra提出的“荷兰国旗问题”(The Dutch National Flag Problem)非常相似。
 
 
Dijkstra的方法如上图：
 
 
从左至右扫描数组，维护一个指针lt使得[lo…lt-1]中的元素都比v小，一个指针gt使得所有[gt+1….hi]的元素都大于v，以及一个指针i，使得所有[lt…i-1]的元素都和v相等。元素[i…gt]之间是还没有处理到的元素，i从lo开始，从左至右开始扫描：
 
 
· 如果a[i]<v: 交换a[lt]和a[i],lt和i自增
 
 
· 如果a[i]>v:交换a[i]和a[gt], gt自减
 
 
· 如果a[i]=v: i自增
 
 
下面是使用Dijkstra的三分区快速排序代码：
 
 
private static void Sort(T[] array, int lo, int hi)
{
    //对于小序列，直接采用插入排序替代
    if (hi - lo <= CUTTOFF - 1)
    {
        Sort<int>.InsertionSort(array, lo, hi);
        return;
    }
    //三分区
    int lt = lo, i = lo + 1, gt = hi;
    T v = array[lo];
    while (i<=gt)
    {
        int cmp = array[i].CompareTo(v);
        if (cmp < 0) Swap(array, lt++, i++);
        else if (cmp > 0) Swap(array, i, gt--);
        else i++;
    }

    //对左边序列进行递归排序
    Sort(array, lo, lt - 1);
    //对右边序列进行递归排序
    Sort(array, gt + 1, hi);
}
 
 
三分区快速排序的每一步如下图所示：
 
 
 
 
三分区快速排序的示意图如下：
 
 
 
 
Dijkstra的三分区快速排序虽然在快速排序发现不久后就提出来了，但是对于序列中重复值不多的情况下，它比传统的2分区快速排序需要更多的交换次数。
 
 
Bentley 和D. McIlroy在普通的三分区快速排序的基础上，对一般的快速排序进行了改进。在划分过程中，i遇到的与v相等的元素交换到最左边，j遇到的与v相等的元素交换到最右边，i与j相遇后再把数组两端与v相等的元素交换到中间
 
 
 
 
 
这个方法不能完全满足只扫描一次的要求，但它有两个好处：首先，如果数据中没有重复的值，那么该方法几乎没有额外的开销；其次，如果有重复值，那么这些重复的值不会参与下一趟排序，减少了无用的划分。
 
 
下面是采用 Bentley&D. McIlroy 三分区快速排序的算法改进：
 
 
private static void Sort(T[] array, int lo, int hi)
{
    //对于小序列，直接采用插入排序替代
    if (hi - lo <= CUTTOFF - 1)
    {
        Sort<int>.InsertionSort(array, lo, hi);
        return;
    }
    // Bentley-McIlroy 3-way partitioning
    int i = lo, j = hi + 1;
    int p = lo, q = hi + 1;
    T v = array[lo];
    while (true)
    {
        while (Less(array[++i], v))
            if (i == hi) break;
        while (Less(v, array[--j]))
            if (j == lo) break;

        // pointers cross
        if (i == j && Equal(array[i], v))
            Swap(array, ++p, i);
        if (i >= j) break;

        Swap(array, i, j);
        if (Equal(array[i], v)) Swap(array, ++p, i);
        if (Equal(array[j], v)) Swap(array, --q, j);
    }

    //将相等的元素交换到中间
    i = j + 1;
    for (int k = lo; k <= p; k++) Swap(array, k, j--);
    for (int k = hi; k >= q; k--) Swap(array, k, i++);

    Sort(array, lo, j);
    Sort(array, i, hi);
}
 
 
三分区快速排序的动画如下：
 
 
 
 
4.并行化
 
 
和前面讨论对合并排序的改进一样，对所有使用分治法解决问题的算法其实都可以进行并行化，快速排序的并行化改进我在之前的浅谈并发与并行这篇文章中已经有过介绍，这里不再赘述。
 
 
五 .NET 中元素排序的内部实现
 
 
快速排序作为一种优秀的排序算法，在很多编程语言的元素内部排序中均有实现，比如Java中对基本数据类型(primitive type)的排序,C++，Matlab，Python，FireFox Javascript等语言中均将快速排序作为其内部元素排序的算法。同样.NET中亦是如此。
 
 
.NET这种对List<T>数组元素进行排序是通过调用Sort方法实现的，其内部则又是通过Array.Sort实现，MSDN上说在.NET 4.0及之前的版本，Array.Sort采用的是快速排序，然而在.NET 4.5中，则对这一算法进行了改进，采用了名为Introspective sort 的算法，即保证在一般情况下达到最快排序速度，又能保证能够在出现最差情况是进行优化。他其实是一种混合算法：
 
 
当待分区的元素个数小于16个时，采用插入排序
当分区次数超过2*logN，N是输入数组的区间大小，则使用堆排序(Heapsort)
否则，使用快速排序。
 
 
有了Reflector这一神器，我们可以查看.NET中的ArraySort的具体实现:
 
 
Array.Sort这一方法在mscorlib这一程序集中，具体的实现方法有分别针对泛型和普通类型的SortedGenericArray和SortedObjectArray，里面的实现大同小异，我们以SortedGenericArray这个类来作为例子看:
 
 
 
 
首先要看的是Sort方法，其实现如下：
 
 
 
 
该方法中，首先判断运行的.NET对的版本，如果是4.5及以上版本，则用IntrospectiveSort算法，否则采用限定深度的快速排序算法DepthLimitedQuickSort。先看IntrospectiveSort：
 
 
 
 
该方法第一个元素为数组的最左边元素位置，第二个参数为最右边元素位置，第三个参数为2*log2N，继续看方法内部：
 
 
 
 
可以看到，当num<=16时，如果元素个数为1,2,3，则直接调用SwapIfGreaterWithItem进行排序了。否则直接调用InsertSort进行插入排序。
 
 
这里面也是一个循环，每循环一下depthLimit就减小1个，如果为0表示划分的次数超过了2logN，则直接调用基排序(HeapSort)，这里面的划分方法PickPivortAndPartitin的实现如下：
 
 
 
 
它其实是一个标准的三平均快速排序。可以看到在.NET 4.5中对Quick进行优化的部分主要是在元素个数比较少的时候采用选择插入，并且在递归深度超过2logN的时候，采用基排序。
 
 
下面再来看下在.NET 4.0及以下平台下排序DepthLimitedQuickSort方法的实现：
 
 
从名称中可以看出这是限定深度的快速排序，在第三个参数传进去的是0x20，也就是32。
 
 
 
 
可以看到，当划分的次数大于固定的32次的时候，采用了基排序，其他的部分是普通的快速排序。
 
 
六 总结
 
 
由于快速排序在排序算法中具有排序速度快，而且是就地排序等优点，使得在许多编程语言的内部元素排序实现中采用的就是快速排序，本问首先介绍了一般的快速排序，分析了快速排序的时间复杂度，然后就分析了对快速排序的几点改进，包括对小序列采用插入排序替代，三平均划分，三分区划分等改进方法。最后介绍了.NET不同版本下的对元素内部排序的实现。
 
 
快速排序很重要，希望本文对您了解快速排序有所帮助。
 

基本思想：
 
        选择一个基准元素,比如选择最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置，又称为轴位置，此位置的元素确定后不再参与排序，然后再用同样的方法递归地排序划分的两部分。
 
分析：
 
      快速排序是不稳定的排序。
 
　　快速排序的时间复杂度为O(nlogn)。
 
　　当n较大时使用快排比较好，当序列基本有序时用快排反而不好。
 
代码实现：
 
递归实现
 
    int[] quickSort(int arr[],int left,int right){
        if(Objects.isNull(arr)){
            return arr;
        }
        if(left<right){
            //获取排序轴索引,该索引本身不再参与排序
            int middle=findMiddlePartion(arr,left,right);
            //从左到中排序
            quickSort(arr,left,middle-1);
            //从中到右排序
            quickSort(arr,middle+1,right);
        }
        return arr;
    }

    //该算法实现 绝对优于多层while循环的那种实现
    int findMiddlePartion(int arr[],int left,int right){
        //以最右的数 为基准元素
        int baseMiddleNum=arr[right];
        //从最左位开始  记录替换索引
        int low=left-1;
        //遍历中不包含基准元素
        for(int i=left;i<right;i++){
            //比基准元素小的 从最左位开始放
            if(arr[i]<=baseMiddleNum){
                //记录最左位已替换的索引
                low++;
                if(i==low){
                    continue;
                }
                //交换
                int temp=arr[low];
                arr[low]=arr[i];
                arr[i]=temp;
            }
        }
        //基准元素放到轴位置
        if((low)+1!=right){
            int temp=arr[low+1];
            arr[low+1]=baseMiddleNum;
            arr[right]=temp;
        }
        //返回下一次遍历位置 以该位置为轴分别向两侧排序
        return low+1;
    }
 
非递归实现：
 
    int[] quickSortNonRecursive(int arr[],int left,int right){
        if(Objects.isNull(arr)){
            return arr;
        }
        //通过栈实现
        Stack<Integer> stack=new Stack<>();
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            int rightNew=stack.peek();
            stack.pop();
            int leftNew=stack.peek();
            stack.pop();
            //获取排序轴索引,该索引本身不再参与排序
            int middle=findMiddlePartion(arr,leftNew,rightNew);
            if(middle-1>leftNew){
                stack.push(left);
                stack.push(middle-1);
            }
            if(middle+1<rightNew){
                stack.push(middle+1);
                stack.push(rightNew);
            }
        }
        return arr;
    }
 
 

　　理论很丰满，实战很骨感，作为一个嫌弃自己的胖子，我对实战很是热衷，导致总是对理论知识不上心，做题的时候就蒙了。
 
　　比如有这样一道自考题：
 

 
 
　　
 
　　看完以后第一感觉就是翻书，因为觉得过了一遍书中知识点的情况下，做题的时候再仔细看看，然后推敲那些自己还没有掌握好的知识效果会更好，在这个过程中暴露了自己看书的一个很不好的习惯，就是知道把握全局，也知道要注重每个标题下边的初始知识介绍，但是总是莫名其妙地就一头扎进了书上的例题讲解中不能自拔，还傻傻地问自己为什么是这个样子，书上讲过吗？结果很是打脸，疑惑之处的解答基本上会在每个小标题下边那个“开门见山”的位置上，呵呵～～～在想以后是不是学习时候先看例题，再回去看书……
 
　　书中对快速排序是这样介绍的：它是交换排序的一种，实质上是对冒泡排序的一种改进。基本思想：在n个记录中取某一个记录的键值作为基准（通常取第一个记录的键值作为基准）通过一趟排序，将待排序的记录分为小于或是等于这个键值和大于这个键值的两个独立部分，这时一部分的记录键值均比另一部分记录键值要小，然后，对这两部分记录继续分别进行快速排序，以达到整个序列有序。
 

 
 
　　这道题的答案如下：
 
　　
 
　　我在做题的时候发现只会第一趟排序，第二趟不知从何下手了，其实就是看书的时候没留意上文阐述的基本思想，后来终于搞明白了。下面是自己根据这道题，以及解题过程中出现的小失误，总结的解题分析，相当于是对书中基本思想的扩写吧（以升序排列为例）：
 
　　1、很废话，若是要求升序排列，比较之后调换位置就把小的放在左边，降序排列同理；
 　　2、第一趟排序的时候默认以第一个数为基准；
 

 　　3、简言之，就是一来一去：挑选完基准数据后，要注意的是，不是跟和它挨着的那个数开始往后依次比较，而是将这个待排序序列末端的数据选做比较对象，从末端开始往回比较，遇到比它小的直接交换位置，比如上题中的默认首位基准数据265,首先和末位的438比较，可知438比它大，那么就和438前边的数据比较，发现076比它小，于是，265就和076交换位置，此时，265的位置发生了改变，比较方向就需要发生改变了，期初它的比较对象是从后往前，经过这次交换后，它的比较对象的选择顺序就要变成从前往后，此时和它比较的是301，比它大，二者交换位置，依照上述方法继续接下来的工作，得到了第一趟的排序结果。
 

 
 
　　4、注意一趟排序是由多次比较交换位置得到的，即看清一趟和一次。
 　　5、通过观察答案所展示的排序过程我们会发现，基准是用来作为子序列的划分界限的，很像是分块，划分后，它的左边都是比它小的，右边都是比它大的，第一趟排序的基准是第一个数，第二趟排序的基准有两个，分别是每个子序列（用[]括起来的部分）的第一个数，他们各自负责自己所在块的排序，排序方法同序号3所述。
 　　6、在得到最后的排序结果之前，我们会发现待排序序列都在[]里边，基准都在外边，就像图中标注的那样，上一趟待排序子序列中的第一个数据会成为下一趟排序的基准。
 

 
 
　　PS:上图中第四趟只有一个数据742是在[]中的了，我在做题的时候以为到第四趟就截止了，毕竟它只剩下一个待排序数字独立成为一个序列了，后来发现竟然还有第五趟，其实这不难理解，第五趟只是起到了一个确定作用，达到去除第四趟结果那个[]的作用。
 

 
 
　　站在个人角度而言，这篇博客，叙述的貌似是快速排序方法，其实算是对自己学习方法的一个反思吧：
 
　　（1）不要把全局观忘了，要注意看书的侧重点；
 
　　（2）切忌眼高手低，不要觉得自己曾经接触过相关知识就觉得自己掌握得很好，从而可以绕开理论知识了，有些实战之前，还是需要巩固下理论知识的。
 

 
 

 
 

 

概念及本文参考
 
快速排序 - 维基百科英文 
 快速排序 - 维基百科中文
 
具体思路及代码
 
快排的思路就是把数字分成两边，小的放左边，大的放右边，相等的要么都放左边要么都放右边。
 
找到第k大的元素就是：根据快排分区得到的主元下标比k大还是比k小，再对其中一边进行快排查找直到得到的主元下标等于k。
 
快排基本版
 
我这里是以最右边的元素为基准，从左往右找大于基准的数字和从右往左找小于或等于基准的数字并进行交换，直到左右两个的下标相遇（相等），就返回这个下标。需要O(n)的存储空间。
 
int partition1(int *arr, int left, int right) {
    int pivot = arr[right];
    int low = left, high = right - 1;
    while (low < high) {
        while (low < high && arr[low] <= pivot)
            ++low;
        while (high > low && arr[high] > pivot)
            --high;
        if (low < high)
            swap(&arr[low], &arr[high]);
    }
    // 把主元放进一个合适的地方并返回主元下标
    if (arr[high] > pivot) {
        swap(&arr[high], &arr[right]);
        return high;
    }
    else {
        swap(&arr[high + 1], &arr[right]);
        return high + 1;
    }
}
 
快排优化版
 
这个版本又叫原地(in-place)分区。暂时地把基准放在数字最后面，最后再交换回中间。空间复杂度O(logn)。
 
// 以主元为中心划分:左边<=右边>；返回主元下标
// 原地分区(in-place)算法
int partition(int *arr, int left, int right) {
    int pivot = arr[right]; // 取最后一个元素为主元
    int large_num_index = left; 

    // 找到第一个一个大于pivot值的元素下标
    while (arr[large_num_index] <= pivot && large_num_index < right)
        ++large_num_index;

    // 与large_num_index后第一个小于pivot的值进行交换
    for (int i = large_num_index + 1; i < right; i++)
        if (arr[i] < pivot)
            swap(&arr[i], &arr[large_num_index++]);

    // 把主元元素交换到中间位置并作为一个分隔的标志
    swap(&arr[right], &arr[large_num_index]);
    return large_num_index;
}
 
测试代码
 
对两种快排算法的测试
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

#define ARRAYSIZE 100    
#define MAX_NUM 65536
#define MIN_NUM -1
#define TRUE 1
#define FALSE 0

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
// 打印出数组
void print_array(int arr[], int num) {
    for (int i = 0; i < num; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// 递归快排
void quicksort(int *arr, int left, int right) {
    if (left < right) {
        int pivot_index = partition(arr, left, right);
        quicksort(arr, left, pivot_index - 1);
        quicksort(arr, pivot_index + 1, right);
    }
}

void quicksort1(int *arr, int left, int right) {
    if (left < right) {
        int pivot_index = partition1(arr, left, right);
        quicksort1(arr, left, pivot_index - 1);
        quicksort1(arr, pivot_index + 1, right);
    }
}

// 复制数组
void copy_array(int *copyarr, int *arr, int num) {
    for (int i = 0; i < num; i++)
        copyarr[i] = arr[i];
}

// 比较两个数组内容是否相同
int comp_array(int *arr, int *copyarr, int num) {
    for (int i = 0; i < num; i++)
        if (copyarr[i] != arr[i])
            return FALSE;
    return TRUE;
}

void quicksort_test() {
    srand((unsigned)time(NULL));
    int arr[ARRAYSIZE] = {0};
    int copyarr[ARRAYSIZE] = {0};
    for (int i = 0; i < ARRAYSIZE; i++)
        arr[i] = rand();
    copy_array(copyarr, arr, ARRAYSIZE);
    print_array(arr, ARRAYSIZE);

    quicksort(arr, 0, ARRAYSIZE - 1);
    quicksort1(copyarr, 0, ARRAYSIZE - 1);
    cout << endl;
    print_array(arr, ARRAYSIZE);
    print_array(copyarr, ARRAYSIZE);
    if (comp_array(copyarr, arr, ARRAYSIZE))
        cout << "Correct" << endl;
    else
        cout << "Error" << endl;
}

int main() {
    quicksort_test();
}
 
测试结果可知这两种快排得出的结果一致。
 
对查找第K大元素的测试
 

int find_kth_element(int *arr, int left, int right, int k) {
    if (left <= right) {
        int pivot_index = partition(arr, left, right);
        if (pivot_index == k)
            return arr[pivot_index];
        else if (pivot_index < k)
            return find_kth_element(arr, pivot_index + 1, right, k);
        else
            return find_kth_element(arr, left, pivot_index - 1, k);
    }
    return -1;
}

int find_kth_element1(int *arr, int left, int right, int k) {
    if (left <= right) {
        int pivot_index = partition1(arr, left, right);
        if (pivot_index == k)
            return arr[pivot_index];
        else if (pivot_index < k)
            return find_kth_element1(arr, pivot_index + 1, right, k);
        else
            return find_kth_element1(arr, left, pivot_index - 1, k);
    }
    return -1;
}

// 升序
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void find_kth_element_test() {
    srand((unsigned)time(NULL));
    int arr[ARRAYSIZE] = {0};
    int copyarr[ARRAYSIZE] = {0};
    int examarr[ARRAYSIZE] = {0};
    for (int i = 0; i < ARRAYSIZE; i++)
        arr[i] = rand();
    copy_array(copyarr, arr, ARRAYSIZE);
    copy_array(examarr, arr, ARRAYSIZE);
    print_array(arr, ARRAYSIZE);
    int k = ARRAYSIZE / 2;
    cout << find_kth_element(arr, 0, ARRAYSIZE - 1, k) << endl;
    cout << find_kth_element1(copyarr, 0, ARRAYSIZE - 1, k) << endl;
    // 用stdlib自带的qsort进行验证
    qsort(examarr, ARRAYSIZE, sizeof(int), compare);
    cout << examarr[k] << endl;
}

int main() {
    find_kth_element_test();
}
 
测试结果是三种方法得出的数字都是一致的~
 
记得去年也做过这道题，当时我还写了很久，嗯，现在用的时间也很久QAQ