数据结构——排序

(共50张PPT)
第 8 章　排序
8.1 概述
8.2 插入排序
8.3 交换排序
8.4 选择排序
8.5 归并排序
8.6 基数排序
8.7 各种内部排序方法比较
1. 直接插入排序
2. 折半插入排序
3. 希尔排序
1. 冒泡排序
2. 快速排序
1. 简单选择排序
2. 树型选择排序
3. 堆排序
8.1 概述
排序：有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2， …，Kn }，相应的下标序列为1，2，…， n。通过排序，要求找出当前下标序列1，2，…， n的一种排列p1，p2， …，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤ Kp2≤…≤ Kpn ，这样就得到一个按关键字有序的记录序列：{Rp1， Rp2， …， Rpn}。
内部排序与外部排序：根据排序时数据所占用存储器的不同，可将排序分为两类。一类是整个排序过程完全在内存中进行，称为内部排序；另一类是由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，成为外部排序。
稳定排序与不稳定排序：
上面所说的关键字Ki可以是记录Ri的主关键字，也可以是次关键字，甚至可以是记录中若干数据项的组合。若Ki是主关键字，则任何一个无序的记录序列经排序后得到的有序序列是唯一的；若Ki是次关键字或是记录中若干数据项的组合，得到的排序结果将是不唯一的，因为待排序记录的序列中存在两个或两个以上关键字相等的记录。
假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri领先于Rj(即i在排序过程中，一般进行两种基本操作：
（1）比较两个关键字的大小；
（2）将记录从一个位置移动到另一个位置。
本章主要讨论在向量结构上各种排序方法的实现。为了讨论方便，假设待排记录的关键字均为整数，均从数组中下标为1的位置开始存储，下标为0的位置存储监视哨，或空闲不用。
typedef int KeyType;
typedef struct {
KeyType key;
OtherType other_data;
} RecordType;
8.2 插入排序
8.2.1 直接插入排序
8.2.2 折半插入排序
8.2.3 希尔排序
8.2.1 直接插入排序
直接插入排序是一种最基本的插入排序方法。其基本操作是将第i个记录插入到前面i-1个已排好序的记录中，具体过程为：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，Ki-2，…K1进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。完整的直接插入排序是从i=2开始，也就是说，将第1个记录视为已排好序的单元素子集合，然后将第二个记录插入到单元素子集合中。i从2循环到n，即可实现完整的直接插入排序。
图8.1 直接插入排序的例子。
A) { 48 } 62 35 77 55 14 35 98

B) { 48 62 } 35 77 55 14 35 98

C) { 35 48 62 } 77 55 14 35 98

D) { 35 48 62 77 } 55 14 35 98

E) { 35 48 55 62 77 } 14 35 98

F) { 14 35 48 55 62 77 } 35 98

G) { 14 35 35 48 55 62 77 } 98

H) { 14 35 35 48 55 62 77 98 }
假设待排序记录存放在r[1..n]之中，为了提高效率，我们附设一个监视哨r[0]，使得r[0]始终存放待插入的记录。监视哨的作用有两个：一是备份待插入的记录，以便前面关键字较大的记录后移；二是防止越界.
具体算法描述如下：
void InsSort(RecordType r[],int length)

{
for ( i=2 ; i< length ; i++ )
{
r[0]=r[i]; j=i-1;
while (r[0].key< r[j].key )
{
r[j+1]= r[j]; j=j-1;
}
r[j+1]=r[0];
}
}
算法描述
算法分析
该算法的要点是：①使用监视哨r[0]临时保存待插入的记录。②从后往前查找应插入的位置。③查找与移动用同一循环完成。
直接插入排序算法分析：首先从空间角度来看，它只需要一个辅助空间r[0]。
从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。
直接插入排序的时间复杂度为T(n)=O(n2)，空间复杂度为S(n)=O(1)。
直接插入排序方法是稳定的排序方法。
直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能就不好
8.2.2 折半插入排序
在直接插入排序中，我们采用顺序查找法来确定记录的插入位置。由于（R1，R2，…，Ri-1）是有序子文件，我们可以采用折半查找法来确定R1的插入位置，这种排序称为折半插入排序。其算法可写出如下：
算法描述
void BinSort (RecordType r[],int length)

