排序：
假设含有n个记录的序列为{r1,r2,……,rn}，其相应的关键字分别为{k1,k2…….,kn}，需确定1，2，……，n的一种排列 p1,p2,……,pn，使其相应的关键字满足 kp1≤kp2≤……≤kpn。(非递减或非递增)关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,……,rpn}，这样的操作就称为排序。

一、排序的基本概念与分类

注意我们在排序问题中，通常将数据元素称为记录。显然我们输入的是一个记录集合，输出的也是一个记录集合，所以说，可以将排序看成是线性表的一种操作。
排序的依据是关键字之间的大小关系，那么，对同一个记录集合，针对不同的关键字进行排序，可以得到不同序列。
这里关键字ki可以是记录r的主关键字，也可以是次关键字，甚至是若干数据项的组合。比如我们某些大学为了选拔在主科上更优秀的学生，要求对所有学生的所有科目总分降序排名，并且在同样总分的情况下将语数外总分做降序排名。这就是对总分和语数外总分两个次关键字的组合排序。如图所示，对于组合排序的问题当然可以先排序总分，若总分相等的情况下，再排序语数外总分，但这是比较土的办法。我们还可以应用一个技巧来实现一次排序即完成组合排序问题，例如，把总分与语数外都当成字符串首尾连接在一起(注意语数外总分如果位数不够三位，需要在前面补零)，很容易可以得到令狐冲的“753229”要小于张无忌的“753236"，于是张无忌就排在了令狐冲的前面。


从这个例子也可看出，多个关键字的排序最终都可以转化为单个关键字的排序，因此，我们这里主要讨论的是单个关键字的排序。

1.1 排序的稳定性

由于排序不仅是针对主关键字，那么对于次关键字，因为待排序的记录序列中可能存在两个或两个以上的关键字相等的记录，排序结果可能会存在不唯一的情况，我们给出了稳定与不稳定排序的定义。

假设 ki=kj(1≤i≤n,1≤j≤n,i≠j)，且在排序前的序列中ri领先于rj(即 i<j)。如果排序后ri仍领先于rj，则称所用的排序方法是稳定的;反之，若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。

如图所示，经过对总分的降序排序后，总分高的排在前列。此时对于令狐冲和张无忌而言，未排序时是令狐冲在前，那么它们总分排序后，分数相等的令狐冲依然应该在前，这样才算是稳定的排序如果他们二者颠倒了，则此排序是不稳定的了。只要有一组关键字实例发生类似情况,就可认为此排序方法是不稳定的。排序算法是否稳定的，要通过分析后才能得出。

1.2 内排序与外排序

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

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

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

1. 时间性能
   排序是数据处理中经常执行的一种操作，往往属于系统的核心部分，因此排序算法的时间开销是衡量其好坏的最重要的标志。在内排序中，主要进行两种操作:比较和移动。比较指关键字之间的比较，这是要做排序最起码的操作。移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改变记录的存储方式来予以避免(这个我们在讲解具体的算法时再谈)。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
2. 辅助空间
   评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。
3. 算法的复杂性
   注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。
   根据排序过程中借助的主要操作，我们把内排序分为:插入排序、交换排序、选择排序和归并排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的更多并不是为了去在现实中编程排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。

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

1.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;
}

二、冒泡排序

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

2.1 最简单排序实现

/* 对顺序表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,1,5,8,3,7,4,6,2}，当i=1时，9与1交换后，在第一位置的1与后面的关键字比较都小，因此它就是最小值。当i=2时，第二位置先后由9换成5，换成3，换成2，完成了第二小的数字交换。后面的数字变换类似，不再介绍。

它应该算是最最容易写出的排序代码了，不过这个简单易懂的代码，却是有缺陷的。观察后发现，在排序好1和2的位置后，对其余关键字的排序没有什么帮助(数字3反而还被换到了最后一位)。也就是说，这个算法的效率是非常低的。

2.2 冒泡排序算法

我们来看看正宗的冒泡算法，有没有什么改进的地方。

    public void bubbleSort(int[] arr) {
        for(int i= arr.length-1; i > 0; i--) {
            for(int j = 0; j < i; j++) {
                if(arr[j]>arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
    }

/* 对顺序表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); /* 交换j和j+1下标所对应的数据值 */
			}
		}
	}
}

依然假设我们待排序的关键字序列是 {9,1,5,8,3,7,4,6,2}，当i=1时，变量j由8反向循环到 1，逐个比较，将较小值交换到前面，直到最后找到最小值放置在了第1的位置。如图所示，当i=1、j=8 时，我们发现 6>2，因此交换了它们的位置，j=7时，4>2，所以交换……直到j=2 时，因为 1<2，所以不交换。j=1 时，9>1，交换，**最终得到最小值1放置第一的位置**。事实上，**在不断循环的过程中，除了将关键字1放到第一的位置，我们还将关键字 2从第九位置提到了第三的位置，显然这一算法比前面的要有进步**，在上十万条数据的排序过程中，这种差异会体现出来。图中**较小的数字如同气泡般慢慢浮到上面，因此就将此算法命名为冒泡算法**。
当i=2 时，变量j由8反向循环到2，逐个比较，在将关键字2交换到第二位置的同时，也将关键字4和3有所提升。

2.3 冒泡排序优化

这样的冒泡程序是否还可以优化呢?答案是肯定的。试想一下，如果我们待排序的序列是 {2,1,3,4,5,6,7,8,9}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当i-1时，交换了2和1，此时序列已经有序，但是算法仍然不依不饶地将 i=2 到9以及每个循环中的j循环都执行了一遍，尽管并没有交换数据但是之后的大量比较还是大大地多余了，如图所示。

当i=2时，我们已经对9与8，8与7，……，3与2作了比较，没有任何数据交换，这就说明此序列已经有序，不需要再继续后面的循环判断工作了。为了实现这个想法，我们需要改进一下代码，增加一个标记变量flag 来实现这一算法的改进。

public void bubbleSortWithFlag(int[] arr) {
        int cycleCount = 0;
        for(int i= arr.length-1; i > 0; i--) {
            boolean flag = false;
            for(int j = 0; j < i; j++) {
                if(arr[j]>arr[j+1]) {
                    swap(arr, j, j+1);
                    flag = true;  // 记录当前轮次是否发生交换
                }
                cycleCount++;
            }
            if(!flag) {
                break;  // 如果当前轮次没有发生交换，说明已经有序，直接退出外层循环
            }

        }
        System.out.println("循环次数:"+cycleCount);
    }

代码改动的关键就是在i变量的 for 循环中，增加了对 flag 是否为 tue 的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断。

