排序

排序

大多数情况下，我们的排序代码只会通过两个方法操作数据：less() 方法对元素进行比较， exch() 方法将元素交换位置。

运行时间：

排序成本模型：在研究排序算法时，我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数。

额外的内存使用：

排序算法的额外内存开销和运行时间是同等重要的。排序算法可以分为两类：除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法，以及需要额外内存空间来存储另一份数组副本的其他排序算法。

1. 初级排序算法

1.1 选择排序

一种最简单的排序算法是这样的：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。——【不断将区间内的最小元素调整顺序】

这样交换的总次数是N。所以算法的时间效率取决于比较的次数。

//less():元素比较；exch():交换元素
public void chooseSort(Comparable[] a){
    int N = a.length;
    for(int i = 0 ; i < a.length;i++){
        int min = i ;
        for(int j = i+1;j<N;j++){
            if(less(a[j],a[min])) min = j;
            exch(a,i,min);
        }
    }
}

1.2 插入排序

适合部分有序，小规模数组

向数组左侧进行交换，即往左边交换

在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。

与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。

和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

public void insertSort(Comparable[] a){
    int N = a.length;
    for(int i = 0 ; i < a.length;i++){
        for(int j = i ; j > 0 && less(a[j],a[j-1]);j--){
            exec(a,j,j-1);
        }
    }
}

对于 1 到 N-1 之间的每一个 i，将 a[i] 与 a[0] 到 a[i-1] 中比它小的所有元素依次有序地交换。在索引 i 由左向右变化的过程中，它左侧的元素总是有序的，所以当 i 到达数组的右端时排序就完成了。

下面是几种典型的部分有序的数组：

数组中每个元素距离它的最终位置都不远；

一个有序的大数组接一个小数组；

数组中只有几个元素的位置不正确。插入排序对这样的数组很有效，而选择排序则不然。

事实上，当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快。

1.3 希尔排序

当对一个大的且混乱无序的数组进行排序时，插入排序的效率非常差，而希尔排序可以改善这种情况。

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。换句话说，一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个数组（见图 2.1.2）。在进行排序时，如果 h 很大，我们就能将元素移动到很远的地方，为实现更小的 h 有序创造方便。用这种方式，对于任意以 1 结尾的 h 序列，我们都能够将数组排序。这就是希尔排序。算法 2.3 的实现使用了序列 1/2（ $排序 - 图1$ ），从 N/3 开始递减至 1。我们把这个序列称为递增序列。

排序 - 图2

序列中的数字每隔h单位组成一组，在组内进行排序，之后减小h的组，减小组的大小，当h=1时，即为插入排序，可以得到有序数组。

如在a[9]中，若h=4，

a[0],a[4],a[8]，a[1],[5]，a[2],a[6]，a[3],a[7]，a[4]分为5组，5组组内使用插入排序进行排序

减小h的大小，h=2，同上进行组内插入排序，这样会不断得到部分有序的数组。

排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序

而插入排序在仅有少量倒置的情况下（有序部分多）效率会非常高，当h=1时，即为插入排序。

//这里h的选择规则和h的减小问题值得商榷
public void xierSort(Comparable[] a){
    int N = a.length;
    int h = 1;
    while(h<N/3) h = h*3+1;
    while(h>=1){
        for(int i = h ; i < N ;i++){
            for(int j = i ; j >= h && less(a[j],a[j-h]);j--){
                exec(a,j,j-h)
            }
        }
        h = h/3;
    }
}

六分钟彻底弄懂希尔排序，简单易懂

2. 归并排序

在本节中我们所讨论的算法都基于归并这个简单的操作，即将两个有序的数组归并成一个更大的有序数组。

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。你将会看到，归并排序最吸引人的性质是它能够保证将任意长度为 N 的数组排序所需时间和 $排序 - 图3$ 成正比；它的主要缺点则是它所需的额外空间和 N 成正比。以下是简单的归并排序：

排序 - 图4

将序列中带排序数字分为若干组，每个数字分为一组
将若干组两两合并，保证合并后的组是有序的
重复第二步操作直到只剩下一组，排序完成

2.1 原地归并的抽象方法

方法merge(a,le,mid,ri)会将子数组a[le,mid]和a[mid+1,ri]归并成一个有序的数组，并将结果存放在a[le,ri]中。下列方法中，将涉及到的元素复制到一个辅助数组中。

