数据结构与算法版第9章排序

第9章排序数据结构与算法(C++版)9.1概述一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素（简称为元素，也可称为记录）序列调整为“有序”的元素序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97

一般情况下，假设含n个元素的序列为{e1,e2,…，en}其相应的关键字序列为{k1,k2,…，kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：

kp1≤kp2≤…≤kpn按此固有关系将上式元素序列重新排列为

{ep1,ep2,

…，epn}的操作称作排序。二、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；

反之，若参加排序的元素数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。三、内部排序的方法

内部排序的过程是一个逐步扩大元素的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区

基于不同的“扩大”

有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类

归并类其它方法1.插入类

将无序子序列中的一个元素“插入”到有序序列中，从而增加元素的有序子序列的长度。2.交换类

通过“交换”无序序列中的元素从而得到其中关键字最小或最大的元素，并将它加入到有序子序列中，以此方法增加元素的有序子序列的长度。3.选择类

从元素的无序子序列中“选择”关键字最小或最大的元素，并将它加入到有序子序列中，以此方法增加元素的有序子序列的长度。4.归并类

通过“归并”两个(2路归并)、三个（3路归并）或多个(多路归并)有序子序列，逐步增加有序序列的长度。5.其它方法9.2插入排序一、直接插入排序有序序列elem[0..i-1]elem[i]无序序列elem[i..n-1]1.一趟直接插入排序的基本思想有序序列elem[0..i]无序序列elem[i+1..n-1]2.实现“一趟插入排序”的步骤3．将elem[i]插入(复制)到elem[j+1]的位置上。2．将elem[j+1..i-1]中的所有元素均后移一个位置；1．在elem[0..i-1]中查找elem[i]的插入位置，

elem[0..j]

elem[i]<

elem[j+1..i-1]；3.直接插入排序的实现

利用“顺序查找”实现“在elem[0..i-1]中查找elem[i]的插入位置”算法的实现要点：从elem[i-1]起向前进行顺序查找循环结束表明elem[i](=e)的插入位置为j+1jelem[i](=e)for(j=i-1;j>=0&&e<elem[j];--j);//从后往前找j=i-1插入位置对于在查找过程中找到的那些关键字大于elem[i](=e)的关键字的元素，并在查找的同时实现元素向后移动；for(j=i-1;j>=0&&e<elem[j];--j)elem[j+1]=elem[j];jelem[i]j=i-1上述循环结束后可以直接进行“插入”插入位置令i=1，3，…,n,实现整个序列的排序。for(i=1;i<n;++i){

在

elem[0..i-1]中查找elem[i]的插入位置;

插入elem[i];}template<classElemType>voidStraightInsertSort(ElemTypeelem[],intn)//操作结果:对数组elem作直接插入排序序{ for(inti=1;i<n;i++) { //第i趟直接插入排序

ElemTypee=elem[i]; //暂存elem[i] intj; //临时变量

for(j=i-1;j>=0&&e<elem[j];j--) { //将比e大的元素都后移

elem[j+1]=elem[j]; //后移

} elem[j+1]=e; //j+1为插入位置

}}二、希尔（Shell）排序希尔排序的基本思想：对待排元素序列先作“宏观”调整，再作“微观”调整。

所谓“宏观”调整，指的是，“跳跃式”的插入排序。1.希尔排序的思想将元素序列分成若干子序列，分别对每个子序列进行插入排序。其中，d

称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n个元素分成d个子序列：

{elem[0]，elem[0+d]，elem[0+2d]，…，elem[0+kd]}{elem[1]，elem[1+d]，elem[1+2d]，…，elem[1+kd]}…{elem[d-1],elem[2d-1],elem[3d-1],…,elem[(k+1)d-1]}2.希尔排序的实现方法例如：162512304711233691831

第一趟希尔排序，设增量d=51123

12

9

181625

36

30

4731

第二趟希尔排序，设增量d=3918

121123

162531

304736第三趟希尔排序，设增量d=1

911121618232530313647template<classElemType>voidShellInsert(ElemTypeelem[],intn,intincr)//操作结果:对数组elem作一趟增量为incr的Shell排序,对// 插入排序作出的修改是子序列中前后相邻元素的增// 量为incr,而不是1{ for(inti=incr;i<n;i++) { //第i趟插入排序