/*对顺序表工作改进冒泡算法 */
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 */
			}
		}
        if(!flag)
            break;// 此轮“冒泡”未交换任何元素，直接跳出
	}
}

2.4 冒泡排序复杂度分析

分析一下它的时间复杂度。当最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，根据最后改进的代码，可以推断出就是n-1次的比较，没有数据交换，时间复杂度为 O(n)。当最坏的情况，即待排序表是逆序的情况，此时需要比较

次，并作等数量级的记录移动，因此总的时间复杂度为O(n^2)。

三、简单选择排序

爱炒股票短线的人，总是喜欢不断的买进卖出，想通过价差来实现盈利。但通常这种频繁操作的人，即使失误不多，也会因为操作的手续费和印花税过高而获利很少。还有一种做股票的人，他们很少出手，只是在不断的观察和判断，等到时机一到，果断买进或卖出。他们因为冷静和沉着，以及交易的次数少，而最终收益颇丰。
冒泡排序的思想就是不断地在交换，通过交换完成最终的排序，这和做股票短线频繁操作的人是类似的。我们可不可以像只有在时机非常明确到来时才出手的股票高手一样，也就是在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作呢?这就是选择排序法的初步思想。
选择排序的基本思想是每一趟在 n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录。我们这里先介绍的是简单选择排序法。

3.1 简单选择排序算法

简单选择排序法是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<i<n)记录交换之。代码如下：

public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 初始化最小值
            int minIndex = i;
            // 寻找后续数组中的最小值,如果比当前最小值小，则更改最小值的索引
            for(int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 与当前起始位置交换
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

/* 对顺序表L作简单选择排序 */
void SelectSort(SqList *L)
{
	int i,j,min;
	fo(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;  /* 将当前关键字的下标赋值给imin */
		}
		if(i!=min)   /* 若min不等于i，说明找到最小值，交换 */
			swap(L,i,min);  /* 交换L->r[i]与L->r[min]的值 */
	}
}

代码应该说不难理解，针对待排序的关键字序列是 {9,1,5,8,3,7,4,6,2}，对i从1循环到 8。当 i=1 时，L.r[i]=9 ，min 开始是 1，然后与 j=2 到9 比较 L.r[min]与 L.r[j]的大小，因为 j=2 时最小，所以 min=2。最终交换了 L.r[2]与 L.r[1]的值。如图所示，注意，这里比较了8次，却只交换数据操作一次。

当 i=2 时，L.r[i]=9，min开始是2，经过比较后，min=9，交换 L.r[min]与 L.r[i]的值。如图所示，这样就找到了第二位置的关键字。

当 i=3 时，L.r[i]=5，min 开始是 3，经过比较后，min=5，交换 L.r[min]与 L.r[i]的值。如图所示。

之后的数据比较和交换完全雷同，最多经过8次交换，就可完成排序工作。

3.2 简单选择排序算法复杂度分析

从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，这样也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多，第i趟排序需要进行n-i.次关键字的比较,此时需要比较

次。而对于交换次数而言，当最好的时候，交换为0次，最差的时候，也就初始降序时，交换次数为n一1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度依然为 O(n^2)
应该说，尽管与冒泡排序同为 O(n^2)，但简单选择排序的性能上还是要略优于冒泡排序。

四、直接插入排序

扑克牌是我们几乎每个人都可能玩过的游戏。最基本的扑克玩法都是一边摸牌一边理牌。假如我们拿到了这样一手牌，如图所示。啊，似乎是同花顺呀，别急，我们得理一理顺序才知道是否是真的同花顺。请问，如果是你，应该如何理牌呢?

应该说，哪怕你是第一次玩扑克牌，只要认识这些数字，理牌的方法都是不用教的。将3和4移动到5的左侧，再将2移动到最左侧，顺序就算是理好了。这里，我们的理牌方法，就是直接插入排序法。

4.1 直接插入排序算法

直接插入排序(StraightInsertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
顾名思义，从名称上也可以知道它是一种插入排序的方法。我们来看直接插入排序法的代码。

public void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int base = arr[i], j=i-1;
            while(j>=0 && arr[j]>base){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=base;
        }
    }

/* 对顺序表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];  /* 设置哨兵 */
			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];  /* 插到正确的位置 */
		}
	}
}

1. 程序开始运行，此时我们传入的SqList参数的值为 length=6,r[6]=(0,5,3,4,6,2}，其中 r[0]=0将用于后面起到哨兵的作用。
2. 第 4~13 行就是排序的主循环。i从2开始的意思是我们假设 r[1]=5 已经放好位置，后面的牌其实就是插入到它的左侧还是右侧的问题。
3. 第6行，此时 i=2，L.r[i]=3比 L.r[i-1]=5 要小，因此执行第 8 ~ 11 行的操作。第8行，我们将 L.r[0]赋值为 L.r[i]=3 的目的是为了起到第9~10 行的循环终止的判断依据。如图9-5-2所示。图中下方的虚线箭头，就是第10行，L.r[j-1]=L.r[j]的过程，将5右移一位。
   
4. 此时，第10行就是在移动完成后，空出了空位，然后第11行 L.r[j+1]=L.r[0]，将哨兵的3赋值给 j=0 时的 L.r[j+1]，也就是说，将扑克牌 3放置到 L.r[1]的位置，如图所示。
   
5. 继续循环，第6行，因为此时 i=3，L.r[i]=4比 L.r[i-1]=5 要小，因此执行第8~11行的操作，将5再右移一位，将4放置到当前5所在位置，如图所示。
   
6. 再次循环，此时 i=4。因为 L.r[i]=6比 Lr[i-1]=5 要大，于是第 8~11 行代码不执行，此时前三张牌的位置没有变化，如图所示。
   
7. 再次循环，此时 i=5，因为 L.r[i]=2比 L.r[i-1]=6 要小，因此执行第 8~11 行的操作。由于6、5、4、3都比2小，它们都将右移一位，将2放置到当前 3所在位置。如图所示。此时我们的排序也就完成了。
   

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

当最好的情况，也就是要排序的表本身就是有序的，比如纸牌拿到后就是 {2,3,4,5,6}，那么我们比较次数，其实就是代码第6行每个 L.r[i]与 L.r[i-1]的比较,共比较了
次，由于每次都是 L.r[i]>L.r[i-1]，因此没有移动的记录，时间复杂度为 O(n)。
当最坏的情况，即待排序表是逆序的情况，比如 {6,5,4,3,2}，此时需要比较
次，而记录的移动次数也达到最大值次。
如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为 n^2/4次。因此，我们得出直接插入排序法的时间复杂度为O(n^2)。从这里也看出，同样的O(n^2)时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。