{for ( i=2 ; i<=length ; ++i )
{x= r[i];low=1; high=i-1;
while (low<=high )
{mid=(low+high) / 2;
if ( x.key< r[mid].key ) high=mid-1;
else low=mid+1;
}
for ( j=i-1 ; j>= low; --j ) r[j+1]= r[j];
r[low]=x;
}
}
算法分析
采用折半插入排序法，可减少关键字的比较次数。每插入一个元素，需要比较的次数最大为折半判定树的深度，如插入第i个元素时，设i=2j,则需进行log2i次比较，因此插入n-1个元素的平均关键字的比较次数为O(nlog2n)。
虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。
8.2.3 希尔排序
希尔排序（Shell’s Method）又称“缩小增量排序”（Diminishing Increment Sort），是由D.L.Shell在1959年提出来的。
希尔排序的基本思想是：先将待排序记录序列分割成若干个“较稀疏的”子序列，分别进行直接插入排序。经过上述粗略调整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。
具体实现时，首先选定两个记录间的距离d1，在整个待排序记录序列中将所有间隔为d1的记录分成一组，进行组内直接插入排序，然后再取两个记录间的距离d2图8.2 希尔排序过程的实例
void ShellInsert(RecordType r[], int length， int delta)

{
for(i=1+delta ；i<= length； i++)

if(r[i].key < r[i-delta].key)
{
r[0]= r[i]；
for(j=i-delta； j>0 &&r[0].key < r[j].key ； j-=delta)
r[j+delta]= r[j]；
r[j+delta]= r[0]；
}
}
算法描述
void ShellSort(RecordType r[], int length)

{
for(i=0 ；i<=n-1；++i)
ShellInsert(r，Length, delta[i])；
}
算法描述续
算法分析
希尔排序的分析是一个复杂的问题，因为它的时间耗费是所取的“增量”序列的函数。到目前为止，尚未有人求得一种最好的增量序列。但大量研究也得出了一些局部的结论。
在排序过程中，相同关键字记录的领先关系发生变化，则说明该排序方法是不稳定的。
8.3 交换排序
8.3.1 冒泡排序
8.3.2 快速排序
8.3.1 冒泡排序
冒泡排序是一种简单的交换类排序方法，它是通过相邻的数据元素的交换，逐步将待排序序列变成有序序列的过程。
冒泡排序的基本思想是：从头扫描待排序记录序列，在扫描的过程中顺次比较相邻的两个元素的大小。以升序为例：在第一趟排序中，对n 个记录进行如下操作：若相邻的两个记录的关键字比较，逆序时就交换位置。在扫描的过程中，不断的将相邻两个记录中关键字大的记录向后移动，最后将待排序记录序列中的最大关键字记录换到了待排序记录序列的末尾，这也是最大关键字记录应在的位置。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是使次大的记录被放在第n-1个记录的位置上。如此反复，直到排好序为止（若在某一趟冒泡过程中，没有发现一个逆序，则可结束冒泡排序），所以 冒泡过程最多进行n-1趟。
图8.3 冒泡排序示例
算法描述
void BubbleSort(RecordType r[], int length )