【原子操作】相当于将两个有序数组合并成一个有序数组。

public static void merge(Comparable[] a, int le, int mid, int ri){
    int i = le , j = ri;
    for(int k = le;k<=ri;k++){
        aux[k] = a[k];//aux辅助数组
    }
    for(int k = le ; k <=ri;k++){
        if(i>mid) a[k] = aux[j++]; //左半边用尽,取右
        else if(j>hi) a[k] = aux[i++]; //右尽取左
        else if(less(aux[j],aux[i])) a[k] = aux[j++];//右小
        else a[k] = aux[i++];//左小
    }
}

2.2 自顶向下的归并排序

运用分治思想，不断划分缩小区间。

递归实现的归并排序是算法设计中分治思想的典型应用。我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。

public class meger{
    private Comparable[] aux; //辅助数组
    public void sort(Comparable[] a){
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    private void sort(Comparable[] a , int lo , int hi){
        if(hi<=lo) return ;
        int mid = lo + (hi-lo)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        merge(a,lo,mid,hi); //见上面的meger函数
    }
}

要对子数组 a[1o..hi] 进行排序，先将它分为 a[1o..mid] 和 a[mid+1..hi] 两部分，分别通过递归调用将它们单独排序，最后将有序的子数组归并为最终的排序结果。

排序 - 图5

排序 - 图6

从这段轨迹可以看到，sort() 方法的作用其实在于安排多次 merge() 方法调用的正确顺序。

排序 - 图7

测试数组是否已经有序：

我们可以添加一个判断条件，如果 a[mid] 小于等于 a[mid+1]，我们就认为数组已经是有序的并跳过 merge() 方法。这个改动不影响排序的递归调用，但是任意有序的子数组算法的运行时间就变为线性的了。

2.3 自底向上的归并排序

首先我们进行的是两两归并（把每个元素想象成一个大小为 1 的数组），然后是四四归并（将两个大小为 2 的数组归并成一个有 4 个元素的数组），然后是八八的归并，一直下去。

public class MergeBU{
    private Comparable[] aux;
    public void sort(Comparable[] a){
        int N = a.length;
        aux = new Comparable[N];
        for(int sz = 1; sz < N ; sz = sz+sz){ //sz子数组大小
            for(int lo = 0 ; lo < N-sz; lo+=sz+sz){//lo:子数组索引，区间大小sz，所以lo<N-sz
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1),N-1);
            }
        }
    }
}

排序 - 图8

自底向上的归并排序比较适合用链表组织的数据。想象一下将链表先按大小为 1 的子链表进行排序，然后是大小为 2 的子链表，然后是大小为 4 的子链表等。这种方法只需要重新组织链表链接就能将链表原地排序（不需要创建任何新的链表结点）。

3. 快速排序

快速排序的内循环比大多数排序算法都要短小，这意味着它无论是在理论上还是在实际中都要更快。它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。

3.1 基本算法

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的位置取决于数组的内容。快速排序的大致过程如图所示。

归并：先不断划分区间，让每个小区间有序，之后合并，使得大区间有序

快速：先让整个大区间呈现“局部有序”，之后在对每个大区间的小区间进行排序

排序 - 图9

public class Quick{
    public void sort(Comparable[] a){
        sort(a,0,a.length-1);
    }
    public void sort(Comparable[] a , int lo , int hi){
        if(hi <= lo) return;
        int j = partition(a,lo,hi);
        sort(a,lo,j-1);
        sort(a,j+1,hi);
    }
}

该方法的关键在于切分，这个过程使得数组满足下面三个条件：

对于某个 j，a[j] 已经排定；
a[lo] 到 a[j-1] 中的所有元素都不大于 a[j]；
a[j+1] 到 a[hi] 中的所有元素都不小于 a[j]。

private static int partition(Comparable[] a, int lo, int hi){
    int i = lo , j = hi+1; //左右扫描指针，hi+1是为了之后的--j
    Comparable v = a[lo]; //切分元素
    while(true){
        //扫描左右，检查扫描是否结束并交换元素
        while(less(a[++i],v)) if(i==hi) break;
        while(less(v,a[--j])) if(j==lo) break;
        if(i>=j) break;
        exch(a,i,j);
    }
    exch(a,lo,j);  //将v=a[j]放入正确的位置
    return j; //a[lo...j-1]<=a[j]<=a[j+1...hi]达成
}