五、希尔排序

给大家出一道智力题。请问“Ⅶ”是什么?
嗯，很好，它是罗马数字的7。现在我们要给它加上一笔，让它变成8(Ⅷ)，应该是非常简单，只需要在右侧加一竖线即可。
现在我请大家试着对罗马数字9，也就是“Ⅸ”增加一笔，把它变成6，应该怎么做?
(几分钟后)
我已经听不少声音说，“这怎么可能!”可为什么一定要用常规方法呢?
我这里有3 种另类的方法可以实现它。
方法一:观察发现“X”其实可以看作是一个正放一个倒置两个因此我们，给“IX”中间加一条水平线，上下颠倒，然后遮住下面部分，也就是说，我们所谓的加上一笔就是遮住一部分，于是就得到“V”，如图所示。

前面加一个“S”，此时构成一个英文单词“SIX"，这就等于得方法二:在“IX”到一个6了。哈哈，我听到下面一片哗然，我刚有没有说一定要是“Ⅵ”呀，我只说把它变成6而已，至于是罗马数字还是英文单词，我可没有限制。显然，你们的思维受到了我前面举例的“Ⅶ”转变为“Ⅷ”的影响，如图所示。

方法三:在“IX”后面加一个“6”，得到“1X6”，其结果当然是数字6了。大家笑了，因为这个想法实在是过分，把字母“1”当成了数字1，字母“X”看成了乘号。可谁又规定说这是不可以的呢?只要没违反规则，得到6即可，如图所示。

智力题的答案介绍完了。大家会发现，看似解决不了的问题，还真不一定就没有办法，也许只是暂时没想到罢了。
我们都能理解，优秀排序算法的首要条件就是速”。于是人们想了许许多多的办法，目的就是为了提高排序的速度。而在很长的时间里，众人发现尽管各种排序算法花样繁多(比如前面我们提到的三种不同的排序算法)，但时间复杂度都是O(n^2)，似乎没法超越了25。此时，计算机学术界充斥着“排序算法不可能突破O(n^2)”的声音。就像刚才大家做智力题的感觉一样，“不可能”成了主流。
终于有一天，当一位科学家发布超越了O(n^2)新排序算法后，紧接着就出现了好几种可以超越O(n^2)的排序算法，并把内排序算法的时间复杂度提升到了O(nlogn)。“不可能超越 O(n^2)”彻底成为了历史。
从这里也告诉我们，做任何事，你解决不了时，想一想“Nothing is impossibke!”，虽然有点唯心，但这样的思维方式会让你更加深入地思考解决方案，而不是匆忙的放弃。

5.1 希尔排序

现在，我要讲解的算法叫希尔排序(Shell Sort)。希尔排序是 D.L.Shell 于1959年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是O(n^2)的，希尔排序算法是突破这个时间复杂度的第一批算法之一。
我们前一节讲的直接插入排序，应该说，它的效率在某些时候是很高的，比如，我们的记录本身就是基本有序的，我们只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入很高效。还有就是记录数比较少时，直接插入的优势也比较明显。可问题在于，两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。
不过别急，有条件当然是好，条件不存在，我们创造条件也是可以去做的。于是科学家希尔研究出了一种排序方法，对直接插入排序改进后可以增加效率。

如何让待排序的记录个数较少呢?很容易想到的就是将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。
此时一定有同学开始疑惑了。这不对呀，比如我们现在有序列是 {9,1,5,8,3,7,4,6,2}，现在将它分成三组，{9,1,5}，{8,3,7}，{4,6,2}，哪怕将它们各自排序排好了，变成 {1,5,9}，{3,7,8}，{2,4,6}，再合并它们成 {1,5,9,3,7,8,2,4,6}，此时，这个序列还是杂乱无序，谈不上基本有序，要排序还是重来一遍直接插入有序，这样做有用吗?需要强调一下，所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，像 {2,1,3,6,4,7,5,8,9}这样可以称为基本有序了。但像 {1,5,9,3,7,8,2,4,6}这样的9在第三位，2在倒数第三位就谈不上基本有序。
问题其实也就在这里，我们分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展。而如上面这样分完组后就各自排序的方法达不到我们的要求。因此，我们需要采取跳跃分割的策略:将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

5.2 希尔排序算法

好了，为了能够真正弄明白希尔排序的算法，我们还是老办法——模拟计算机在执行算法时的步骤，还研究算法到底是如何进行排序的。
希尔排序算法代码如下。