{n=length; change=TRUE；
for ( i=1 ; i<= n-1 && change ;++i )
{ change=FALSE；
for ( j=1 ; j<= n-i ; ++j)
if (r[j].key> r[j+1].key )
{ x= r[j];
r[j]= r[j+1];
r[j+1]= x;
change=TRUE；
}
}
}
算法分析
最坏情况下，待排序记录按关键字的逆序进行排列，此时，每一趟冒泡排序需进行i次比较，3i次移动。经过n-1趟冒泡排序后，总的比较次数为
总的移动次数为3n(n-1)/2 次，因此该算法的时间复杂度为O(n2)，空间复杂度为O(1)。另外，冒泡排序法是一种稳定的排序方法。
8.3.2 快速排序
快速排序的基本思想是：从待排序记录序列中选取一个记录（通常选取第一个记录），其关键字设为K1，然后将其余关键字小于K1的记录移到前面，而将关键字大于K1的记录移到后面，结果将待排序记录序列分成两个子表，最后将关键字为K1的记录插到其分界线的位置处。我们将这个过程称作一趟快速排序。通过一次划分后，就以关键字为K1的记录为分界线，将待排序序列分成了两个子表，且前面子表中所有记录的关键字均不大于K1，而后面子表中的所有记录的关键字均不小于K1。对分割后的子表继续按上述原则进行分割，直到所有子表的表长不超过1为止，此时待排序记录序列就变成了一个有序表。
图8.4 快速排序图示
快速排序算法描述
void QKSort(RecordType r[],int low, int high )

