概述
插入排序
交换排序
选择排序
归并排序
分配排序
外排序
一、概述
什么是排序(Sorting)？
简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。
排序是计算机中经常遇到的操作。
排序的几个基本概念
数据表(Data List) 待排序的数据对象的有限集合。
关键字(Key) 作为排序依据的数据对象中的属性域。
主关键字 不同的数据对象若关键字互不相同，则这种关键字称为主关键字。
排序的确切定义 使一组任意排列的对象变成一组按关键字线性有序的对象。
排序的几个基本概念（续）
排序算法的稳定性 判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。如 2, 2*,1，排序后若为1, 2*, 2 则该排序方法是不稳定的。
内排序与外排序 区分标准：排序过程是否全部在内存进行。
排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。
排序的方法有很多，但简单地判断那一种算
法最好，以便能够普遍选用则是困难的。
评价排序算法好坏的标准主要有两条：算法
执行所需要的时间和所需要的附加空间。
另外，算法本身的复杂程度也是需要考虑
的一个因素。
排序算法所需要的附加空间一般都不大，矛
盾并不突出。而排序是一种经常执行的一
种运算，往往属于系统的核心部分，因此
排序的时间开销是算法好坏的最重要的标
志。
为简单起见，数据的存储结构采用记录数组形式，同时假定关键字是整数。记录数组的类型说明如下：
typedef struct
{ int key;
datatype other;
} rectype;
rectype R[n];
其中n为记录总数加1
二、插入排序
基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。
直接插入排序(Insert Sort)
希尔排序(Shell Sort)
直接插入排序(Insert Sort)
基本思想：当插入第i个对象时，前面的V[0],V[1],…,V[i-1]已经排好序，此时，用v[i]的关键字与V[i-1], V[i-2],…的关键字顺序进行比较，找到插入位置即将V[i]插入，原来位置上对象向后顺移。
直接插入排序举例
i (0) (1) (2) (3) (4) (5) temp
[21] 25 49 25* 16 08 25
1 [21 25] 49 25* 16 08 49
2 [21 25 49] 25* 16 08 25*
3 [21 25 25* 49] 16 08 16
4 [16 21 25 25* 49] 08 08
5 [08 16 21 25 25* 49]
直接插入排序算法
INSERTSORT(rectype R[])
{ int i,j;
for (i=2;i<n;i++)
{ R[0]＝R[i];
j＝i-1;
while (R[0].key<R[j].key)
R[j+1]＝R[j- -];
R[j+1]＝R[0];
}
}
算法中引入附加记录R[0]有两个作用：其一是进入查找循环之前，它保存了R[i]的副本，使得不至于因记录的后移而丢失R[i]中的内容；其二是在while循环“监视”下标变量j是否越界，一旦越界（即j<1），R[0]自动控制while循环的结束，从而避免了在while循环内的每一次都要检测j是否越界（即省略了循环条件j>=1）。因此，我们把R[0]称为“监视哨”。
直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。
若初始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的比较次数为2(n-1)。
若初始时关键字递减有序，这是最坏情况。这时的记录比较和移动次数分别为：
算法分析
直接插入排序的稳定性
直接插入排序是一种稳定的排序方法。
原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。
希尔排序
1959年由. Shell提出，又称缩小增量排序(Diminishing-increment sort) 。
基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。
希尔排序的基本过程
设待排序的对象序列有n个对象，首先取一个整数gap<n作为间隔，将全部对象分为gap个子序列，所有距离为gap的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然后缩小间隔gap，如取gap=gap/2，重复上述的子序列划分和排序工作，直到最后取gap为1为止。
希尔排序示例
i (0) (1) (2) (3) (4) (5) gap
21 25 49 25* 16 08
1 21 - - 25* 3
25 - - 16
49 - - 08
21 16 08 25* 25 49
2 21 - 08 - 25 2
16 - 25* - 49
08 16 21 25* 25 49
3 08 16 21 25* 25 49 1
08 16 21 25* 25 49
希尔排序算法
rectype R[n+d1];
int d[t];
SHELLSORT(rectype R[],int d)
{ int i,j,k,h;
rectype temp;
int maxint＝32767;
for (i=0;i<d[0];i++)
R[i].key＝-maxint;
k＝0;
do
{ h＝d[k];
for (i=h+dl;i<n+dl;i++)
{ temp＝R[i];
j＝i-h;
while (<R[j].key)
{ p[j+h]＝R[j];
j＝j-h;
}
R[j+h]＝temp;
}
k++;
} while(h!=1);
}
为什么shell排序的时间性能优于直接插入排序呢？因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟排序过程也较块。
希尔排序中gap的取法
Shell最初的方案是 gap= n/2, gap=gap/2，直到gap=1.
Knuth的方案是gap = gap/3+1
其它方案有：都取奇数为好；或gap互质为好等等。
希尔排序的时间复杂度
对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到。
Knuth的统计结论是，平均比较次数和对象平均移动次数在 与之间。
希尔排序的稳定性
希尔排序是一种不稳定的排序方法。
如序列 3 2 2* 5
三、交换排序
两种常见的交换排序
起泡排序(Bubble Sort)
快速排序(Quick Sort)
基本原理：两两比较待排序的对象的关键字，如果发生逆序，则交换之，直到全部对象都排好序为止。
起泡排序的基本过程
假设待排序的n个对象的序列为V[0],V[1],..., V[n-1]，起始时排序范围是从V[0]到V[n-1]
在当前的排序范围之内，自右至左对相邻的两个结点依次进行比较，让值较大的结点往下移(下沉)，让值较小的结点往上移(上冒)。每趟起泡都能保证值最小的结点上移至最左边，下一遍的排序范围为从下一结点到V[n-1]。
在整个排序过程中，最多执行(n-1)遍。但执行的遍数可能少于(n-1)，这是因为在执行某一遍的各次比较没有出现结点交换时，就不用进行下一遍的比较。
起泡排序示例
i (0) (1) (2) (3) (4) (5)
21 25 49 25* 16 08
1 08 21 25 49 25* 16
2 08 16 21 25 49 25*
3 08 16 21 25 25* 49
4 08 16 21 25 25* 49
起泡排序算法
BUBBLESORT(rectype R[])
{ int i,j,noswap;
rectype temp;
for (i=0;i<n-2;i++)
{ noswap＝TRUE;
for (j=n-1;j>=i;j++)
if (R[j+1].key<R[j].key)
{ temp＝R[j+1];
R[j+1]=R[j];
R[j]＝temp;
noswap＝FALSE;
}
if (noswap) break;
}
}
起泡排序的时间复杂度
考虑关键字的比较次数和对象移动次数
1、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为n-1，没有记录移动。
2、若初始状态是反序的，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为：
起泡排序方法是稳定的。
快速排序的基本过程
快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的方法。
其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。
快速排序示例
49
38
65
97
76
13
27
49’
38
65
97
76
13
27
49’
27
38
65
97
76
13
49’
49
38
97
76
13
65
49’
49
38
13
97
76
65
49’
49
38
13
76
97
65
49’
49
38
13
49
76
49
65
49’
49
temp
快速排序算法
int PARTITION(rectype R[],int l,int h)
{ int i,j;
rectype temp;
i=l; j=h; temp=R[i];
do {
while ((R[j].key >= )&&(i<j)) j--;
if (i<j) R[i++]=R[j];
while ((R[i].key<=)&&(i<j)) i++;
if (i<j) R[j--]=R[i];
} while (i!=j);
R[i]=temp;
return i;
}
QUICKSORT(rectype R[],int s1,int t1)
{ int i;
if (s1<t1)
{ i=PARTITION(R,s1,t1);
QUICKSORT(R,s1,i-1);
QUICKSORT(R,i+1,t1);
}
}
快速排序的时间复杂度
2、最好情况是每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。
考虑关键字的比较次数和对象移动次数
1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为
设C(n)表示对长度为n的序列进行快速排序所需的比较次数，显然，它应该等于对长度为n的无序区进行划分所需的比较次数n-1，加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k ，k=log2n，因此有：
快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。
可以证明，快速排序的平均时间复杂度也是O(nlog2n)。
快速排序是不稳定的排序方法。
四、选择排序
两种常见的选择排序
直接选择排序
堆排序
基本原理: 将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。
直接选择排序的基本过程
在一组对象V[i]到V[n-1]中选择具有最小关键字的对象
若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。
删除具有最小关键字的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。
直
接
选择
排序
示
例
49
38
65
97
76
13
27
49’
13
38
65
97
76
49
27
49’
13
27
65
97
76
49
38
49’
13
27
38
97
76
49
65
49’
13
27
38
49
76
97
65
49’
13
27
38
49
49’
97
65
76
13
27
38
49
49’
65
97
76
13
27
38
49
49’
65
76
97
直接选择排序算法
SELECTSORT(rectype R[])
{ int i,j,k;
rectype temp;
for (i=0;i<n-1;i++)
{ k=i;
for (j=i+1;j<n;j++)
if (R[j].key<R[k].key) k=j;
if (k!=i)
{ temp=R[i];
R[i]=R[k];
R[k]=temp;
}
}
}
直接选择排序的时间复杂度
2. 当文件为正序时，移动次数为0，文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
直接选择排序是不稳定的排序方法。
1、无论初始状态如何，在第i 趟排序中选择最小关键字的记录，需做n-i次比较，因此总的比较次数为：
堆排序
堆排序是一种树型选择排序。
在排序过程中，将R[1]到R[n]看成是一个完全二叉树顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小记录。
堆排序分为两个步骤：
1、根据初始输入，形成初始堆。
2、通过一系列的对象交换和重新调整
进行排序。
堆的定义
n个关键字序列K1, k2, ... ,Kn称为堆，当且仅当该序列满足特性：
从堆的定义可以看出，堆实质上是满足如下性质的二叉树：树中任一非叶子结点的关键字均小于或等于它的孩子结点的关键字。
10
15
56
25
30
70
10
15
56
25
30
70
小根堆示例
70
56
30
25
15
10
70
56
30
25
15
10
大根堆示例
堆排序的第一个工作是建堆，即把整个记录数组R[1]到R[n]调整为一个堆。显然,只有一个结点的树是堆，而在完全二叉树中，所有序号i >= low(n/2)的结点都是叶子，因此以这些结点为根的子树都已是堆。这样，我们只需依次将序号为low(n/2)，low(n/2)-1，...，1的结点作为根的子树都调整为堆即可。
我们以大根堆为例进行说明
若已知结点R[i]的左右子树已是堆，如何将以R[i]为根的完全二叉树也调整为堆？
解决这一问题可采用“筛选法”，其基本思想是：因为R[i]的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以我们必须在R[i]和它的左右孩子中选取关键字最大的结点放到R[i]的位置上。若R[i]的关键字已是三者中的最大者，则无须做任何调整，以R[i]为根的子树已构成堆，否则必须将R[i]和具有最大关键字的左孩子R[2i]或右孩子R[2i+1]进行交换。假定R[2i]的关键字最大，将R[i]和R[2i]交换位置，交换之后有可能导致R[2i]为根的子树不再是堆，但由于R[2i]的左右子树仍然是堆，于是可以重复上述过程，将以R[2i]为根的子树调整为堆，...，如此逐层递推下去，最多可能调整到树叶。
例子：关键字序列为 42，13，91，23， 24， 16，05，88，n=8，故从第四个结点开始调整
42
13
91
23
24
16
05
88
42
13
91
23
24
16
05
88
42
13
91
88
24
16
05
23
42
13
91
88
24
16
05
23
不调整
42
13
91
88
24
16
05
23
42
13
91
88
24
16
05
23
42
88
91
23
24
16
05
13
42
88
91
23
24
16
05
13
91
88
42
23
24
16
05
13
91
88
42
23
24
16
05
13
建成的堆
筛选算法
SIFT(rectype R[],int i;int m)
{ int j;
rectype temp;
temp=R[i];
j=2*i;
while (j<=m)
{ if ((j<m)&&(R[j].key<R[j+1].key)) j++;
if (<R[j].key)
{ R[i]=R[j];
i=j;j=2*i;
}
else break;
}
R[i]=temp;
}
上述算法只是对一个指定的结点进行调整。有了这个算法，则将初始的无序区R[1]到R[n]建成一个大根堆，可用以下语句实现：
for (i = n/2; i>=1; i--)
SIFT(R, i, n)
由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将R[1]和R[n]交换，这就得到了第一趟排序的结果。
第二趟排序的操作首先是将无序区R[1]到R[n-1]调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用SIFT函数将R[1]到R[n-1]调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录R[n-1]交换，如此反复进行下去。
91
88
42
23
24
16
05
13
91
88
42
23
24
16
05
13
（a）初始堆R[1]到R[8]
13
88
42
23
24
16
05
91
13
88
42
23
24
16
05
91
（b）第一趟排序之后
（c）重建的堆R[1]到R[7]
88
24
42
23
13
16
05
91
88
24
42
23
13
16
05
91
05
24
42
23
13
16
88
91
05
24
42
23
13
16
88
91
（d）第二趟排序之后
（e）重建的堆R[1]到R[6]
42
24
16
23
13
05
88
91
42
24
16
23
13
05
88
91
（f）第三趟排序之后
05
24
16
23
13
42
88
91
05
24
16
23
13
42
88
91
（g）重建的堆R[1]到R[5]
24
23
16
05
13
42
88
91
24
23
16
05
13
42
88
91
（h）第四趟排序之后
13
23
16
05
24
42
88
91
13
23
16
05
24
42
88
91
（i）重建的堆R[1]到R[4]
23
13
16
05
24
42
88
91
23
13
16
05
24
42
88
91
（j）第五趟排序之后
05
13
16
23
24
42
88
91
05
13
16
23
24
42
88
91
（k）重建的堆R[1]到R[3]
16
13
05
23
24
42
88
91
16
13
05
23
24
42
88
91
（l）第六趟排序之后
05
13
16
23
24
42
88
91
05
13
16
23
24
42
88
91
（m）重建的堆R[1]到R[2]
13
05
16
23
24
42
88
91
13
05
16
23
24
42
88
91
（n）第七趟排序之后
05
13
16
23
24
42
88
91
05
13
16
23
24
42
88
91
堆排序算法
HEAPSORT(rectype R[])
{ int i;
rectype temp;
for (i=n/2;i>=1;i--)
SIFT(R,i,n);
for (i=n;i>=1;i--)
{
temp=R[1]; R[1]=R[i];
R[i]=temp;
SIFT(R,1,i-1);
}
}
堆排序的时间复杂度
堆排序的时间复杂性为O(n log2n)
空间复杂性为 O(1)
堆排序是不稳定的排序方法。
五、归并排序
基本原理，通过对两个有序结点序列的合并来实现排序。
所谓归并是指将若干个已排好序的部分合并成一个有序的部分。
两路归并的基本思想
设有两个有序表A和B，对象个数分别为al和bl，变量i和j分别是两表的当前指针。设表C是归并后的新有序表，变量k是它的当前指针。i和j对A和B遍历时，依次将关键字小的对象放到C中，当A或B遍历结束时，将另一个表的剩余部分照抄到新表中。
两路归并的示例
25 57 48 37 12 92 86
25 57 37 48 92 12 86
25 37 48 57 12 86 92
12 25 37 48 57 86 92
归并算法
MERGE(rectypr R[],rectype R1[],int low,int mid,int
high)
{ int i,j,k;
i=low; j=mid+1; k=low;
while ((i<=mid)&&(j<=high))
if (R[i].key<=R[j].key) R1[k++]=R[i++];
else R1[k++]=R[j++];
while (j<=mid) R1[k++]=R[i++];
while (j<=high) R1[k++]=R[j++];
}
归并排序就是利用上述归并操作实现排序的。其基本思想是：将待排序列R[0]到R[n-1]看成n个长度为1的有序子序列，把这些子序列两两归并，便得到high(n/2)个有序的子序列。然后再把这high(n/2)个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。上述每次的归并操作，都是将两个子序列归并为一个子序列，这就是“二路归并”，类似地还可以有“三路归并”或“多路归并”。
归并过程示例
(25) (57) (48) (37) (12) (92) (86)
(25 57) (37 48) (12 92) (86)
(25 37 48 57) (12 86 92)
(12 25 37 48 57 86 92)
一趟归并算法
MERGEPASS(rectype R[],rectype R1[],int length)
{ int i,j;
i=0;
while (i+2*length-1<n)
{ MERGE(R,R1,i,i+length-1,i+2*length-1);
i=i+2*length;
}
if (i+length-1<n-1)
MERGE(R,R1,i,i+length-1,n-1);
else
for (j=i;j<n;j++) R1[j]=R[j];
}
归并排序算法
MERGESORT(rectype R[])
{ int length=1;
while (length<n)
{ MERGEPASS(R,R1,length);
length=2*length;
MERGEPASS(R1,R,length);
length=2*length;
}
}
算法复杂性分析
归并排序是稳定的排序方法。
归并排序在第i 趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做high(log2n)趟归并，每趟归并所花的时间为O(n)。所以，二路归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为O(n)。
六、基数排序
基本原理，采用“分配”和“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。
下面先介绍多关键字排序
多关键字排序方法示例
如对扑克牌的排序
每张扑克牌有两个“关键字”：花色和面值它们之间有次序的优先。
对以上排序，可以先对花色排序，或先对面值排序。
多关键字有序的概念
考虑对象序列{V0,V1,..., Vn-1}，每个对象Vi含d个关键字(Ki1,Ki2,..., Kid)。若对序列中的任意两个对象Vi和Vj都有
(Ki1,Ki2,..., Kid) < (Kj1,Kj2,..., Kjd)
则称序列对关键字(Ki1,Ki2,..., Kid)有序，且K1称为最高位关键字，Kd称为最低位关键字。
多关键字排序
原理：根据组成关键字的各位的值进行排序。
实现基数排序的两种方法：
1 最高位优先(MSD)排序：从关键
字的高位到低位
2 最低位优先(LSD)排序：从关键字
的低位到高位
MSD方法通常是一个递归的过程。
多关键字排序（续）
LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一个子关键字组：
(Ki1,Ki2,..., Kid)
如对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。
MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3 ,K2 , K1的顺序对所有对象排序。
链式的基数排序
基数排序是一种典型的LSD排序方法，它利用“分配”和“收集”两种运算对单关键字进行排序。
此时可将单关键字K看成是一个子关键字组：
(Ki1,Ki2,..., Kid)
排序过程：设关键字共有d位，让j= d, d-1,...,1, 依次执行d次“分配”与“收集”。
179
208
306
93
859
984
55
9
271
33
B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f
B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e
271
93
33
984
55
306
208
179
859
9
271
93
33
984
55
306
208
179
859
9
B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f
B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e
33
984
306
208
9
55
859
271
179
93
306
208
9
33
55
859
271
179
984
93
B[0].f B[1].f B[2].f B[3].f B[4].f B[5].f B[6].f B[7].f B[8].f B[9].f
B[0].e B[1].e B[2].e B[3].e B[4].e B[5].e B[6].e B[7].e B[8].e B[9].e
179
306
984
859
9
33
55
93
208
271
9
33
55
93
179
208
271
306
859
984
分配排序算法
typedef struct
{ int key[d];
int next;
datatype other;
} rectype;
rectype R[n];
typedef struct
{ int f,e;
} queue;
queue B[m];
for (j=d-1;j>=0;j--)
{ for (i=0;i<m;i++)
{ B[i].f=-1;
B[i].e=-1;
}
while (p!=-1)
{ k=R[p].key[j];
if (B[k].f==-1) B[k].f=p;
else R[B[k].e].next=p;
B[k].e=p;
p=R[p].next;
}
i=0;
while (B[i].f==-1) i++;
t=B[i].e; p=B[i].f;
while (i<m-1)
{ i++;
if (B[i].f!=-1)
{R[t].next=B[i].f; t=B[i].e;}
}
R[t].next=-1;
}
return p;
}
int RADIXSORT
(rectype R[])
{ int i,j,k,t,p;
for (i=0;i<n-1;i++)
R[i].next=i+1;
R[n-1].next=-1;
p=0;
内部排序方法的比较和选择
选取排序方法时需要考虑的因素有：
待排序的记录数目
记录本身信息量的大小
关键字的结构及其分布情况
对排序稳定性的要求
语言工具的条件、辅助空间的大小
外部排序简介
如果待排序的记录数很大，无法将所有记录都调入内存，只能将它们存放在外存上，我们称这时的排序为外部排序。
外部排序的实现，主要是依靠数据的内外存交换和“内部归并”。