/* 对顺序表L作希尔排序 */
void ShellSort(SqList *L)
{
	int i,j;
	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];  /* 暂存于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);
}

1. 程序开始运行，此时我们传入的SqList参数的值为 ength=9,r[10]={0,9,1,5,8,3,7,4,6,2}。这就是我们需要等待排序的序列，如图所示。
2. 第4行，变量increment就是那个“增量”，我们初始值让它等于待排序的记录数。
3. 第5~19 行是一个 do 循环，它提终止条件是 increment 不大于1时，其实也就是增量为1时就停止循环了。
4. 第7行，这一句很关键，但也是难以理解的地方，我们后面还要谈到它，先放一放。这里执行完成后，increment=9/3+1=4。
5. 第8~17行是一个for循环，i从 4+1=5 开始到9 结束。
6. 第10行，判断 L.r[i]与 L.r[i-increment]大小，L.r[5]=3小于 L.r[i-increment]=L.r[1]=9，满足条件，第12行，将 L.r[5]=3 暂存入 L.r[0]。第13~14 行的循环只是为了将 L.r[1]=9 的值赋给 L.r[5]，由于循环的增量是 j-=increment，其实它就循环了一次，此时 j=-3。第15行，再将 L.r[0]=3 赋值给 L.r[j+increment]=L.r[-3+4]=L.r[1]=3。如图所示，事实上，这段代码就干了一件事，就是将第5位的3和第1位的9交换了位置。
7. 循环继续，i=6，L.r[6]=7>L.r[i-increment]=L.r[2]=1，因此不交换两者数据如图 所示。
8. 循环继续，i=7，L.r[7]=4<L.r[i-increment]=L.r[3]=5，交换两者数据。如图所示。
9. 循环继续，i=8，L.r[8]=6<L.r[i-increment]=L.r[4]=8，交换两者数据。如图所示。
10. 循环继续，1-9，Lr[9]=2<L,r[i-increment]=L.r[5]=9，交换两者数据。注意第13~14 行是循环，此时还要继续比较 L.r[5]与 L.r[1]的大小，因为 2<3所以还要交换 L.r[5]与 L.r[1]的数据，如图所示。
    最终第一轮循环后，数组的排序结果为图所示。细心的同学会发现，我们的数字 1、2等小数字已经在前两位，而8、9等大数字已经在后两位，也就是说，通过这样的排序，我们已经让整个序列基本有序了。这其实就是希尔排序的精华所在，它将关键字较小的记录，不是一步一步地往前挪动，而是跳跃式地往前移，从而使得每次完成一轮循环后，整个序列就朝着有序坚实地迈进一步。
11. 我们继续，在完成一轮 do 循环后，此时由于 increment=4>1 因此我们需要继续 do 循环。第7行得到 increment=4/3+1=2。第8~17行for 循环,i从 2+1=3开始到9结束。当 i=3、4时，不用交换，当 i=5 时，需要交换数据，如图所示。
12. 此后，i=6,7,8,9 均不用交换，如图。
13. 再次完成一轮do循环，increment=2>1，再次do循环，第7行得到 increment=2/3+1=1，此时这就是最后一轮 do 循环了。尽管第 8~17行for循环，i从 1+1=2开始到9结束，但由于当前序列已经基本有序，可交换数据的情况大为减少，效率其实很高。如图所示，图中箭头连线为需要交换的关键字。

最终完成排序过程，如图所示。

5.3 希尔排序时间复杂度分析

通过这段代码的剖析，相信大家有些明白，希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。
这里“增量"的选取就非常关键了。我们在代码中第7行，是用 increment=increment/3+1;的方式选取增量的，可究竟应该选取什么样的增量才是最好，目前还是一个数学难题，迄今为止还没有人找到一种最好的增量序列。不过大量的研究表明，当增量序列为 dlta[k]=2^(t-k+1)-1(0≤k≤t≤[log2(n+1)」)时，可以获得不错的效率，其时间复杂度为0(n^3/2)，要好于直接排序的O(n^2)。需要注意的是，增量序列的最后一个增量值必须等于1才行。另外由于记录是跳跃式的移动，希尔排序并不是种稳定的排序算法。
不管怎么说，希尔排序算法的发明，使得我们终于突破了慢速排序的时代(超越了时间复杂度为 O(n^2))，之后，相应的更为高效的排序算法也就相继出现了。

六、堆排序

我们前面讲到简单选择排序，它在待排序的n个记录中选择一个最小的记录需要比较 n-1 次。本来这也可以理解，查找第一个数据需要比较这么多次是正常的，否则如何知道它是最小的记录。
可惜的是，这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较中，有许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数较多。
如果可以做到每次在选择到最小记录的同时，并根据比较结果对其他记录做出相应的调整，那样排序的总体效率就会非常高了。而堆排序(Heap Sort)，就是对简单选择排序进行的一种改进，这种改进的效果是非常明显的。堆排序算法是Foyd和Williams 在 1964 年共同发明的，同时，他们发明了“堆”这样的数据结构。
回忆一下我们小时候，特别是男同学，基本都玩过叠罗汉的恶作剧。通常都是先把某个要整的人按倒在地，然后大家就一拥而上扑了上去……后果?后果当然就是一笑了之，一个恶作剧而已。不过在西班牙的加泰罗尼亚地区，他们将叠罗汉视为了正儿八经的民族体育活动，可以想象当时场面的壮观。
叠罗汉运动是把人堆在一起，而我们这里要介绍的“堆”结构相当于把数字符号堆成一个塔型的结构。当然，这绝不是简单的堆砌。大家看图所示，能够找到什么规律吗?
很明显，我们可以发现它们都是二叉树，如果观察仔细些，还能看出它们都是完全二叉树。左图中根结点是所有元素中最大的，右图的根结点是所有元素中最小的。再细看看，发现左图每个结点都比它的左右孩子要大，右图每个结点都比它的左右孩子要小。这就是我们要讲的堆结构。
堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆(例如左图所示);或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆(例如右图所示)。
这里需要注意从堆的定义可知，根结点一定是堆中所有结点最大(小)者。较大(小)的结点靠近根结点(但也不绝对，比如右图小顶堆中60、40均小于70，但它们并没有 70 靠近根结点)。
如果按照层序遍历的方式给结点从1开始编号，则结点之间满足如下关系:

这里为什么i要小于等于 Ln/2」呢?相信大家可能都忘记了二叉树的性质 5^26，其实忘记也不奇怪，这个性质在我们讲完之后，就再也没有提到过它。可以说，这个性质仿佛就是在为堆准备的。性质5的第一条就说一棵完全二叉树，如果 i=1，则结点i是二叉树的根，无双亲;如果i>1，则其双亲是结点 Li/2」。那么对于有n个结点的二叉树而言，它的i值自然就是小于等于 Ln/2」了。性质5的第二、三条，也是在说明下标i与2i和 2i+1的双亲子女关系。如果完全忘记的同学不妨去复习一下。
如果将图的大顶堆和小顶堆用层序遍历存入数组，则一定满足上面的关系表达，如下图所示。

6.1 堆排序的算法

堆排序(Heap Sort) 就是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的 n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。
例如图所示，图①是一个大顶堆，90为最大值，将90与20(末尾元素)互换，如图②所示，此时90就成了整个堆序列的最后一个元素，将20经过调整，使得除 90以外的结点继续满足大顶堆定义(所有结点都大于等于其子孩子)，见图③，然后再考虑将30与80互换…


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

1. 如何由一个无序序列构建成一个堆?
2. 如果在输出堆顶元素后，调整剩余元素成为一个新的堆?
   要解释清楚它们，让我们来看代码。

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

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

从代码中也可以看出，整个排序过程分为两个for循环。第一个循环要完成的就是将现在的待排序序列构建成一个大顶堆。第二个循环要完成的就是逐步将每个最大值的根结点与末尾元素交换，并且再调整其成为大顶堆。
假设我们要排序的序列是 {50,10,90,30,70,40,80,60,20} ，那么 L.length=9，第一个for 循环，代码第4行，i是从 L9/2=4开始，4→3→2→1的变量变化。为什么不是从1到9或者从9到1，而是从4到1呢?其实我们看了图就明白了，它们都有什么规律?它们都是有孩子的结点。注意灰色结点的下标编号就是1、2、3、4。

我们所谓的将待排序的序列构建成为一个大顶堆，其实就是从下往上、从右到左，将每个非终端结点(非叶结点)当作根结点，将其和其子树调整成大顶堆。i的4→3→2→1的变量变化，其实也就是30，90，10、50的结点调整过程。
既然已经弄清楚i的变化是在调整哪些元素了，现在我们来看关键的 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;    /* 插入 */
}