{
if(1ow {
pos=QKPass(r, low, high);
QKSort(r, low, pos-1);
QKSort(r, pos+1, high);
}
}
一趟快速排序算法描述:
int QKPass(RecordType r[],int left，int right)
*对记录数组r 中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/
{ x= r[left]； low=left ; high=right；
while ( low{while (low< high && r[high].key>=x.key )

high--；
if ( low
while (low low++;
if ( low}
r[low]=x；
return low;
}
算法分析
分析快速排序的时间耗费, 共需进行多少趟，取决于递归调用深度。
快速排序所需时间的平均值为 Targ(n) ≤ Knln(n) ，这是目前内部排序方法中所能达到的最好平均时间复杂度。
但是若初始记录序列按关键字有序或基本有序时，快速排序将蜕变为冒泡排序，其时间复杂度为O(n2) 。为改进之，可采用其他方法选取枢轴元素，以弥补缺陷。
8.4 选择排序
选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。我们主要介绍简单选择排序、树型选择排序和堆排序。
8.4.1 简单选择排序
8.4.2 树型选择排序
8.4.3 堆排序
8.4.1 简单选择排序
简单选择排序的基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。例如：进行第i趟选择时，从当前候选记录中选出关键字最小的k号记录，并和第i个记录进行交换。
算法描述
void SelectSort(RecordType r[], int length)

{
n=length;
for ( i=1 ; i<= n－１; ++i)
{
k=i；
for ( j=i+1 ; j<= n ; ++j)
if (r[j].key < r[k].key ) k=j；
if ( k!=i)
{ x= r[i]； r[i]= r[k]； r[k]=x; }
}

}
算法分析
简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是
=(n-1)+(n-2)+…+2+1=n(n-1)/2，
即进行比较操作的时间复杂度为O(n2)。
8.4.2 树型选择排序
树型选择排序也称作锦标赛排序。它的基本思想是：先把待排序的n个记录的关键字两两进行比较，取出较小者。然后再在 n/2 个较小者中，采用同样的方法进行比较选出每两个中的较小者，如此反复，直至选出最小关键字记录为止。我们可以用一棵有n个结点的树来表示，选出的最小关键字记录就是这棵树的根结点。在输出最小关键字之后，为选出次小关键字，将根结点即最小关键字记录所对应的叶子结点的关键字的值置为∞，再进行上述的过程，直到所有的记录全部输出为止。
图8.5 树型选择排序示例
(a) 选出最小关键字13
图8.5 树型选择排序示例
(b) 选出次小关键字27
算法分析
在树型选择排序中，被选中的关键字都是走了一条由叶子结点到根结点的比较的过程,由于含有n个叶子节点的完全二叉数的深度 log2n +1，则在树型选择排序中，每选择一个小关键字需要进行 log2n 次比较，因此其时间复杂度为O(nlog2n)。移动记录次数不超过比较次数，故总的算法时间复杂度为O(nlog2n)。与简单选择排序相比较降低了比较次数的数量级，增加了n-1个额外的存储空间存放中间比较结果，同时附加了与∞进行比较的时间耗费。为了弥补，威洛母斯在1964年提出了进一步的改进方法，即另外一种形式的选择排序方法——堆排序。
8.4.3 堆排序
堆排序是对树型选择排序的进一步改进。采用堆排序时，只需要一个记录大小的辅助空间。堆排序是在排序过程中，将向量中存储的数据看成一棵完全二叉树，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小的记录，即待排序记录仍采用向量数组方式存储，并非采用树的存储结构，而仅仅是采用完全二叉树的顺序结构的特征进行分析而已。
具体做法是：把待排序的记录的关键字存放在数组r[1..n]之中，将r 看成是一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录r[1]作为二叉树的根，以下各记录r[2...n]依次逐层从左到右顺序排列，任意结点r[i]的左孩子是r[2i],右孩子是r[2i+1],双亲是r[ i/2 ]。对这棵完全二叉树进行调整，使各结点的关键字值满足下列条件：
r[i].key≥r[2i].key并且r[i].key≥r[2i+1].key(i=1,2, ... n/2 )，满足这个条件的完全二叉树为堆。这个堆中根结点的关键字最大，称为大根堆。反之，如果这棵完全二叉树中任意结点的关键字大于或者等于其左孩子和右孩子的关键字（当有左孩子或右孩子时），对应的堆为小根堆。
图8.6 堆示例
(a)大根椎
(b)小根椎
8.5 归并排序
前面介绍的三类排序方法：插入排序、交换排序和选择排序，都是将一组记录按关键字大小排成一个有序的序列。
而本节介绍的归并排序法，它的基本思想是将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到 个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。
归并的思想主要用于外部排序。
外部排序可分两步，①待排序记录分批读入内存，用某种方法在内存排序，组成有序的子文件，再按某种策略存入外存。②子文件多路归并，成为较长有序子文件，再记入外存，如此反复，直到整个待排序文件有序。
外部排序可使用外存、磁带、磁盘，最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略，归并路数取决于所能提供排序的外部设备数。
8.6 基数排序
前介绍的排序方法都是根据关键字值的大小来进行排序的。本节介绍的方法是按组成关键字的各个位的值来实现的排序的，这种方法称为基数排序（radix sort）。采用基数排序法需要使用一批桶（或箱子），故这种方法又称为桶排序列。下面以十进制数为例来说明基数排充的过程。
假定待排序文件中所有记录的关键字为不超过d位的非负整数，从最高位到最低位（个位）的编号依次为1，2，…，d。设置10个队列（即上面所说的桶），它们的编号分别为0，1，2，…，9。当第一遍扫描文字时，将记录按关键字的个位（即
第d位）数分别放到相应的队列中：个位数为0的关键字，其记录依次放入0号队列中i个位数为1的关键字，其记录放入1号队列中…；个位数为9的关键字，其记录放入9号队列中。这一过程叫做按个位数分配。现在把这10个队列中的记录，按0号，1号，9号队列的顺序收集和排列起来，同一队列中的记录按先进先出的次序排列。这是第1遍。第2遍排序使用同样的办法，将第1遍排序后的记录按其关键字的十位数（第d—1位）分配到相应的队列中，再把队列中的记录收集和排列起来。继续进行下去。第d遍排序时，按第d—1遍排序后记录的关键字的最高位（第1位）进行分配，再收集和排列各队列中的记录，医得到了原文件的有序文件，这就是以10为基的关键字的基数排序法。
例如，给出关键字序列（02，77，70，54，64，21，55，11，38，21），其中关键字02用1个0在2的前面补足到2位，余关键字均为2位的正整数。进行基数排序的过程如图9-9所示。
在这个例子中，文件和所有的队列都表示成向量（一维数组）。显然，关键字的某一位有可能均为同一个数字（例如，个数都为0），这时所有的记录都同时装入同一个队列中（例如，同时装入0号队列中）。因此，如果每个队列的大小和文件大小相同，则需要一个10倍于文件大小的附加空间。此外，排序时需要进行反复的分配和收集记录。所以，采用顺序表示是不方便的。
基数排序所需的计算时间不仅与文件的大小n有关，而且还与关键字的位数、关键字的基有关。设关键字的基为r（十进制数的基为10，二进制数的基为2），为建立r个空队列所需的时间为O（r）。把n个记录分放到各个队列中并重新收集起来所需的时间为O（n），因此一遍排序所需的时间为O（n+r）。若每个关键字有d位，则总共要进行d遍排，所以基数排序的时间复杂度为O（d（n+r））。由于关键字的位数d直接与基数r以及最大关键字的值有关，因此不同的r和关键字将需要不同的时间。
8.7 各种内部排序方法比较
在已介绍的上述各种内部排序方法中，就所需要的计算时间来看，快速排序、归并排序、堆排序是很好的方法。但是，归并排序需要大小为n的辅助空间，快速排序需要一个栈。除了快速排序、堆排序、选择排序不稳定外，基它排序方法都是稳定的。评价一个排序算法性能好坏的主要标准是它所需的计算时间和存储空间。影响计算时间的两个景要因素是比较关键字的次数和记录的移动次数。在实际应用中，究竟应该选用何种排序方法，取决于具体的应用和机器条件。
迄今为止，已有的排序方法远远不止本章讨论的这些方法，人们之所以热衷于研究多种排序方法，不仅是由于排序在计算机中所处的重要地位，而且还因为不同的方法各有其优缺点，可适用于不同的场合。选取排序方法时需要考虑的因素有：
待排序的记录数目n；记录本身信息量的大小；关键字的结构及分布情况；对排序稳定性的要求；语言工具的条件，辅助空间的大小等。依据这些因素，可得出如下几点结论：
（1）若n较小（譬如n50)，可采用直接插入排序或直接选。由于直接插入排序所需记录移动操作较直接选择排序多，因此若记录本身信息量较大时，则选用直接选择排序为宜。
（2）若文件的初始状态已是按关键字基本有序，则选用直接插入排序泡排序为宜。
（3）若N较大，则应采用时间复杂度为的排序方法：快速排序\堆排序或归并排序，快速排序是目前基于内部排序的中被认为是最好的方法，档待排序的关键字是随机人布时，快速排序的平均时间最少，但堆排序所需的辅助窨少于快速排序，并且不会出现序可能出现的最坏情况，这两种排序方法都是不稳定的，若要求排序稳定则可选用归并排序。但本文章结合介绍的单个记录起进行两两归并排算法并不值得提倡，通常可以将它和直接排序结合在一起用。先利用直接插入排序求得的子文件，然后，再两 两 归并之。因为直接插入排序是稳定的，所以，改进后的归并排序是稳定的。
（4）在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此，可以利用一棵二叉树来描述比较判定过程，由此可以证明;当文件的N个关键字分布时，任何借助于比较的排序算法，至少要的时间，由于箱排序和基数排序只需一步就会引起M种可能的转移，即把一个记录半装入M个箱子之一，因此，在一般情况下，箱乔序和排序可能在时间内完成对N个记录的。但踞的是，箱排序和排序只适用于象字符串和整数这类有明显的结构特征的关键字，当关键字的取值范围属于某个无穷集合时，无法使用箱排序和排序，这时只有借助于比较方法来排序。由此可知，若N较大，记录的关键字倍数较少时且可以分解时采用排序较好。
（5）前面讨论的排序算法，除排序外，都是在一维数组上实现的，当记录本身信息量较大时，为了避免浪费大量时间移动记录，可以用链表作为存储结构，如插入排序和归并排序都易于在链表上实现，并分别称之为表和归并表，但有的方法，如快速排序和堆排序，在链表上难于实现，在这种情况下，可以提取关键字建立索引表，然后，对索引表进行排序。然而更为简单的方法是;引入一个整形向量作为辅助表，排序前，若排序算法中要求交换，则只需交换R[I]和R[j]即可，排序结束后，向量就指示了记录之间的顺序关系：
无论是用链表还是用辅助空间来实现排序，都有可能要求最终结果是:
若上述要求，则可以在排序结束后，再按链表或辅助窨表所规定的次序重排各记录，完成这种 重排时间是o(n)。