排序的定义：
假设含有n个记录的序列为{$r_1$，$r_2$，…，$r_n$}，其相应的关键字分别为{$k_1$，$k_2$，…，$k_n$}，需确定1，2，……，n的一种排列$p_1$，$p_2$，……，$p_n$，使其相应的关键字满足$k_{p1}$≤$k_{p2}$≤······≤$k_{pn}$（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列{$r_{p1}$，$r_{p2}$，······，$r_{pn}$}，这样的操作就称为排序。

9.1-9.2 排序的基本概念与分类

我们在排序问题中，通常将数据元素称为记录。显然我们输入的是一个记录集合，输出的也是一个记录集合，所以说，可以将排序看成是线性表的一种操作。

排序的依据是关键字之间的大小关系，那么，对同一个记录集合，针对不同的关键字进行排序，可以得到不同序列。

这里关键字k可以是记录r的主关键字，也可以是次关键字，甚至是若干数据项的组合。

9.2.1 排序的稳定性

假设$k_i=k_y(1≤i≤n，1≤j≤n，i≠j)$，且在排序前的序列中$r_i$领先于$r_j$（即$i<j$）。如果排序后$r_i$仍领先于$r_j$，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中$r_j$领先$r_i$，则称所用的排序方法是不稳定的。

9.2.2 内排序与外排序

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为：内排序和外排序。

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。我们这里主要就介绍内排序的多种方法。

对于内排序来说，排序算法的性能主要是受3个方面影响：

1. 时间性能
   排序是数据处理中经常执行的一种操作，往往属于系统的核心部分，因此排序算法的时间开销是衡量其好坏的最重要的标志。在内排序中，主要进行两种操作：比较和移动。比较指关键字之间的比较，这是要做排序最起码的操作。移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改变记录的存储方式来予以避免（这个我们在讲解具体的算法时再谈）。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
2. 辅助空间
   评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。
3. 算法的复杂性
   注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。

根据排序过程中借助的主要操作，我们把内排序分为：插入排序、交换排序、选择排序和归并排序。

本章一共要讲解七种排序的算法，按照算法的复杂度分为两大类，冒泡排序、简单选择排序和直接插入排序属于简单算法，而希尔排序、堆排序、归并排序、快速排序属于改进算法。

9.2.3 排序用到的结构与函数

为了讲清楚排序算法的代码，我先提供一个用于排序用的顺序表结构，此结构也将用于之后我们要讲的所有排序算法。

#define MAXSIZE 10  /* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
    int r[MAXSIZE + 1];    /* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
    int length;            /* 用于记录顺序表的长度 */
}SqList;

另外，由于排序最最常用到的操作是数组两元素的交换，我们将它写成函数，在之后的讲解中会大量的用到。

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L, int i, int j)
{
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}

9.3 冒泡排序

9.3.1 最简单排序实现

冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。冒泡的实现在细节上可以有很多种变化，我们将分别就3种不同的冒泡实现代码，来讲解冒泡排序的思想。

/* 对顺序表L作交换排序（冒泡排序初级版） */
void BubbleSort0(SqList *L)
{
    int i, j;
    for (i = 1; i < L->length; i++)
    {
        for (j = i + 1; j <= L->length; j++)
        {
            if (L->r[i] > L->r[j])
            {
                swap(L, i, j);/* 交换L->r[i]与L->r[j]的值 */
            }
        }
    }
}

9.3.2 冒泡排序算法

我们来看看正宗的冒泡算法。

/* 对顺序表L作冒泡排序 */
void BubbleSort(SqList *L)
{
    int i, j;
    for (i = 1; i < L->length; i++)
    {
        for (j = L->length - 1; j >= i; j--)  /* 注意j是从后往前循环 */
        {
            if (L->r[j] > L->r[j + 1]) /* 若前者大于后者（注意这里与上一算法的差异）*/
            {
                swap(L, j, j + 1);/* 交换L->r[j]与L->r[j+1]的值 */
            }
        }
    }
}

9.3.3 冒泡排序优化