ElemTypee=elem[i]; //暂存elem[i] intj; //临时变量

for(j=i-incr;j>=0&&e<elem[j];j-=incr) { //将子序列中比e大的元素都后移

elem[j+incr]=elem[j]; //后移

} elem[j+incr]=e; //j+incr为插入位置

}}template<classElemType>voidShellSort(ElemTypeelem[],intn,intinc[],intt)//操作结果:按增量序列inc[0..t-1]对数组elem作Shell排// 序{ for(intk=0;k<t;k++) { //第k趟Shell排序

ShellInsert(elem,n,inc[k]); }}9.3交换排序一、起泡排序

假设在排序过程中，元素序列elem[0..n-1]的状态为：第i趟起泡排序无序序列elem[0..n-i]有序序列elem[n-i+1..n-1]n-i无序序列elem[0..n-i-1]有序序列elem[n-i..n-1]比较相邻元素，将关键字最大的元素交换到

n-i的位置上template<classElemType>voidBubbleSort(ElemTypeelem[],intn)//操作结果:在数组elem中用起泡排序进行排序{ for(inti=n-1;i>0;i--) { //第i趟起泡排序

for(intj=0;j<i;j++) { //比较elem[j]与elem[j+1] if(elem[j]>elem[j+1]) { //如出现逆序,则交换elem[j]和

//elem[j+1] Swap(elem[j],elem[j+1]); } } }}二、快速排序1.一趟快速排序（一次划分）

目标：找一个元素，以它的作为“枢轴”，凡其关键字小于枢轴的元素均移动至该元素之前，反之，凡关键字大于枢轴的元素均移动至该元素之后。致使一趟排序之后，元素的无序序列elem[s..t]将分割成两部分：elem[s..i-1]和elem[i+1..t]，且

elem[j]≤elem[i]≤elem[k](s≤j≤i-1)

枢轴

(i+1≤k≤t)。stlowhigh设elem[s]=52为枢轴

逐渐减小high，将elem[high]和枢轴进行比较，当elem[high]≥枢轴时，high--，否则进行交换

逐渐增大low，将elem[low]和枢轴进行比较，当elem[low]≤

枢轴时，low++，否则行交换high23low52high52low52例如lowhighhighhighlow8014

可见，经过“一次划分”，将关键字序列

52,49,80,36,14,58,61,97,23,75调整为:23,49,14,36,(52)58,61,97,80,75

在调整过程中，设立了两个变量：low

和high，它们的初值分别为：s和t，

之后逐渐减小high，增加low，并保证

elem[high]≥52，和elem[low]≤52,否则进行元素的“交换”。2.快速排序的实现

首先对无序的元素序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的序列无序子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序9.4选择排序一、简单选择排序假设排序过程中，待排元素序列的状态为：有序序列elem[0..i-1]无序序列elem[i..n-1]

第i趟简单选择排序从中选出关键字最小的元素有序序列elem[0..i]无序序列elem[i+1..n-1]template<classElemType>voidSimpleSelectionSort(ElemTypeelem[],intn)//操作结果:对数组elem作简单选择排序{ for(inti=0;i<n-1;i++) { //第i趟简单选择排序

intlowIndex=i;//elem[i..n-1]中最小元素小标

for(intj=i+1;j<n;j++) { if(elem[j]<elem[lowIndex]) { //lowIndexd当前的最小元素小标

lowIndex=j; } } Swap(elem[i],elem[lowIndex]); //交换

}}二、堆排序堆是满足下列性质的数列{e0,e1,…，en-1}：或堆的定义:(小顶堆)(大顶堆)eie2i+1

e2i+2

若将该数列视作完全二叉树，则e2i+1是ei的左孩子；e2i+2是ei

的右孩子。1236276549817355403498例如:是堆14不

堆排序即是利用堆的特性对元素序列进行排序的一种排序方法。例如：建大顶堆{98,81,49,73,36,27,40,55,64,12}{12,81,49,73,36,27,40,55,64,98}交换98和12重新调整为大顶堆{81,73,49,64,36,27,40,55,12,98}{40,55,49,73,12,27,98,81,64,36}经过筛选如何“建堆”？两个问题:如何“筛选”？所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。堆堆筛选98814973556412362740例如:是大顶堆12但在98和12进行互换之后，它就不是堆了，因此，需要对它进行“筛选”。9881121212比较比较73比较比较比较比较64建堆是一个从下往上进行“筛选”的过程。40554973816436122798例如:排序之前的关键字序列为1236817349988155