当指针 i 和 j 相遇时主循环退出。在循环中，a[i] 小于 v 时我们增大 i，a[j] 大于 v 时我们减小 j，然后交换 a[i] 和 a[j] 来保证 i 左侧的元素都不大于 v，j 右侧的元素都不小于 v。

要完成这个实现，需要实现切分方法。一般策略是先随意地取 a[lo] 作为切分元素，即那个将会被排定的元素，然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换它们的位置。如此继续，我们就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，我们只需要将切分元素 a[lo] 和左子数组最右侧的元素（a[j]）交换然后返回 j 即可。

排序 - 图10

【问题】

为什么当两个指针相遇时，仅需要将切分元素a[lo]和左子数组最右侧的元素a[j]进行交换即可？

while(less(a[++i],v)) if(i==hi) break;
while(less(v,a[--j])) if(j==lo) break;
if(i>=j) break;

1、左子数组的最右侧元素交换？

按照快排的思想，左子数组都小于切分元素，在此处交换不会破坏排序。

2、最右侧元素a[j]而不是a[i]？

当指针相遇时交换 a[lo] 和 a[j]，切分结束（这样切分值就留在 a[j] 中了）。

3.2 算法改进

三取样切分

改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好，但代价是需要计算中位数。人们发现将取样大小设为 3 并用大小居中的元素切分的效果最好。我们还可以将取样元素放在数组末尾作为“哨兵”来去掉 partition() 中的数组边界测试。

熵最优的排序

实际应用中经常会出现含有大量重复元素的数组，例如我们可能需要将大量人员资料按照生日排序，或是按照性别区分开来。在这些情况下，我们实现的快速排序的性能尚可，但还有巨大的改进空间。例如，一个元素全部重复的子数组就不需要继续排序了，但我们的算法还会继续将它切分为更小的数组。在有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现，这就有很大的改进潜力，将当前实现的线性对数级的性能提高到线性级别。

一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。这种切分实现起来比我们目前使用的二分法更复杂，人们为解决它想出了许多不同的办法。这也是 E. W. Dijkstra 的荷兰国旗问题引发的一道经典的编程练习，因为这就好像用三种可能的主键值将数组排序一样，这三种主键值对应着荷兰国旗上的三种颜色。

Dijkstra 的解法如“三向切分的快速排序”中极为简洁的切分代码所示。它从左到右遍历数组一次，维护一个指针 lt 使得 a[lo..lt-1] 中的元素都小于 v，一个指针 gt 使得 a[gt+1..hi] 中的元素都大于 v，一个指针 i 使得 a[lt..i-1] 中的元素都等于 v，a[i..gt] 中的元素都还未确定，如图 2.3.4 所示。一开始 i 和 lo 相等，我们使用 Comparable 接口（而非 less()）对 a[i] 进行三向比较来直接处理以下情况：

a[i] 小于 v，将 a[lt] 和 a[i] 交换，将 lt 和 i 加一；
a[i] 大于 v，将 a[gt] 和 a[i] 交换，将 gt 减一；
a[i] 等于 v，将 i 加一。

public class Quick3way{
    private void sort(Comparable[] a , int lo , int hi ){
        if(hi<=lo) return ;
        int lt = lo , i = lo + 1,gt = hi ;
        Comparable v = a[lo];
        while(i<=gt){
            int cmp = a[i].comparaTo(v){
                if(cmp<0) exch(a,i++,lt++);
                else if(cmp > 0) exch(a,i++,gt--);
                else i++;
            }
        }
        sort(a,lo,lt-1);
        sort(a,gt+1,hi);
    }
}

将大于v的丢到最右边（gt指针），将小于v的丢到最左边（lt指针），等于v的因为通过不断交换不等于v的元素使得其聚集在一起。

排序 - 图11

【对于存在大量重复元素的数组，这种方法效率较高】

4. 优先队列

许多应用程序都需要处理有序的元素，但不一定要求它们全部有序，或是不一定要一次就将它们排序。很多情况下我们会收集一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素。

优先队列最重要的操作是删除最大元素和插入元素

约定的API：

MaxPQ()：创建一个优先队列
MaxPQ(int max)：创建一个初始容量为max的优先队列
MaxPQ(key[] a)：用a[]中元素创建一个优先队列
void insert(key v)：向优先队列中插入一个元素
key max()：返回最大元素
key delMax()：删除并返回最大元素
boolean isEmpty()：返回队列是否为空
int size()：返回优先队列中的元素个数