1. 函数被第一次调用时，s=4，m=9，传入的SqList参数的值为 length=9,r[10]={0,50,10,90,30,70,40,80,60,20}.
2. 第4行，将 L.r[s]=L.r[4]=30 赋值给 temp，如图所示。
   
3. 第5~13行，循环遍历其结点的孩子。这里j变量为什么是从 2*s 开始呢?又为什么是 j*=2 递增呢?原因还是二叉树的性质5，因为我们这棵是完全二叉树，当前结点序号是s，其左孩子的序号一定是2s，右孩子的序号一定是2s+1，它们的孩子当然也是以2的位数序号增加，因此j变量才是这样循环。
4. 第7~8行，此时 j=2*4=8，j<m说明它不是最后一个结点，如果 L.r[j]<L.r[j+1]，则说明左孩子小于右孩子。我们的目的是要找到较大值，当然需要让j+1以便变成指向右孩子的下标。当前30的左右孩子是60和20，并不满足此条件，因此j还是 8。
5. 第9~10行，temp=30，L.r[j]=60，并不满足条件。
6. 第11~12行，将60赋值给 L.r[4]，并令 s=j=8。也就是说，当前算出，以 30为根结点的子二叉树，当前最大值是60，在第8的位置。注意此时 L.r[4]和 L.r[8]的值均为 60。
7. 再循环因为 j=2*j=16，m=9，j>m，因此跳出循环。
8. 第14行，将temp=30赋值给 L.r[s]=L.r[8]，完成30与60的交换工作。如图所示。本次函数调用完成。
   
9. 再次调用 HeapAdjust，此时s=3，m=9。第4行，temp=L.r[3]=90，第 7~8行，由于40<80得到 j+1=2*s+1=7。9~10行，由于90>80，因此退出循环，最终本次调用，整个序列未发什么改变。
10. 再次调用 HeapAdjust，此时 s=2，m=9。第4行，temp=L.r[2]=10，第7~8行，60<70，使得j=5。最终本次调用使得10与70 进行了互换，如图所示。
    
    
11. 再次调用 HeapAdjust，此时 s=1，m=9。第4行，temp=L.r[1]=50，第78行，70<90，使得 j=3。第 1112 行，L.r[1]被赋值了 90，并且 s=3，再循环，由于 2j=6 并未大于m，因此再次执行循环体，使得 L.r[3]被赋值了80，完成循环后，L.[7]被赋值为50，最终本次调用使得50、90、80进行了轮换，如图所示。
    
    到此为止，我们构建大顶堆的过程算是完成了，也就是HeapSort函数的第45行循环执行完毕。或许是有点复杂，如果不明白，多试着模拟计算机执行的方式走几遍，应该就可以理解其原理。
    接下来 HeapSort 函数的第611行就是正式的排序过程，由于有了前面的充分准备，其实这个排序就比较轻松了。下面是这部分代码。

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

1. 当i-9时，第8行，交换20与90，第9行，将当前的根结点 20 进行大顶堆的调整，调整过程和刚才流程一样，找到它左右子结点的较大值，互换，再找到其子结点的较大值互换。此时序列变为 {80,70,50,60,10,40,20,30,90}，如图所示。
2. 当i-8时，交换30与80，并将30与70交换，再与60交换，此时序列变为{70,60,50,30,10,40,20,80,90}，如图所示。
3. 后面的变化完全类似，不解释，只看图。
   最终就得到一个完全有序的序列了。

6.2 堆排序复杂度分析

堆排序的效率到底有多高呢?我们来分析一下，它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个结点到根结点的距离为 Llog2i」+1)，并且需要取 n-1次堆顶记录，因此，重建堆的时间复杂度为 O(nlogn)。
所以总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的 O(n^2)的时间复杂度了。
空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录的比较与交换是跳跃式进行，因此堆排序也是一种不稳定的排序方法。
另外，由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。

七、归并排序

前面我们讲了堆排序，因为它用到了完全二叉树，充分利用了完全二叉树的深度是Llog2n」+1 的特性，所以效率比较高。不过堆结构的设计本身是比较复杂的，老实说，能想出这样的结构就挺不容易，有没有更直接简单的办法利用完全二叉树来排序呢?当然有。
先来举一个例子。你们知道高考一本、二本、专科分数线是如何划分出来的吗?
简单地说，如果各高校本科专业在某省高三理科学生中计划招收1万名，那么将全省参加高考的理科学生分数倒排序，第1万名的总分数就是当年本科生的分数线(现实可能会比这复杂，这里简化之)。
也就是说，即使你是你们班级第一、甚至年级第一名，如果你没有上分数线，则说明你的成绩排不到全省前1万名，你也就基本失去了当年上本科的机会了。
换句话说，所谓的全省排名，其实也就是每个市、每个县、每个学校、每个班级的排名合并后再排名得到的。注意我这里用到了合并一词。
我们要比较两个学生的成绩高低是很容易的，比如甲比乙分数低，丙比丁分数低。那么我们也就可以很容易得到甲乙丙丁合并后的成绩排名，同样的，戊已辛的排名也容易得到，由于他们两组分别有序了，把他们八个学生成绩合并有序也是很容易做到的了，继续下去……最终完成全省学生的成绩排名，此时高考状元也就诞生了。
为了更清晰地说清楚这里的思想，大家来看图示，我们将本是无序的数组序列 {16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14}，通过两两合并排序后再合并，最终获得了一个有序的数组。注意仔细观察它的形状，你会发现，它像极了一棵倒置的完全二叉树，通常涉及到完全二叉树结构的排序算法，效率一般都不低的——这就是我们要讲的归并排序法。

7.1 归并排序的算法实现

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

归并排序(Merging Sort) 就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子列，每个子序列的长度为1，然后两两归并，得到n/2(向上取整，表示不小于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] */	}
}

1. MSort被调用时，SR与TR1都是 {50,10,90,30,70,40,80,60,20}，s=1，t=9，最终我们的目的就是要将 TR1 中的数组排好顺序。
2. 第5行，显然s不等于t，执行第 8~13 行语句块。
3. 第9行，m=(1+9)/2=5。m 就是序列的正中间下标。
4. 此时第10行，调用“MSort(SR,TR2,1,5);”的 目标就是将数组 SR 中的第1~5的关键字归并到有序的TR2(调用前TR2为空数组)，第11行，调用“MSort(SR,TR2,6,9);”的目标就是将数组SR中的第6~9 的关键字归并到有序的 TR2。也就是说，在调用这两句代码之前，代码已经准备将数组分成了两组了，如图所示。
5. 第12行，函数Merge的代码细节一会再讲，调用“Merge(TR2,TR1,1,5,9);”的目标其实就是将第10和11行代码获得的数组 TR2(注意它是下标为15和69的关键字分别有序)归并为TR1，此时相当于整个排序就已经完成了，如图所示。
6. 再来看第 10行递归调用进去后，s=1，t=5，m=(1+5)/2=3。此时相当于将5个记录拆分为三个和两个。继续递归进去，直到细分为一个记录填入TR2，此时s与t相等，递归返回，如左图所示。每次递归返回后都会执行当前递归函数的第12行，将TR2归并到TR1中，如右图所示，最终使得当前序列有序。
7. 同样的第 11 行也是类似方式，如图所示。
8. 此时也就是刚才所讲的最后一次执行第12行代码，将{10,30,50,70,90}与{20,40,60,80}归并为最终有序的序列。

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