/* 对顺序表L作改进冒泡算法 */
void BubbleSort2(SqList *L)
{
    int i, j;
    Status flag = TRUE;            /* flag用来作为标记 */
    for (i = 1; i < L->length && flag; i++) /* 若flag为true说明有过数据交换，否则停止循环 */
    {
        flag = FALSE;                /* 初始为False */
        for (j = L->length - 1; j >= i; j--)
        {
            if (L->r[j] > L->r[j + 1])
            {
                swap(L, j, j + 1);    /* 交换L->r[j]与L->r[j+1]的值 */
                flag = TRUE;        /* 如果有数据交换，则flag为true */
            }
        }
    }
}

代码改动的关键就是在i变量的for循环中，增加了对flag是否为true的判断。

经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断。

9.3.4 冒泡排序复杂度分析

分析一下它的时间复杂度。当最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，根据最后改进的代码，可以推断出就是n-1次的比较，没有数据交换，时间复杂度为 O（n）。当最坏的情况，即待排序表是逆序的情况，此时需要比较$\sum_{i=2}^n(i-1)=1+2+3+…+（n-1）=\frac{n(n-1)}2$次，并作等数量级的记录移动。因此，时间复杂度为O（n²）。

9.4 简单选择排序

冒泡排序的思想就是不断地在交换，通过交换完成最终的排序，这和做股票短线频繁操作的人是类似的。我们可不可以像只有在时机非常明确到来时才出手的股票高手一样，也就是在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作呢？这就是选择排序法的初步思想。

选择排序的基本思想是每一趟在n-i+1（i=1,2,…,n-1）个记录中选取关键字最小的记录作为有序序列的第i个记录。我们这里先介绍的是简单选择排序法。

9.4.1 简单选择排序算法

简单选择排序法（Simple Selection Sort）就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之。

/* 对顺序表L作简单选择排序 */
void SelectSort(SqList *L)
{
    int i, j, min;
    for (i = 1; i < L->length; i++)
    {
        min = i;                        /* 将当前下标定义为最小值下标 */
        for (j = i + 1; j <= L->length; j++)/* 循环之后的数据 */
        {
            if (L->r[min] > L->r[j])    /* 如果有小于当前最小值的关键字 */
                min = j;                /* 将此关键字的下标赋值给min */
        }
        if (i != min)                        /* 若min不等于i，说明找到最小值，交换 */
            swap(L, i, min);                /* 交换L->r[i]与L->r[min]的值 */
    }
}

简单选择排序会先找到最小值的下标，然后交换。接着迭代循环。

9.4.2 简单选择排序复杂度分析

从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多，第i趟排序需要进行n-i次关键字的比较，此时需要比较$\sum_{i=1}^{n-1}(n-i)=n-1+n-2+…+1=\frac{n(n-1)}{2}$次。而对于交换次数而言，当最好的时候，交换为0次，最差的时候，也就初始降序时，交换次数为n-1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度依然为O（n²）。

应该说，尽管与冒泡排序同为O（n²），但简单选择排序的性能上还是要略优于冒泡排序。

9.5 直接插入排序

9.5.1 直接插入排序算法

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

/* 对顺序表L作直接插入排序 */
void InsertSort(SqList *L)
{
    int i, j;
    for (i = 2; i <= L->length; i++)
    {
        if (L->r[i] < L->r[i - 1]) /* 需将L->r[i]插入有序子表 */
        {
            L->r[0] = L->r[i]; /* L->r[0]一开始无数值，以待设置哨兵 */
            for (j = i - 1; L->r[j] > L->r[0]; j--)
                L->r[j + 1] = L->r[j]; /* 记录后移 */
            L->r[j + 1] = L->r[0]; /* 插入到正确位置 */
        }
    }
}

9.5.2 直接插入排序复杂度分析

我们来分析一下这个算法，从空间上来看，它只需要一个记录的辅助空间，因此关键是看它的时间复杂度。

当最好的情况，也就是要排序的表本身就是有序的，比如数列是{2，3，4，5，6}，那么我们比较次数，其实就是代码第7行每个L.r[i]与L.r[i-1]的比较，共比较了$n-1(\sum_{i=2}^{n}1)$次，由于每次都是L.r[i]>L.r[i-1]，因此没有移动的记录，时间复杂度为O(n)。

当最坏的情况，即待排序表是逆序的情况，比如{6，5，4，3，2}，此时需要比较$\sum_{i=2}^{n}(i)=2+3+…+n=\frac{(n+2)(n-1)}{2}$次，而记录的移动次数也达到最大值$\sum_{i=2}^{n}(i+1)=\frac{(n+4)(n-1)}{2}$次。