优先队列的【调用示例】：

输入 N 个字符串，每个字符串都对应着一个整数，你的任务就是从中找出最大的（或是最小的）M 个整数（及其关联的字符串）。——【Top M】

示例	时间	空间
排序算法的用例	$排序 - 图12$	$排序 - 图13$
调用初级实现的优先队列	$排序 - 图14$	$排序 - 图15$
调用基于堆实现的优先队列	$排序 - 图16$	$排序 - 图17$

4.1 初级实现

数组实现（无序）

数组实现（有序）

链表表示法

4.2 堆的定义

数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素，以此类推。如果我们将所有元素画成一棵二叉树，将每个较大元素和两个较小的元素用边连接就可以很容易看出这种结构。

定义：当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。

相应地，在堆有序的二叉树中，每个结点都小于等于它的父结点（如果有的话）。从任意结点向上，我们都能得到一列非递减的元素；从任意结点向下，我们都能得到一列非递增的元素。

二叉堆表示法：

如果我们用指针来表示堆有序的二叉树，那么每个元素都需要三个指针来找到它的上下结点（父结点和两个子结点各需要一个）。但如图所示，如果我们使用完全二叉树，表达就会变得特别方便。要画出这样一棵完全二叉树，可以先定下根结点，然后一层一层地由上向下、从左至右，在每个结点的下方连接两个更小的结点，直至将 N 个结点全部连接完毕。完全二叉树只用数组而不需要指针就可以表示。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置 1，它的子结点在位置 2 和 3，而子结点的子结点则分别在位置 4、5、6 和 7，以此类推。

排序 - 图18

定义：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置）。

在一个堆中，位置 k 的结点的父结点的位置为 k/2，而它的两个子结点的位置则分别为 2k 和 2k+1。

4.3 堆的算法

我们使用长度为N+1的数组pq[]来标识一个大小为N的堆，不适用pq[0]，堆元素放在pq[1]至pq[N]中。

堆的有序化

堆的操作会首先进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。我们称这个过程叫做堆的有序化。

有序化过程中的两种情况

当某个结点的优先级上升（或是在堆底加入一个新的元素）时，我们需要由下至上恢复堆的顺序。

当某个结点的优先级下降（例如，将根结点替换为一个较小的元素）时，我们需要由上至下恢复堆的顺序。

由下至上的堆有序化（上浮）——insert

如果堆的有序状态因为某个结点变得比它的父结点更大而被打破，那么我们就需要通过==交换它和它的父结点来修复堆。交换后，这个结点比它的两个子结点都大（一个是曾经的父结点，另一个比它更小，因为它是曾经父结点的子结点），但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍地用同样的办法恢复秩序，将这个结点不断向上移动直到我们遇到了一个更大的父结点==。只要记住位置 k 的结点的父结点的位置是 $排序 - 图19$ ，这个过程实现起来很简单。swim() 方法中的循环可以保证只有位置 k上的结点大于它的父结点时堆的有序状态才会被打破。因此只要该结点不再大于它的父结点，堆的有序状态就恢复了。至于方法名，当一个结点太大的时候它需要浮（swim）到堆的更高层。

private void swim(int k ){
    while(k>1 && less(k/2),k){
        exch(k/2,k);
        k = k/2;
    }
}

由上至下的堆有序化（下沉）——delete

如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被打破了，那么我们可以通过==将它和它的两个子结点中的较大者交换来恢复堆。交换可能会在子结点处继续打破堆的有序状态，因此我们需要不断地用相同的方式将其修复，将结点向下移动直到它的子结点都比它更小或是到达了堆的底部==。由位置为 k 的结点的子结点位于 $排序 - 图20$ 和 $排序 - 图21$ 可以直接得到对应的代码。当一个结点太小的时候它需要沉（sink）到堆的更低层。

private void sink(int k ){
    while(2*k<=N){
        int j = 2*k;
        if(j<N && less(j,j+1)) j++; //将索引调整到子节点中较大的节点
        if(!less(k,j)) break; //如果k节点大于子节点，则跳出
        exch(k,j);//k节点小于子节点，交换节点位置
        k = j;
    }
}

基于堆的优先队列

在这里部分，我们需要记住是我们使用pq[]来存储完成二叉树，从pq[]的索引可以重建树的关系。