现在我们来看看 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+1] = SR[i+1];    /* 将剩余的SR[i..m] 复制到 */
		}
	}
	if(j<=m)
	{
		for(l=0;l<=m;l++)
		{
			TR[k+1]=SR[j+1];  /* 将剩余的SR[j..n]复制到TR */
		}
	}
}

1. 假设我们此时调用的Merge 就是将 {10,30,50,70,90}与 {20,40,60,80}归并为最终有序的序列，因此数组SR为 {10,30,50,70,90,20,40,60,80}，i=1,m=5,n=9。
2. 第4行，for循环，j由 m+1=6开始到9,i由1开始到5,k由1开始每次加1,k 值用于目标数组 TR的下标。
3. 第6行，SR[i]=SR[1]=10，SR[j]=SR[6]=20，SR[i]<SR[j]，执行第7行,TR[k]=TR[1]=10，并且i++。如图所示。
   
4. 再次循环，k++得到k=2，SR[i]=SR[2]=30，SR[j]=SR[6]=20，SR[i]>SR[j]，执行第9行，TR[k]=TR[2]=20，并且j++，如图所示。
5. 再次循环，k++得到k=3，SR[i]=SR[2]=30，SR[j]=SR[7]=40，SR[i]<SR[j]，执行第7行，TR[k]=TR[3]=30，并且i++，如图所示。
6. 接下来完全相同的操作，一直到j++后，j=10，大于9退出循环，如图所示。
7. 第 1120行的代码，其实就将归并剩下的数组数据，移动到TR的后面。当前 k=9，i=m=5，执行第1320 行代码，for 循环 l=0，TR[k+I]=SR[i+l]=90大功告成。

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

7.2 归并排序的时间复杂度分析

我们来分析一下归并排序的时间复杂度，一趟归并需要将 SR[1]~SR[n]中相邻的长度为h的有序序列进行两两归并。并将结果放到 TR1[1]~TR1[n]中，这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行 [log2n]次，因此，总的时间复杂度为 O(nlgn)，而且这是归并排序算法中最好、最坏、平均的时间性能。
由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为 log2n 的栈空间，因此空间复杂度为 O(n+logn)。
另外，对代码进行仔细研究，发现Merge函数中有 if (SR[i]<SR[j])语句，这就说明它需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。
也就是说，归并排序是一种比较占用内存，但却效率高且稳定的算法。

7.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;    /* 子序列长度加倍 */
	}
}

1. 程序开始执行，数组L为 {50,10,90,30,70,40,80,60,20}，L.length=9。
2. 第3行，我们事先申请了额外的数组内存空间，用来存放归并结果。
3. 第5~11行，是一个 while 循环，目的是不断地归并有序序列。注意k值的变化，第8行与第10行，在不断循环中，它将由 1→2→4→8→16，跳出循环。
4. 第7行，此时k=1，MergePass函数将原来的无序数组两两归并入TR(此函数代码稍后再讲)，如图所示。
5. 第8行，k=2。
6. 第9行，MergePass 函数将TR中已经两两归并的有序序列再次归并回数组L中，如图所示。
7. 第10行，k=4，因为 k<9，所以继续循环，再次归并，最终执行完第7~1行，k=16，结束循环，完成排序工作，如图所示。
   从代码中，我们能够感受到，非递归的迭代做法更加直截了当，从最小的序列开始归并直至完成。不需要像归并的递归算法一样，需要先拆分递归，再归并退出递归。
   现在我们来看 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];
}

1. 程序执行。我们第一次调用 MergePass(L.r,TR,k,L.length);，此时 L.r 是初始无序状态，TR为新申请的空数组，k=1，L.length=9。
2. 第5~9行，循环的目的就两两归并，因 s=1，n-2*s+1=8，为什么循环i从1到8，而不是9呢?就是因为两两归并，最终9条记录定会剩下来，无法归并。
3. 第7行，Merge 函数我们前面已经详细讲过，此时 i=1，i+s-1=1，i+2*s-1=2。也就是说，我们将SR(即L.r)中的第一个和第二个记录归并到TR中，然后第8行，i=i+2*s=3，再循环，我们就是将第三个和第四个记录归并到 TR 中，一直到第七和第八个记录完成归并，如图所示。
4. 第1014行，主要是处理最后的尾数，第11行是说将最后剩下的多个记录归并到 TR 中。不过由于 i=9，n-s+1=9，因此执行第1314 行，将20放入到 TR 数组的最后，如图所示。
5. 再次调用 MergePass时，s=2，第5~9行的循环，由第8行的 i=i+2*s 可知，此时i就是以4为增量进行循环了，也就是说，是将两个有两个记录的有序序列进行归并为四个记录的有序序列。最终再将最后剩下的第九条记录“20”插入 TR，如图所示。
6. 后面的以此类推。

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

八、快速排序

终于我们的高手要登场了，如果将来你工作后，你的老板要让你写个排序算法而你会的算法中竟然没有快速排序，我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑。
事实上，不论是C++STL、Java SDK或者.NET FrameWork SDK 等开发工具包中的源代码中都能找到它的某种实现版本。
快速排序算法最早由图灵奖获得者 Tony Hoare 设计出来的，他在形式化方法理论以及 ALGOL60 编程语言的发明中都有卓越的贡献，是上世纪最伟大的计算机科学家之一。而这快速排序算法只是他众多贡献中的一个小发明而已。
更牛的是，我们现在要学习的这个快速排序算法，被列为20世纪十大算法之一。
我们这些玩编程的人还有什么理由不去学习它呢?
希尔排序相当于直接插入排序的升级，它们同属于插入排序类，堆排序相当于简单选择排序的升级，它们同属于选择排序类。而快速排序其实就是我们前面认为最慢的冒泡排序的升级，它们都属于交换排序类。即它也是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数。

8.1 快速排序算法实现