如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为$\frac{n^{2}}{4}$次。因此，我们得出直接插入排序法的时间复杂度为O(n²)。从这里也看出，同样的O(n²)时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。

9.6 希尔排序

9.6.1 希尔排序原理

因为直接插入排序在排序表本身有序的情况下，时间复杂度为O(n)。

如果让待排序的记录个数较少呢，我们就可以用直接插入排序很快完成排序工作。很容易想到的就是将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。

所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，像{2，1，3，6，4，7，5，8，9}这样可以称为基本有序了。但像{1，5，9，3，7.8，2，4，6}这样的9在第三位，2在倒数第三位就谈不上基本有序。

因此，我们需要采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

9.6.2 希尔排序算法

希尔排序算法代码如下。

/* 对顺序表L作希尔排序 */
void ShellSort(SqList *L)
{
    int i, j, k = 0;
    int increment = L->length;
    do
    {
        increment = increment / 3 + 1;/* 增量序列 */
        for (i = increment + 1; i <= L->length; i++)
        {
            if (L->r[i] < L->r[i - increment])
            {/*  需将L->r[i]插入有序增量子表 */
                L->r[0] = L->r[i]; /*  暂存在L->r[0] */
                for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment)
                    L->r[j + increment] = L->r[j]; /*  记录后移，查找插入位置 */
                L->r[j + increment] = L->r[0]; /*  插入 */
            }
        }
    }
    while (increment > 1);
}

9.6.3 希尔排序复杂度分析

通过这段代码的剖析，相信大家有些明白，希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。

这里“增量”的选取就非常关键了。我们在代码中第7行，是用increment=increment/3+1；的方式选取增量的，可究竟应该选取什么样的增量才是最好，目前还是一个数学难题，迄今为止还没有人找到一种最好的增量序列。不过大量的研究表明，当增量序列为$dlta[k]=2^{t-k+1}-1(0\leq k\leq t\leq [\log_{2}(n+1)] )$时，可以获得不错的效率，其时间复杂度为$O(n^{3/2})$，要好于直接排序的O(n²)。需要注意的是，增量序列的最后一个增量值必须等于1才行。另外由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。

不管怎么说，希尔排序算法的发明，使得我们终于突破了慢速排序的时代（超越了时间复杂度为O(n²)），之后，相应的更为高效的排序算法也就相继出现了。

9.7 堆排序

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（例如图9-7-2左图所示）；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（例如图9-7-2右图所示）。

这里需要注意从堆的定义可知，根结点一定是堆中所有结点最大（小）者。较大（小）的结点靠近根结点（但也不绝对，比如右图小顶堆中60、40均小于70，但它们并没有70靠近根结点）。

如果按照层序遍历的方式给结点从1开始编号，则结点之间满足如下关系：

这里为什么i要小于等于[n/2]呢？相信大家可能都忘记了二叉树的性质5，其实忘记也不奇怪，这个性质在我们讲完之后，就再也没有提到过它。可以说，这个性质仿佛就是在为堆准备的。性质5的第一条就说一棵完全二叉树，如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。那么对于有n个结点的二叉树而言，它的i值自然就是小于等于[n/2]了。性质5的第二、三条，也是在说明下标i与2i和2i+1的双亲子女关系。如果完全忘记的同学不妨去复习一下。

如果将图9-7-2的大顶堆和小顶堆用层序遍历存入数组，则一定满足上面的关系表达，如图9-7-3所示。

9.7.1 堆排序算法

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

相信大家有些明白堆排序的基本思想了，不过要实现它还需要解决两个问题：

1. 如何由一个无序序列构建成一个堆？
2. 如果在输出堆顶元素后，调整剩余元素成为一个新的堆？

要解释清楚它们，让我们来看代码。