public class MaxPQ<key extends Comparable<key>>{
    private key[] pq; //基于堆的完全二叉树
    private int N = 0; //存储与pq[1...N]中，pq[0]没有使用

    public MaxPQ(int maxN){
        pq = (key[]) new Comparable[maxN+1];
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    public void insert(key v){
        pq[++N] = v;
        swim(N); //这里使用索引代替需要上浮的数
    }
    public key delMax(){
        key max = pq[1]; //从根节点得到最大元素
        exch(1,N--); //将其和最后一个节点交换
        pq[N+1] = null; //防止对象游离
        sink(1);     //恢复堆的有序性
        return max;
    }
}

多叉堆

基于用数组表示的完全三叉树构造堆并修改相应的代码并不困难。对于数组中 1 至 N 的 N 个元素，位置 k 的结点大于等于位于 $排序 - 图22$ 、 $排序 - 图23$ 和$ 3k+1$ 的结点，小于等于位于 $排序 - 图24$ %2F3%7D%5Cright%5Crfloor#card=math&code=%5Cleft%5Clfloor%7B%28k%2B1%29%2F3%7D%5Cright%5Crfloor) 的结点。甚至对于给定的 d，将其修改为任意的 d 叉树也并不困难。我们需要在树高（ $排序 - 图25$ ）和在每个结点的 d 个子结点找到最大者的代价之间找到折中，这取决于实现的细节以及不同操作的预期相对频繁程度。

索引优先队列、多向合并问题（待补充）

4.4 堆排序

堆排序过程：

1、构造一个大顶堆，取堆顶数字（也就是最大值）

2、再将剩下的数字构建一个大顶堆，取堆顶数字

3、重复以上操作，直到取完堆中的数字，最终得到一个从大到小排列的序列

堆的构造

法1：从左至右遍历数组，用swim()保证扫描指针左侧的所有元素已经是一颗堆有序的完全数，就像连续向优先队列中插入元素一样。

法2：从右至左使用sink()函数构造子堆。数组的每个位置都已经是一个子堆的根结点了，sink() 对于这些子堆也适用。如果一个结点的两个子结点都已经是堆了，那么在该结点上调用 sink() 可以将它们变成一个堆。这个过程会递归地建立起堆的秩序。

开始时我们只需要扫描数组中的一半元素，因为我们可以跳过大小为 1 的子堆。最后我们在位置 1 上调用 sink() 方法，扫描结束。在排序的第一阶段，堆的构造方法和我们的想象有所不同，因为我们的目标是构造一个堆有序的数组并使最大元素位于数组的开头（次大的元素在附近）而非构造函数结束的末尾。

【问题】：为什么只需要扫描一般元素(下列代码的N/2)？

【解答】：堆排序中我们可以认为数组是一颗完全二叉树，那么数组最后一位元素的父节点一定位于 $排序 - 图26$ 处，即该堆的最后一个父节点在 $排序 - 图27$ 处，这样就跳过了大小为1的堆。

public void sort(Comparable[] a){
    int N  = a.length;
    //构造大顶堆
    for(int i = N/2 ; i >= 0 ;i--){
        sink(a,k,N);
    }
    //下沉排序
    while(N>1){
        exch(1,N--);
        sink(a,1,N);
    }
}

排序 - 图28

下沉排序

堆排序的主要工作都是在第二阶段完成的。这里我们将堆中的最大元素删除，然后放入堆缩小后数组中空出的位置。这个过程和选择排序有些类似（按照降序而非升序取出所有元素），但所需的比较要少得多，因为堆提供了一种从未排序部分找到最大元素的有效方法。

如果使用额外数组存储即可得到升序序列。

【问】堆排序与冒泡排序有什么区别？

【答】堆提供了一种快速找到最大值的方法

4.5 问题

【问】为什么在堆的表示中不使用 a[0] ？

【答】这么做可以稍稍简化计算。实现从 0 开始的堆并不困难，a[0] 的子结点是 a[1] 和 a[2]，a[1] 的子结点是 a[3] 和 a[4]，a[2] 的子结点是 a[5] 和 a[6]，以此类推。但大多数程序员更喜欢我们的简单方法。另外，将 a[0] 的值用作哨兵（作为 a[1] 的父结点）在某些堆的应用中很有用。

5. 应用

排序 - 图29

快速排序是最快的通用排序算法。

中位数的寻找