快速排序(Quicksort)的基本思想是:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
从字面上感觉不出它的好处来。假设现在要对数组 {50,10,90,30,70,40,80,60,20}进行排序。我们通过代码的讲解来学习快速排序的精妙。
我们来看代码。

public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public int partition(int[] arr, int left, int right) {
        int i = left;
        int j = right;
        while(i < j) {
            while (i < j && arr[j] >= arr[left]){
                j--;
            }
            while (i < j && arr[i] <= arr[left]){
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, i, left);
        return i;
    }

    public void quickSort(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

/* 对顺序表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(I,pivot+l,high); /*对高子表递归排序*/
	}
}

从这里，你应该能理解前面代码“QSort(L,1,L->length);”中1和L->length 代码的意思了，它就是当前待排序的序列最小下标值low 和最大下标值 high。
这一段代码的核心是“pivot=Partiton(L,ow,high);”在执行它之前，L.r的数组值为{50,10,90,30,70,40,80,60,20}。Partition 函数要做的，就是先选取当中的一个关键字，比如选择第一个关键字 50，然后想尽办法将它放到一个位置，使得它左边的值都比它小，右边的值比它大，我们将这样的关键字称为枢轴(pivot)。
在经过 Parttion(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函数实现。

/*交换顺序表工中子表的记录，使枢轴记录到位，并返回其所在位置*/
/*此时在它之前(后)的记录均不大(小)于它。*/
int Patition(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;  /* 返回数轴所在位置 */
}

1. 程序开始执行，此时 low=1，high=L.length=9。第4行，我们将 L.r[low]=L.r[1]=50赋值给枢轴变量 pivotkey，如图所示。
2. 第5~13 行为 whike 循环，目前 low=1<high=9，执行内部语句。
3. 第7行，L.r[high]=L.r[9]=20+pivotkey=50，因此不执行第8行。
4. 第9行，交换 L.r[low]与 L.r[high]的值，使得 L.r[1]=20，L.r[9]=50。为什么要交换，就是因为通过第7行的比较知道，L.r[high]是一个比 pivotkey=50(即 L.r[low])还要小的值，因此它应该交换到 50的左侧，如图所示。
5. 第10行，当 L.r[low]=L.r[1]=20，pivotkey=50，Lr[ow]<pivotkey，因此第11行，low++，此时 low=2。继续循环，L.r[2]=10<50，low++，此时 low=3。L.r[3]=90>50，退出循环。
6. 第12行，交换 L.r[low]=L.r[3]与 L.r[high]=L.r[9]的值，使得 Lr[3]=50,L.r[9]=90。此时相当于将一个比50大的值 90 交换到了50的右边。注意此时low 已经指向了 3，如图所示。
7. 继续第5行，因为 low=3<high=9，执行循环体。
8. 第7行，当 L.r[high]=L.r[9]=90，pivotkey=50，Lr[high]>pivotkey，因此第8.行，high--，此时 high=8。继续循环，L.r[8]=60>50，high--，此时 high=7,L.r[7]=80>50，high--，此时 high=6。Lr[6]=40<50，退出循环。
9. 第9行，交换 L.r[low]=L.r[3]=50与 L.r[high]=L.r[6]=40的值，使得 L.r[3]=40，L.r[6]=50，如图所示。
10. 第10行，当 L.r[low]=L.r[3]=40，pivotkey=50，Lr[kow]<pivotkey，因此第11行，low++，此时 low=4。继续循环 L.r[4]=30<50，low++，此时 low=5。L.r[5]=70>50，退出循环。
11. 第12行，交换 L.r[low]=L.r[5]=70与 L.r[high]-L.r[6]-50的值，使得 L.r[5]=50，L.r[6]=70，如图所示。
12. 再次循环。因 low=5<high=6，执行循环体后，ow=high=5，退出循环，如图所示。
13. 最后第14行，返回low的值5。函数执行完成。接下来就是递归调用 QSort(L,1,5-1);和 QSort(L5+1,9);语句，对 {20,10,40,30}和 {70,80,60,90}分别进行同样的Partton 操作，直到顺序全部正确为止。我们就不再演示了。

通过这段代码的模拟，大家应该能够明白，Partition函数，其实就是将选取的pivotkey 不断交换，将比它小的换到它的左边，比它大的换到它的右边，它也在交换中不断更改自己的位置，直到完全满足这个要求为止。

8.2 快速排序复杂度分析

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

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

也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。
在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行 n-1次递归调用，且第i次划分需要经过 n-i 次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为
最终其时间复杂度为 O(n^2)
平均的情况，设枢轴的关键字应该在第k的位置(1≤k≤n)，那么:

由数学归纳法可证明，其数量级为 O(nlogn)。
就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为 log2n，其空间复杂度也就为 O(logn)，最坏情况，需要进行n-1递归调用，其空间复杂度为 O(n)，平均情况，空间复杂度也为O(logn)。
可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

8.3 快速排序的优化

1. 优化枢轴选取

如果我们选取的 pivotkey 是处于整个序列的中间位置，那么我们可以将整个序列分成小数集合和大数集合了。但注意，我刚才说的是“如果……是中间”，那么假如我们选取的 pivotkey 不是中间数又如何呢?比如我们前面讲冒泡和简单选择排序一直用到的数组 {9,1,5,8,3,7,4,6,2}，由代码第4行 pivotkey=L->r[low];知道，我们应该选取9作为第一个枢轴pivotkey。此时，经过一轮“pivot=Partition(L,1,9);”转换后，它只是更换了9与2的位置，并且返回9给pivot，整个系列并没有实质性的变化，如图所示。

就是说，代码第4行“pivotkey=L->r[ow];”变成了一个潜在的性能瓶颈。排序速度的快慢取决于 L.r[1]的关键字处在整个序列的位置，L.r[1]太小或者太大，都会影响性能(比如第一例子中的 50 就是一个中间数，而第二例子的9 就是一个相对整个序列过大的数)。因为在现实中，待排序的系列极有可能是基本有序的，此时，总是固定选取第一个关键字(其实无论是固定选取哪一个位置的关键字)作为首个枢轴就变成了极为不合理的作法。
改进办法，有人提出，应该随机获得一个low与high之间的数 rnd，让它的关键字 Lr[rnd]与 Lr[low]交换，此时就不容易出现这样的情况，这被称为随机选取枢轴法。应该说，这在某种程度上，解决了对于基本有序的序列快速排序时的性能瓶颈。不过，随机就有些撞大运的感觉，万一没撞成功，随机到了依然是很小或很大的关键字怎么办呢?
再改进，于是就有了三数取中(median-of-three)法。即取三个关键字先进行排序，将中间数作为枢轴，一般是取左端、右端和中间三个数，也可以随机选取。这样至少这个中间数一定不会是最小或者最大的数，从概率来说，取三个数均为最小或最大数的可能性是微乎其微的，因此中间数位于较为中间的值的可能性就大大提高了。由于整个序列是无序状态，随机选取三个数和从左中右端取三个数其实是一回事，而且随机数生成器本身还会带来时间上的开销，因此随机生成不予考虑。
我们来看看取左端、右端和中间三个数的实现代码，在Parttion 函数代码的第3行与第4行之间增加这样一段代码。

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);  /* 交换中间与左端数据，保证左端较小 */
/* 此时L.r[low]已经为整个序列左中右三个关键字的中间值。 */

