下载掌阅APP，畅读海量书库
立即打开
所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）的次序排列起来。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不是唯一的。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
要注意的是，排序算法的稳定性是针对所有的输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
插入排序的基本思想是，每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。
直接插入排序的过程是，在插入第i个记录时，R 1 ，R 2 ，…，R i -1 已经排好序，将第i个记录的排序码k i 依次和R 1 ，R 2 ，…，R i -1 的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n–1趟排序。各种状态下的时间复杂度如表1-1所示。
表1-1 直接插入排序有关数据
说明：初始文件按关键字递增排序，简称“正序”，初始文件按关键字递减排序，简称“反序”。
希尔（Shell）排序的基本思想是，先取一个小于n的整数d 1 作为第一个增量，把文件的全部记录分成d 1 个组。所有距离为d l 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d 2 ＜d 1 重复上述的分组和排序，直至所取的增量d t =1(d t ＜d t -1 ＜…＜d 2 ＜d 1 )，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
一般取d 1 =n/2，d i +1 =d i /2。如果结果为偶数，则加1，保证d i 为奇数。
例如，要对关键码{72，28，51，17，96，62，87，33，45，24}进行排序，这里n=10，首先取d 1 =n/2=5。则排序过程如图1-12所示。
图1-12 希尔排序的过程
希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，有人在大量实验的基础上指出，当n在某个特定范围内时，希尔排序的平均时间复杂度为O(n 1 .3 )。
选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。
直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第一个记录交换，然后在其余的记录内选出排序码最小的记录，与第二个记录交换……，依次类推，直到所有记录排完为止。
无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需进行n–i次比较，因此，总的比较次数为n(n–1)/2=O(n 2 )。当初始文件为正序时，移动次数为0；文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n–1)。直接选择排序的平均时间复杂度为O(n 2 )。直接选择排序是不稳定的。
交换排序的基本思想是，两两比较待排序记录的排序码，并交换不满足顺序要求的那些偶对，直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序。
冒泡排序将被排序的记录数组R[1…n]垂直排列，每个记录R[i]看成是重量为k i 的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
冒泡排序的具体过程如下。
第一步，先比较k 1 和k 2 ，若k 1 ＞k 2 ，则交换k 1 和k 2 所在的记录，否则不交换。继续对k 2 和k 3 重复上述过程，直到处理完k n -1 和k n 。这时最大的排序码记录转到了最后位置，称第一次起泡。共执行n–1次比较。
与第一步类似，从k 1 和k 2 开始比较，到k n -2 和k n -1 为止，共执行n–2次比较。称第二次起泡。
以此类推，共进行n–1次起泡，完成整个排序过程。
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数为n–1次，记录移动次数为0。因此，冒泡排序最好的时间复杂度为O(n)。
若初始文件是反序的，需要进行n–1趟排序。每趟排序要进行n–i次关键字的比较（1≤i≤n-1），且每次比较都必须移动记录3次来达到交换记录位置的目的。在这种情况下，比较次数达到最大值n(n–1)/2=O(n 2 )，移动次数也达到最大值3n(n–1)/2=O(n 2 )。因此，冒泡排序的最坏时间复杂度为O(n 2 )。
虽然冒泡排序不一定要进行n–1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。冒泡排序是就地排序，且它是稳定的。
快速排序采用了一种分治的策略，通常称其为分治法。其基本思想是，将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序的具体过程如下。
第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这两组中间。
第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。
例如，要对关键码{7，2，5，1，9，6，8，3}进行排序，选择第一个元素为基准。第一趟排序的过程如图1-13所示。
要注意的是，在快速排序中，选定了第一个元素为基准，接着就拿最后一个元素和第一个元素比较，如果大于第一个元素，则保持不变，再拿倒数第二个元素和基准比较；如果小于基准，则进行交换。交换之后，再从前面的元素开始与基准比较，如果小于基准，则保持不变；如果大于基准，则交换。交换之后，再从后面开始比较，依此类推，前后交叉进行。
然后，再采取同样的办法对{3，2，5，1，6}和{8，9}分别进行排序，具体过程如图1-14所示。
图1-13 第一趟排序过程
图1-14 各趟排序过程
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k–1次关键字的比较。
最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准左边的子区间为空（或右边的子区间为空），而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须进行n-1次划分，第i次划分开始时区间长度为n–i+1，所需的比较次数为n–i（1≤i≤n-1），故总的比较次数达到最大值n(n-1)/2=O(n 2 )。如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增次序（或递减次序）排列时，每次划分所取的基准就是当前无序区中关键字最小（或最大）的记录，则快速排序所需的比较次数反而最多。
在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数为O(nlog 2 n)。
因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为O(n 2 )，最好时间复杂度为O(nlog 2 n)。
尽管快速排序的最坏时间为O(n 2 )，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而 得 名。它的平均时间复杂度为O(nlog 2 n)。快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(log 2 n)，故递归后需栈空间为O(log 2 n)。在最坏的情况下，递归树的高度为O(n)，所需的栈空间为O(n)。快速排序是不稳定的。
归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看为有n个长度都为1的有序子表所组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们进行两两合并。直到得到长度为n的有序表，排序结束。
例如，需要对关键码{72，28，51，17，96，62，87，33}进行排序，其归并过程如图1-15所示。
图1-15 归并排序的过程
归并排序是一种稳定的排序，可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行log 2 n趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog 2 n)。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
设单关键字的每个分量的取值范围均是C 0 ≤k j ≤C rd –1 （0≤j＜d），可能的取值个数r d 称为基数。基数的选择和关键字的分解因关键字的类型而异。
（1）若关键字是十进制整数，则按个、十等位进行分解，基数r d =10，C 0 =0，C 9 =9，d为最长整数的位数。
（2）若关键字是小写的英文字符串，则r d =26，C 0 ='a'，C 25 ='z'，d为字符串的最大长度。
基数排序的基本思想是：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列。
基数排序的具体实现过程如下：设有r个队列，队列的编号分别为0，1，2，…，r–1。首先按最低有效位的值把n个关键字分配到这r个队列中；然后从小到大将各队列中的关键字再依次收集起来；接着再按次低有效位的值把刚刚收集起来的关键字分配到r个队列中。重复上述收集过程，直至最高有效位，这样便得到一个从小到大的有序序列。为减少记录移动的次数，队列可以采用链式存储分配，称为链式基数排序。每个队列设有两个指针，分别指向队头和队尾。
例如，需要对{288，371，260，531，287，235，56，299，18，23}进行排序，因为这些数据最高位为百位，所以需要3趟分配和收集。第1趟分配和收集（按个位数）的过程如图1-16所示；第2趟分配与收集（按十位数）的过程如图1-17所示；第3趟分配与收集（按百位数）的过程如图1-18所示。
图1-16 第1趟分配与收集
图1-17 第2趟分配与收集
图1-18 第3趟分配与收集
基数排序的时间复杂度为O(d(r+n))，所需的辅助存储空间为O(n+r d )，基数排序是稳定的。
顺序查找的基本思想是，从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。
成功时顺序查找的平均查找长度如下：
在等概率的情况下，p i =1/n(1≤i≤n)，故成功的平均查找长度为(n+…+2+1)/n=(n+1)/2，
即查找成功时的平均比较次数约为表长的一半。若k值不在表中，则须进行n+1次比较之后才能确定查找失败。
若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中的结点按查找概率由小到大存放，以便提高顺序查找的效率。
顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字排序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。
二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中的结点按关键字排序，并且要用向量作为表的存储结构。
二分法查找的基本思想如下（设R[low，…，high]是当前的查找区间）。
（1）确定该区间的中点位置：mid=[(low+high)/2]；
（2）将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下：
若R[mid].key＞k，则由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,…,mid-1]中。因此，新的查找区间是左子表R[low,…,high]，其中high=mid-1。
若R[mid].key＜k，则要查找的k必在mid的右子表R[mid+1,…,high]中，即新的查找区间是右子表R[low,…,high]，其中low=mid+1。
若R[mid].key=k，则查找成功，算法结束。
（3）下一次查找时针对新的查找区间进行，重复步骤（1）和（2）。
（4）在查找过程中，low逐步增加，而high逐步减少。如果high＜low，则查找失败，算法结束。
因此，从初始的查找区间R[1,…,n]开始，每经过一次与当前查找区间中点位置上的结点关键字比较，就可以确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为k的结点，或者直至当前的查找区间为空（即查找失败）时为止。
例如，我们要在{11，13，17，23，31，36，40，47，52，58，66，73，77，82，96，99}中查找58的过程如图1-19所示（粗体表示mid位置）。在上述序列中查找35的过程如图1-20所示。
图1-19 二分法查找58
图1-20 二分法查找35
二分法查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。需要注意的是，判定树的形态只与表结点的个数n相关，而与输入实例中R[1，…，n].key的取值无关。
设内部结点的总数为n=2 h –1，则判定树是深度为h=log 2 (n+1)的满二叉树。树中第k层上的结点个数为2 k – 1 ，查找它们所需的比较次数是k。因此在等概率假设下，二分法查找成功时的平均查找长度约为log 2 (n+1)–1。二分法查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度，即为[log 2 n]+1。二分法查找的最坏性能和平均性能相当接近。
虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费o(nlog 2 n)的时间。二分法查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分法查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表，可采用链表作为存储结构，进行顺序查找。链表上无法实现二分法查找。
分块查找（Blocking Search）又称索引顺序查找。它是一种性能介于顺序查找和二分法查找之间的查找方法。二分法查找表由分块有序的线性表和索引表组成。表R[1，…，n]均分为b块，前b–1块中结点个数为s=[n/b]，第b块的结点数允许小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。
抽取各块中的最大关键字及其起始位置构成一个索引表ID[l，…，b]，即ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。
分块查找的基本思想是：索引表是有序表，可采用二分法查找或顺序查找，以确定待查的结点在哪一块。
由于块内无序，只能用顺序查找。分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。如果以二分查找来确定块，则分块查找成功时的平均查找长度为ASL1 = log 2 (b+1)–1+(s+1)/2≈log 2 (n/s+1)+s/2；如果以顺序查找确定块，分块查找成功时的平均查找长度为ASL2 =(b+1)/2+(s+1)/2=(s 2 +2s+n)/(2s)。
注意，当
时ASL2取极小值
，即当采用顺序查找确定块时，应将各块中的结点数选定为
。
分块查找的优点是：在表中插入或删除一个记录时，只要找到该记录所属的块，就可以在该块内进行插入和删除运算；因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。
分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。