/*  对顺序表L进行堆排序 */
void HeapSort(SqList *L)
{
    int i;
    for (i = L->length / 2; i > 0; i--) /*  把L中的r构建成一个大根堆 */
        HeapAdjust(L, i, L->length);

    for (i = L->length; i > 1; i--)
    {
        swap(L, 1, i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */
        HeapAdjust(L, 1, i - 1); /*  将L->r[1..i-1]重新调整为大根堆 */
    }
}

从代码中也可以看出，整个排序过程分为两个for循环。第一个循环要完成的就是将现在的待排序序列构建成一个大顶堆。第二个循环要完成的就是逐步将每个最大值的根结点与末尾元素交换，并且再调整其成为大顶堆。

现在我们来看关键的 HeapAdjust（堆调整）函数是如何实现的。

/* 已知L->r[s..m]中记录的关键字除L->r[s]之外均满足堆的定义， */
/* 本函数调整L->r[s]的关键字,使L->r[s..m]成为一个大顶堆 */
void HeapAdjust(SqList *L, int s, int m)
{
    int temp, j;
    temp = L->r[s];
    for (j = 2 * s; j <= m; j *= 2) /* 沿关键字较大的孩子结点向下筛选 */
    {
        if (j < m && L->r[j] < L->r[j + 1])
            ++j; /* j为关键字中较大的记录的下标 */
        if (temp >= L->r[j])
            break; /* rc应插入在位置s上 */
        L->r[s] = L->r[j];
        s = j;
    }
    L->r[s] = temp; /* 插入 */
}

HeapAdjust函数的作用其实就是构建初始堆。初始堆的构建如下：假设有n个结点，依次检查（n/2）到1的所有结点。假如序号为n/2的结点不是堆，则调整位置，将较大的元素调整到根结点（保证根结点比左右孩子都大）；假如n/2的结点已经是堆，则考虑下面序号为n/2-1的结点…直到最后序号为1的结点。此时，序号为1的结点就是最大的数了。

9.7.2 堆排序复杂度分析

堆排序的效率到底有多高呢？我们来分析一下。

它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。

在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O（n）。

在正式排序时，第i次取堆顶记录重建堆需要用O(㏒i)的时间（完全二叉树的某个结点到根结点的距离为$[\log_{2}i]+1$，并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(n㏒n)。

所以总体来说，堆排序的时间复杂度为O(n㏒n)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(n㏒n)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O（n²）的时间复杂度了。

空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。

另外，由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。

9.8 归并排序

9.8.1 归并排序算法

归并”一词的中文含义就是合并、并入的意思，而在数据结构中的定义是将两个或两个以上的有序表组合成一个新的有序表。

归并排序（Merging Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（[x]表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

好了，有了对归并排序的初步认识后，我们来看代码。

/* 对顺序表L作归并排序 */
void MergeSort(SqList *L)
{
    MSort(L->r, L->r, 1, L->length);
}

一句代码，别奇怪，它只是调用了另一个函数而已。为了与前面的排序算法统一，我们用了同样的参数定义SqList*L，由于我们要讲解的归并排序实现需要用到递归调用，因此我们外封装了一个函数。假设现在要对数组{50，10，90，30，70，40，80，60，20}进行排序，L.length=9，我现来看看MSort的实现。

/* 递归法 */
/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[], int TR1[], int s, int t)
{
    int m;
    int TR2[MAXSIZE + 1];
    if (s == t)
        TR1[s] = SR[s];
    else
    {
        m = (s + t) / 2;                /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
        MSort(SR, TR2, s, m);        /* 递归地将SR[s..m]归并为有序的TR2[s..m] */
        MSort(SR, TR2, m + 1, t);    /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
        Merge(TR2, TR1, s, m, t);    /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
    }
}

可以说，如果对递归函数的运行方式理解比较透的话，MSort 函数还是很好理解的。我们来看看整个数据变换示意图，如图9-8-6所示。

现在我们来看看Merge函数的代码是如何实现的。

/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[], int TR[], int i, int m, int n)
{
    int j, k, l;
    for (j = m + 1, k = i; i <= m && j <= n; k++)    /* 将SR中记录由小到大地并入TR */
    {
        if (SR[i] < SR[j])
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }
    if (i <= m)
    {
        for (l = 0; l <= m - i; l++)
            TR[k + l] = SR[i + l];        /* 将剩余的SR[i..m]复制到TR */
    }
    if (j <= n)
    {
        for (l = 0; l <= n - j; l++)
            TR[k + l] = SR[j + l];        /* 将剩余的SR[j..n]复制到TR */
    }
}

如图9-8-7，函数Merge的作用其实就是将SR数组的下标1和6比较，较小的归并到TR数组；然后SR的6和2比较，较小的归并到TR；然后SR的2和7比较，较小的归并到TR；…；最后SR的5和9比较，归并到TR，大功告成。