int pivotkey = L->r[low];    /* 用子表的第一个记录作枢轴记录 */

试想一下，我们对数组 {9,1,5,8,3,7,4,6,2}，取左9、中3、右2来比较，使 L.r[low]=3，一定要比9和2来得更为合理。
三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey，但是对于常大的待排序的序列来说还是不足以保证能够选择出一个好的pivotkey，因此还有办法是所谓九数取中(median-of-nine)，它先从数组中分三次取样，每次取三数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。显然就更加保证了取到的 pivotkey 是比较接近中间值的关键字。有兴趣的同学可以自己实现一下代码，这里不再详述了。

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //三数取中值
    public int medianTree(int[] arr, int left,int mid, int right) {
        if((left <= mid && mid <= right) || (left >= mid && mid >= right)) {
            return mid;
        }else if((right >= left && left >= mid) || (right <= left && left <= mid )){
            return left;
        }else
            return right;
    }

    public int partition(int[] arr, int left, int right) {
        int mid = medianTree(arr, left, (left+right)/2, right);
        swap(arr, left, mid);
        int i = left;
        int j = right;
        while(i < j) {
            while (i < j && arr[j] >= arr[left]){
                j--;
            }
            while (i < j && arr[i] <= arr[left]){
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, i, left);
        return i;
    }

    public void quickSort(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

2. 优化不必要的交换

观察发现，50这个关键字，其位置变化是1→9→3→6→5，可其实它的最终目标就是5，当中的交换其实是不需要的。因此我们对 Partiton函数的代码再进行优化。

/* 快速排序优化算法 */
int Partition1(SqList *L,int low,int high)
{
	int pivotkey;
	// 这里省略从三数取中代码
	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];  /* 将枢轴数值替换回L.r[low] */
	return low;        /* 返回枢轴所在位置 */
}

注意代码中加粗部分的改变。我们事实将pivotkey备份到 L.r[0]中，然后在之前是 swap 时，只作替换的工作，最终当low与high会合，即找到了枢轴的位置时，再将 L.r[0]的数值赋值回 L.r[low]。因为这当中少了多次交换数据的操作，在性能上又得到了部分的提高。如图所示。

3. 优化小数组时的排序方案

对于一个数学科学家、博士生导师，他可以攻克世界性的难题，可以培养最优秀的数学博士，但让他去教小学生“1+1=2”的算术课程，那还真未必会比常年在小学里耕耘的数学老师教得好。换句话说，大材小用有时会变得反而不好用。刚才我谈到了对于非常大的数组的解决办法。那么相反的情况，如果数组非常小，其实快速排序反而不如直接插入排序来得更好(直接插入是简单排序中性能最好的)。其原因在于快速排序用到了递归操作，在大量数据排序时，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了一个大炮打蚊子的大问题。因此我们需要改进一下 QSort 函数。

#define MAX_LENGTH_INSERT_SORT 7  /* 数组长度阈值 */
/* 对顺序表L中的子序列L.r[low..high]作快速排序 */
void QSort(SqList &L,int low, int high)
{
	int pivot;
	if((high-low) > MAX_LENGTH_INSERT_SORT)
	{/* 当high-low大于常数时用快速排序 */
		pivot = Partition(L,low,high);  /* 将L.r[low..high]一分为二，并算出枢轴值pivot	 */
		QSort(L,low,pivot-1);    /* 对低子表递归排序 */
		QSort(L,pivot+1,high);	 /* 对高子表递归排序 */
	}
	else   /* 当high-low小于等于常数时用直接插入排序 */
		InsertSort(L);
}

我们增加了一个判断，当 high-ow 不大于某个常数时(有资料认为7比较合适，也有认为 50更合理，实际应用可适当调整)，就用直接插入排序，这样就能保证最大化地利用两种排序的优势来完成排序工作。

4.优化递归操作

大家知道，递归对性能是有一定影响的，QSort函数在其尾部有两次递归操作。如果待排序的序列划分极端不平衡，递归深度将趋近于n，而不是平衡时的 log2n，这就不仅仅是速度快慢的问题了。栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此如果能减少递归，将会大大提高性能。

于是我们对 QSort 实施尾递归优化。来看代码。

public void quickSort(int[] arr, int left, int right) {
        while (left < right) {

            int pivot = partition(arr, left, right);
            if (pivot - left < right - pivot) {
                quickSort(arr, left, pivot - 1); // 递归排序左子数组
                left = pivot + 1;    // 剩余未排序区间为 [pivot + 1, right]
            } else {
                quickSort(arr, pivot + 1, right); // 递归排序右子数组
                right = pivot - 1;   // 剩余未排序区间为 [left, pivot - 1]
            }
        }

/* 对顺序表L中的子序列L.r[low..high]作快速排序 */
void QSort1(SqList &L,int low, int high)
{
	int pivot;
	if((high-low) > MAX_LENGTH_INSERT_SORT)
	{/* 当high-low大于常数时用快速排序 */
		while(low<high)
		{
			pivot = Partition(L,low,high);  /* 将L.r[low..high]一分为二，并算出枢轴值pivot	 */
			QSort1(L,low,pivot-1);    /* 对低子表递归排序 */
			low=pivot+1;    /* 尾递归 */
		}
	}
	else   /* 当high-low小于等于常数时用直接插入排序 */
		InsertSort(L);
}

当我们将if改成 while 后，因为第一次递归以后，变量 low 就没有用处了，所以可以将 pivot+1赋值给low，再循环后，来一次 Partion(L,lowhigh)，其效果等同于“QSort(L,pivot+1,high);”。结果相同，但因采用迭代而不是递归的方法可以缩减堆栈深度，从而提高了整体性能。

九、总结与回顾

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

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

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

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

• 简单算法:冒泡、简单选择、直接插入。
• 改进算法:希尔、堆、归并、快速。
  从平均情况来看，显然最后3种改进算法要胜过希尔排序，并远远胜过前3种简单算法。

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

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

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

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

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

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

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

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

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