现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。984064361227557340499.5归并排序1.归并排序的基本思想

归并排序的过程基于下列基本思想进行：

将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。有序序列elem[l..n]有序子序列elem[l..m]有序子序列elem[m+1..n]这个操作对顺序表而言，是轻而易举的。2.归并排序的算法如果无序序列elem[s..t]的两部分

elem[s..(s+t)/2]和elem[(s+t)/2+1..t]分别按关键字有序，则利用上述归并算法很容易将它们归并成整个序列是一个有序序列。

由此，应该先分别对这两部分进行2-路归并排序。例如：*9.6基数排序

基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键字的排序链式基数排序一、多关键字的排序

n

个元素的序列{e1,e2,…，en}对关键字(ki0,ki1,…,kid-1)有序是指：

其中:k0被称为“最高”位关键字kd-1被称为“最低”位关键字

对于序列中任意两个元素ei和ej(1≤i<j≤n)都满足下列(词典)有序关系：

(ki0,ki1,

…,kid-1)<(kj0,kj1,

…,kjd-1)

实现多关键字排序通常有两种作法:最低位优先LSD法最高位优先MSD法（1）最高位优先MSD法先对k0进行排序，并按k0的不同值将元素序列分成若干子序列之后，分别对k1进行排序，...…，依次类推，直至最后对最次位关键字排序完成为止。（2）最低位优先LSD法先对kd-1进行排序，然后对kd-2进行排序，依次类推，直至对最主位关键字k0排序完成为止。

例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最高位关键字。

无序序列对K2排序对K1排序对K0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下:二、链式基数排序假如多关键字的元素序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。例如：对下列这组关键字

{27,91,01,97,17,23,72,25,05,67,84,07,21,31}

首先按其“个位数”取值分别为0,1,…,9

“分配”成10组，之后按从0至9的顺序将它们“收集”在一起；

然后按其“十位数”取值分别为0,1,…,9“分配”

成10组，之后再按从0至9的顺序将它们“收集”

在一起；

在计算机上实现基数排序时，为方便起见，可采用链表作存储结构，即链式基数排序，具体作法为：1．“分配”时，按当前“关键字位”所取值，将元素分配到不同的链表中，每个链表中元素的“关键字位”相同；2．“收集”时，按当前关键字位取值从小到大将各链表进行收集;3．对每个关键字位均重复1)和2)两步。{27,91,01,97,17,23,72,25,05,67,84,07,21,31}{91,01,21,31,72,23,84,25,05,27,97,17,67,07}

基数排序的时间复杂度为O(d(2n+r))其中：分配为O(n)

收集为O(r)(r为“基”)

d为“分配-收集”的趟数*9.7各种内部排序方法讨论一、时间性能（1）平均的时间性能基数排序时间复杂度为O(nlogn)：快速排序、堆排序和归并排序时间复杂度为O(n2)：直接插入排序、起泡排序和简单选择排序时间复杂度为O(n):（2）排元素序列按关键字顺序有序简单选择排序、起泡排序、堆排序和归并排序的时间性能不随元素序列中关键字的分布而改变。直接插入排序能达到O(n)的时间复杂度，

快速排序的时间性能蜕化为O(n2)

。（3）排序的时间性能不随关键字分布而改变的排序二、排序方法的稳定性能

稳定的排序方法指的是，对于两个关键字相等的元素，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。排序之前:{·····ei(k)·····ej(k)·····}排序之后:{·····ei(k)ej(k)··········}例如：

排序前

(56,34,47,23,66,18,82,

47)若排序后得到结果

(18,23,34,47,47,56,66,82)则称该排序方法是稳定的;若排序后得到结果

(18,23,34,

47,47,56,66,82)则称该排序方法是不稳定的。对于不稳定的排序方法，只要能举出一个实例说明即可。快速排序、所有选择排序(包括堆排序）和希尔排序是不稳定的排序方法。例如:对{4,3,4,2}进行快速排序，得到{2,3,4,4}9.8外部排序一.问题的提出