就这样，我们的归并排序就算是完成了一次排序工作，怎么样，和堆排序比，是不是要简单一些呢？

9.8.2 归并排序复杂度分析

我们来分析一下归并排序的时间复杂度，一趟归并需要将SR[1]~SR[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到TR1[1]~TR1[n]中，这需要将待排序序列中的所有记录扫描一遍，因此耗费O（n）时间，而由完全二叉树的深度可知，整个归并排序需要进行$[\log_{2}n]$次，因此，总的时间复杂度为$O（n㏒n）$，而且这是归并排序算法中最好、最坏、平均的时间性能。

由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为$\log_{2}n$的栈空间，因此空间复杂度为$O（n+㏒n）$。

另外，对代码进行仔细研究，发现Merge函数中有if(SR[i]<SR[j])语句，这就说明它需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。也就是说，归并排序是一种比较占用内存，但却效率高且稳定的算法。

9.8.3 非递归实现归并排序

我们常说，“没有最好，只有更好。”归并排序大量引用了递归，尽管在代码上比较清晰，容易理解，但这会造成时间和空间上的性能损耗。我们排序追求的就是效率，有没有可能将递归转化成迭代呢？结论当然是可以的，而且改动之后，性能上进一步提高了，来看代码。

/* 对顺序表L作归并非递归排序 */
void MergeSort2(SqList *L)
{
    int* TR = (int*)malloc(L->length * sizeof(int));/* 申请额外空间 */
    int k = 1;
    while (k < L->length)
    {
        MergePass(L->r, TR, k, L->length);
        k = 2 * k;/* 子序列长度加倍 */
        MergePass(TR, L->r, k, L->length);
        k = 2 * k;/* 子序列长度加倍 */
    }
}

从代码中，我们能够感受到，非递归的迭代做法更加直截了当，从最小的序列开始归并直至完成。不需要像归并的递归算法一样，需要先拆分递归，再归并退出递归。

现在我们来看MergePass代码是如何实现的。

/* 非递归法 */
/* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
void MergePass(int SR[], int TR[], int s, int n)
{
    int i = 1;
    int j;
    while (i <= n - 2 * s + 1)
    {/* 两两归并 */
        Merge(SR, TR, i, i + s - 1, i + 2 * s - 1);
        i = i + 2 * s;
    }
    if (i < n - s + 1) /* 归并最后两个序列 */
        Merge(SR, TR, i, i + s - 1, n);
    else /* 若最后只剩下单个子序列 */
        for (j = i; j <= n; j++)
            TR[j] = SR[j];
}

非递归的迭代方法，避免了递归时深度为$\log_{2}n$的栈空间，空间只是用到申请归并临时用的TR数组，因此空间复杂度为O（n），并且避免递归也在时间性能上有一定的提升，应该说，使用归并排序时，尽量考虑用非递归方法。

9.9 快速排序

快速排序算法最早由图灵奖获得者Tony Hoare设计出来的，他在形式化方法理论以及ALGOL60编程语言的发明中都有卓越的贡献，是上世纪最伟大的计算机科学家之一。而这快速排序算法只是他众多贡献中的一个小发明而已。

更牛的是，我们现在要学习的这个快速排序算法，被列为20世纪十大算法之一。

希尔排序相当于直接插入排序的升级，它们同属于插入排序类，堆排序相当于简单选择排序的升级，它们同属于选择排序类。而快速排序其实就是我们前面认为最慢的冒泡排序的升级，它们都属于交换排序类。即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。

9.9.1 快速排序算法

快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

从字面上感觉不出它的好处来。假设现在要对数组{50，10，90，30，70，40，80，60，20}进行排序。我们通过代码的讲解来学习快速排序的精妙。我们来看代码。

/* 对顺序表L作快速排序 */
void QuickSort(SqList *L)
{
    QSort(L, 1, L->length);
}

又是一句代码，和归并排序一样，由于需要递归调用，因此我们外封装了一个函数。现在我们来看QSort的实现。

/* 对顺序表L中的子序列L->r[low..high]作快速排序 */
void QSort(SqList *L, int low, int high)
{
    int pivot;
    if (low < high)
    {
        pivot = Partition(L, low, high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */
        QSort(L, low, pivot - 1);        /*  对低子表递归排序 */
        QSort(L, pivot + 1, high);        /*  对高子表递归排序 */
    }
}

从这里，你应该能理解前面代码“QSort（L，1，L->length）；”中1和L->length代码的意思了，它就是当前待排序的序列最小下标值low和最大下标值high。

这一段代码的核心是“pivot=Partition（L，low,high）；”在执行它之前，L.r的数组值为{50，10，90，30，70，40，80，60，20}。Partition函数要做的，就是先选取当中的一个关键字，比如选择第一个关键字50，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值比它大，我们将这样的关键字称为枢轴（pivot）。

在经过Partition（L，1，9）的执行之后，数组变成{20，10，40，30，50,70，80，60，90}，并返回值5给pivot，数字5表明50放置在数组下标为5的位置。此时，计算机把原来的数组变成了两个位于50左和右小数组{20，10，40，30}和{70，80，60，90}，而后的递归调用“QSort（L，1，5-1）；"和“QSort（L，5+1，9）；"语句，其实就是在对{20，10，40，30}和{70，80，60，90}分别进行同样的Partition操作，直到顺序全部正确为止。

到了这里，应该说理解起来还不算困难。下面我们就来看看快速排序最关键的Partition 函数实现。

/* 交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置 */
/* 此时在它之前(后)的记录均不大(小)于它。 */
int Partition(SqList *L, int low, int high)
{
    int pivotkey;

    pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */
    while (low < high) /*  从表的两端交替地向中间扫描 */
    {
        while (low < high&&L->r[high] >= pivotkey)
            high--;
        swap(L, low, high);/* 将比枢轴记录小的记录交换到低端 */
        while (low < high&&L->r[low] <= pivotkey)
            low++;
        swap(L, low, high);/* 将比枢轴记录大的记录交换到高端 */
    }
    return low; /* 返回枢轴所在位置 */
}

Partition函数，其实就是将选取的pivotkey不断交换，将比它小的换到它的左边，比它大的换到它的右边，它也在交换中不断更改自己的位置，直到完全满足这个要求为止。

9.9.2 快速排序复杂度分析

我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。如果是{50，10，90，30，70，40，80，60，20}在快速排序过程中的递归过程。由于我们的第一个关键字是50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。

在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为$[\log_{2}n]+1$（[x]表示不大于x的最大整数），即仅需递归$\log_{2}n$次，需要时间为T（n）的话，第一次Partiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，我们就有了下面的不等式推断。
$T(n)\leq 2T(n/2)+n , T(1)=0$
$T(n)\leq 2(2T(n/4)+n/2) +n=4T(n/4)+2n$
$T(n)\leq 4(2T(n/8)+n/4) +2n=8T(n/8)+3n$
$……$
$T(n)\leq nT(1)+(\log_{2}n)×n=O(n\log n)$

也就是说，在最优的情况下，快速排序算法的时间复杂度为$O(n\log n)$。

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为$\sum_{i=1}^{n-1}(n-i)=n-1+n-2+…+1=\frac{n(n-1)}{2}$，最终其时间复杂度为O(n²)。

平均的情况，设枢轴的关键字应该在第k的位置（1≤k≤n），那么：
$$T(n)=\frac{1}{n}\sum_{k=1}^{n}（T(k-1)+T(n-k)）+n=\frac{2}{n}\sum_{k=1}^{n}T(k)+n$$

由数学归纳法可证明，其数量级为$O(n\log n)$。

就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为$\log_{2}n$，其空间复杂度也就为$O(\log n)$，最坏情况，需要进行n-1递归调用，其空间复杂度为$O(n)$，平均情况，空间复杂度也为$O(\log n)$。

可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

9.9.3 快速排序优化

刚才讲的快速排序还是有不少可以改进的地方，我们来看一些优化的方案。

1. 优化选取枢轴
   三数取中（median-of-three）法。即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。
2. 优化不必要的交换
   采用替换而不是交换的方式进行操作
3. 优化小数组时的排序方案
   我们增加了一个判断，当high-low不大于某个常数时（有资料认为7比较合适，也有认为50更合理，实际应用可适当调整），就用直接插入排序，这样就能保证最大化地利用两种排序的优势来完成排序工作。
4. 优化递归操作
   对QSort实施尾递归优化。

/* 改进后快速排序******************************** */

/* 快速排序优化算法 */
int Partition1(SqList *L, int low, int high)
{
    int pivotkey;

    int m = low + (high - low) / 2; /* 计算数组中间的元素的下标 */
    if (L->r[low] > L->r[high])
        swap(L, low, high);    /* 交换左端与右端数据，保证左端较小 */
    if (L->r[m] > L->r[high])
        swap(L, high, m);        /* 交换中间与右端数据，保证中间较小 */
    if (L->r[m] > L->r[low])
        swap(L, m, low);        /* 交换中间与左端数据，保证左端较小 */

    pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */
    L->r[0] = pivotkey;  /* 将枢轴关键字备份到L->r[0] */
    while (low < high) /*  从表的两端交替地向中间扫描 */
    {
        while (low < high&&L->r[high] >= pivotkey)
            high--;
        L->r[low] = L->r[high];
        while (low < high&&L->r[low] <= pivotkey)
            low++;
        L->r[high] = L->r[low];
    }
    L->r[low] = L->r[0];
    return low; /* 返回枢轴所在位置 */
}

void QSort1(SqList *L, int low, int high)
{
    int pivot;
    if ((high - low) > MAX_LENGTH_INSERT_SORT)
    {
        while (low < high)
        {
            pivot = Partition1(L, low, high); /*  将L->r[low..high]一分为二，算出枢轴值pivot */
            QSort1(L, low, pivot - 1);        /*  对低子表递归排序 */
            /* QSort(L,pivot+1,high);        /*  对高子表递归排序 */
            low = pivot + 1;    /* 尾递归 */
        }
    }
    else
        InsertSort(L);
}

/* 对顺序表L作快速排序 */
void QuickSort1(SqList *L)
{
    QSort1(L, 1, L->length);
}

9.10 箱排序和基数排序

9.10.1 箱排序(又称桶排序)

基本思想：设置若干个箱子，依次扫描待排序的记录R[0],R[1],…,R[n-1]，把关键字等于k的记录全部都装入第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来。

简单来说就是：将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序。

public static void sort(int[] arr){
    //最大最小值
    int max = arr[0];
    int min = arr[0];
    int length = arr.length;

    for(int i=1; i<length; i++) {
        if(arr[i] > max) {
            max = arr[i];
        } else if(arr[i] < min) {
            min = arr[i];
        }
    }

    //最大值和最小值的差
    int diff = max - min;

    //桶列表
    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
    for(int i = 0; i < length; i++){
        bucketList.add(new ArrayList<>());
    }

    //每个桶的存数区间
    float section = (float) diff / (float) (length - 1);

    //数据入桶
    for(int i = 0; i < length; i++){
        //当前数除以区间得出存放桶的位置 减1后得出桶的下标
        int num = (int) (arr[i] / section) - 1;
        if(num < 0){
            num = 0;
        }
        bucketList.get(num).add(arr[i]);
    }

    //桶内排序
    for(int i = 0; i < bucketList.size(); i++){
        //jdk的排序速度当然信得过
        Collections.sort(bucketList.get(i));
    }

    //写入原数组
    int index = 0;
    for(ArrayList<Integer> arrayList : bucketList){
        for(int value : arrayList){
            arr[index] = value;
            index++;
        }
    }
}

9.10.2 基数排序

9.10.2.1 原理和例子

基数排序是对桶排序的改进和推广。

基数排序一种非比较型整数排序算法，其原理是将数据按位数切割成不同的数字，然后按每个位数分别比较。

【例】已知关键字序列{278,109,063,930,589,184,505,269,008,083},写出基数排序(升序)的排序过程。

初始状态：
P->278->109->063->930->589->184->505->269->008->083

第一趟分配，按个位从小到大装箱后如下：
P->930->063->083->184->505->278->008->109->589->269

第二趟分配，按十位从小到大装箱后如下：
P->505->008->109->930->063->269->278->083->184->589

第三趟分配，按百位从小到大装箱后如下：
P->008->063->083->109->184->269->278->505->589->930

排序完成。

9.10.2.2 代码

public static void sort(int[] arr){
    int length = arr.length;

    //最大值
    int max = arr[0];
    for(int i = 0;i < length;i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }
    //当前排序位置
    int location = 1;

    //桶列表
    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();

    //长度为10 装入余数0-9的数据
    for(int i = 0; i < 10; i++){
        bucketList.add(new ArrayList());
    }

    while(true)
    {
        //判断是否排完
        int dd = (int)Math.pow(10，(location - 1));
        if(max < dd){
            break;
        }

        //数据入桶
        for(int i = 0; i < length; i++)
        {
            //计算余数 放入相应的桶
            int number = ((arr[i] / dd) % 10);
            bucketList.get(number).add(arr[i]);
        }

        //写回数组
        int nn = 0;
        for (int i=0;i<10;i++){
            int size = bucketList.get(i).size();
            for(int ii = 0;ii < size;ii ++){
                arr[nn++] = bucketList.get(i).get(ii);
            }
            bucketList.get(i).clear();
        }
        location++;
    }
}

9.10.2.3 时间复杂度和空间复杂度

基数排序算法是稳定的。

时间复杂度是$O(d*(rd+n))$,其中$rd$是基数，$d$是关键字的位数，$n$是元素个数。

空间复杂度(辅助空间)为$O(n+rd)$。

9.11 总结回顾

本章内容只是在讲排序，我们需要对已经提到的各个排序算法进行对比来总结回顾。

首先我们讲了排序的定义，并提到了排序的稳定性，排序稳定对于某些特殊需求来说是至关重要的，因此在排序算法中，我们需要关注此算法的稳定性如何。

我们根据将排序记录是否全部被放置在内存中，将排序分为内排序与外排序两种，外排序需要在内外存之间多次交换数据才能进行。我们本章主要讲的是内排序的算法。

根据排序过程中借助的主要操作，我们将内排序分为：插入排序、交换排序、选择排序和归并排序四类。之后介绍的7种排序法，就分别是各种分类的代表算法。

事实上，目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。因此我们就来从多个角度来剖析一下提到的各种排序的长与短。

我们将7种算法的各种指标进行对比，如表9-10-1所示。

从算法的简单性来看，我们将7种算法分为两类：

• 简单算法：冒泡、简单选择、直接插入。
• 改进算法：希尔、堆、归并、快速。

从平均情况来看，显然最后3种改进算法要胜过希尔排序，并远远胜过前3种简单算法。

从最好情况看，反而冒泡和直接插入排序要更胜一筹，也就是说，如果你的待排序序列总是基本有序，反而不应该考虑4种复杂的改进算法。

从最坏情况看，堆排序与归并排序又强过快速排序以及其他简单排序。

从这三组时间复杂度的数据对比中，我们可以得出这样一个认识。堆排序和归并排序就像两个参加奥数考试的优等生，心理素质强，发挥稳定。而快速排序像是很情绪化的天才，心情好时表现极佳，碰到较糟糕环境会变得差强人意。但是他们如果都来比赛计算个位数的加减法，它们反而算不过成绩极普通的冒泡和直接插入。

从空间复杂度来说，归并排序强调要马跑得快，就得给马吃个饱。快速排序也有相应的空间要求，反而堆排序等却都是少量索取，大量付出，对空间要求是O(1)。如果执行算法的软件所处的环境非常在乎内存使用量的多少时，选择归并排序和快速排序就不是一个较好的决策了。

从稳定性来看，归并排序独占鳌头，我们前面也说过，对于非常在乎排序稳定性的应用中，归并排序是个好算法。

从待排序记录的个数上来说，待排序的个数n越小，采用简单排序方法越合适。反之，n越大，采用改进排序方法越合适。这也就是我们为什么对快速排序优化时，增加了一个阀值，低于阀值时换作直接插入排序的原因。

从表9-10-1的数据中，似乎简单选择排序在3种简单排序中性能最差，其实也不完全是，比如，如果记录的关键字本身信息量比较大（例如，关键字都是数十位的数字），此时表明其占用存储空间很大，这样移动记录所花费的时间也就越多，我们给出3种简单排序算法的移动次数比较，如表9-10-2所示。

你会发现，此时简单选择排序就变得非常有优势，原因也就在于，它是通过大量比较后选择明确记录进行移动，有的放矢。因此对于数据量不是很大而记录的关键字信息量较大的排序要求，简单排序算法是占优的。另外，记录的关键字信息量大小对那四个改进算法影响不大。

总之，从综合各项指标来说，经过优化的快速排序是性能最好的排序算法，但是不同的场合我们也应该考虑使用不同的算法来应对它。