数据结构 第七章 排序

第七章 排序 知 识 点 难 点 排序的基本概念 三种简单的排序方法：冒泡排序、直接选择排序、简单插入排序 堆排序 快速排序 归并排序 第七章 排序 知 识 点 排序的基本概念 三种简单的排序方法：冒泡排序、直接选择排序、简单插入排序 堆排序 快速排序 归并排序 基数排序 难 点 第七章 排序

要 求 熟练掌握以下内容： 熟悉各种内部排序方法的基本思想和特点 各种排序方法的优缺点、时、空性能和适用场合 熟悉并掌握三种简单排序算法、快速排序算法和堆排序算法 了解以下内容： 二路归并排序算法 基数排序算法 第七章 排序

第七章目录 7.1 排序的基本概念 7.2 三种简单排序方法 7.3 堆排序 7.4 快速排序 7.5 归并排序 7.6 基数排序 7.1 排序的基本概念 7.2 三种简单排序方法 7.3 堆排序 7.4 快速排序 7.5 归并排序 7.6 基数排序 7.7 应用实例及分析 小 结 习题与练习 第七章 排序

7.1 排序的基本概念 将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序(sort)。 对一批记录的排序，应该指定是根据记录中哪个域的数据进行排列。这个作为排序依据的数据域我们称之为关键字(key)。 本章讨论的排序均为按递增顺序排序，并假定要排序的记录均已存储在一个一维数组中。 第七章 排序

ElemType data; /*其他域*/ }sqlist[MAXITEM]; 该一维数组定义如下： #define MAXITEM 100 struct record { KeyType key; /*关键字*/ ElemType data; /*其他域*/ }sqlist[MAXITEM]; 第七章 排序

大多数的排序方法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内部排序。 如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。 一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。 返回 第七章 排序

7.2.1 简单选择排序 简单选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。 在每一趟扫描数据时，用一个整型变量跟踪当前最小数据的位置，然后，第i趟扫描只需将该位置的数据与第i个数据交换即可。这样扫描n-1次，处理数据的个数从n每次逐渐减1，每次扫描结束时才可能有一次交换数据的操作。 第七章 排序

图7.1 简单选择排序 第七章 排序

简单选择排序分析 简单选择排序在(n-1)趟扫描中共需进行n(n-1)/2次比较，最坏情况下的互换次数为(n-1)，整个算法的时间复杂性为O(n2)。 简单选择排序简单并且容易实现，适宜于n较小的情况。 简单选择排序是不稳定的排序算法。 第七章 排序

简单选择排序算法 void selectsort (sqlist r, int n) { int i, j, min; for (i=1;i<=n-1;i++) min=i; /*用min指出每一趟在无序区范围内的最小元素*/ 第七章 排序

简单选择排序算法续 for (j=i+1;j<=n-1;j++) if (r[j].key < r[min].key) min=j; r[0] = r[i]; /* r[0]用于暂时存放元素*/ r[i] = r[min]; r[min] =r[0]; } 第七章 排序

7.2.2 冒泡排序 冒泡排序是一种简单而且容易理解的排序方法，它和气泡从水中不断往上冒的情况有些类似。 其基本思想是对存放原始数据的数组，按从后往前的方向进行多次扫描，每次扫描称为一趟（pass）。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。 第七章 排序

图7.2 冒泡排序过程 第七章 排序

需扫描的趟数视原始数据最初的排列次序的不同而不同，最坏的情况要进行（n-1）趟扫描，一般常常少于(n-1)趟即可完成。 可以设置一个标志flag用来指示扫描中有没有进行数据交换，每趟扫描开始前将其置1。当这趟扫描至少出现一次互换时，将其置0。如某趟扫描后flag仍为1，说明此趟扫描已无数据互换，则排序结束，不必再继续扫描了。 第七章 排序

冒泡排序算法 void bubblesort(sqlist r, int n) { int i,j,flag; for(i=1;i<=n-1;i++) flag=1; for( j=i;j<=n-1;j++) if (r[j+1].key < r[j].key) 第七章 排序

冒泡排序算法续 { flag=0; r[0]=r[j]; /* r[0]用于暂时存放元素*/ r[j]=r[j+1]; } if (flag==1) return; 第七章 排序

冒泡排序算法分析 冒泡排序算法的优点是比较容易理解，且当原始数据大体符合要求的次序时，运算速度较快。 但它不是高效率的算法，在最坏的情况下，如果输入数据的次序与排序要求的次序完全相反，冒泡排序需要进行n(n-1)/2次比较和n(n-1)3/2次移动，其数量级均为O(n2)。 对于有相同关键字记录的情况，冒泡排序是稳定的。 第七章 排序

7.2.3 直接插入排序 直接插入排序的基本思想是：从数组的第二个单元开始，依次从原始数据中取出数据，并将其插入到数组中该单元之前的已排好序的序列中合适的位置处。 直接插入算法需要经过（n-1）趟插入过程。如果数据恰好应插入到序列的最后端，则不需移动数据，可节省时间，所以若原始数据大体有序，此算法可以有较快的运算速度。 第七章 排序

图7.3 简单插入排序 第七章 排序

简单插入排序算法 void insertsort (sqlist r, int n) { int i,j; for( i=2; i<=n; i++) r[0]=r[i]; /* r[0]用于暂时存放待插入的元素*/ j= i-1; /* j为待比较元素下标，初始时指向待插入元素前一个单元*/ 第七章 排序

简单插入排序算法续 while (r[0].key<r[j].key) { r[j+1]=r[j]; j--; } r[j+1]=r[0]; /* 在j+1位置插入r[0]*/ 简单插入排序的时间复杂性是O(n2)。 对于有相同关键字记录的情况，此算法是稳定的。 返回 第七章 排序

7.3.1 堆的概念 堆排序（Heap Sort）是利用二叉树的一种排序方法。 由于堆是完全二叉树，采用将结点顺序编号存入一维数组中的表示法比链接表示法节省存储空间，也便于计算。 第七章 排序

设某堆的结点数共有n个，顺序将它们存入一维数组r中。根据顺序表示二叉树的特点，除下标为1的结点是整棵树的根结点而没有父结点以外，其余下标为j的结点（2≤j≤n）都有父结点，父结点的下标为i= 。 故堆的条件可以表示成： r[i]≥r[j] 当2≤j≤n且i= 第七章 排序

图7.4 堆及其顺序存储结构 第七章 排序

堆排序 由堆的定义可知，其根结点（即在数组中下标为1的结点）具有最大的数字，堆排序就是利用这一特点进行的。 实现堆排序需要解决二个问题： 1. 对一组待排序的数据，先将它们构建成一个堆，输出堆顶的最大数据； 2. 将余下的n-1个数据再构建堆，输出具有次小值的数据；如此反复进行下去，直至全部数据都输出，就可以得到排好序的元素序列。 第七章 排序

7.3.2 构建堆 一般构建堆是采用一种称为筛选（sift）的算法。这种方法是将一个无序数据序列的构建堆的过程看作一个反复“筛选”的过程。 设原始数据为7，10，13，15，4，20，19，8（数据个数n=8）。 首先把这些数据按任意次序置入完全二叉树的各结点中，由于原始数据的次序是任意的，此树一般不符合堆的条件，需要用筛选运算进行调整。 第七章 排序

筛选运算是从最末尾结点的父结点开始，向前逐结点进行，直至筛选完根结点即形成此堆。 筛每个结点时，将其数值与其两个儿子结点中数值较大者进行比较，如小于该儿子结点数值，则与之进行交换，互换后又将它看成父结点，再与下一层的儿子结点进行比较，如此做下去，直至不小于其儿子结点的数值，或已筛到叶结点而不再有儿子结点了，此数据的筛选运算即完成。 第七章 排序

图7.5 用筛选算法构建堆 第七章 排序

第七章 排序

第七章 排序

筛选算法 设共有n个结点，置于一维数组r中，则筛选第v号结点的函数如下： void sift (sqlist r, int v, int n) { int i,j; i=v; j=2*i; /* j为i的左儿子结点下标*/ r[0]=r[i]; /* 将待筛数据暂存于r[0]中*/ while (j<=n) if (j<n && r[j].key<r[j+1].key) 第七章 排序

筛选算法续 j++; /* 如右儿子数据较左儿子大，将j改为右儿子下标*/ if (r[0].key<r[j].key) { r[i]=r[j]; i=j; j=2*i;/*如待筛数据小于其儿子数据，则与其儿子数据互换*/ } else j=n+1; /*筛选完成，令j=n+1，以便终止循环*/ 第七章 排序

筛选算法续 } r[i]=r[0]; /*被筛结点数据放入最终位置*/ 令待筛结点下标v由 逐次减小到1，反复调用函数sift，就可以得到符合条件的堆。 第七章 排序

7.3.3 利用堆排序 利用堆进行排序的方法是从根结点逐个取出数据，每次将新的再提到根结点，如此反复进行，直到堆只剩下一个结点为止。 为了节约存储空间，要求排序得到的有序数据序列仍存放于原数组中，故将从根结点取出的数据由数组的末端起逐单元存放。每存放一个数据，同时将原来在该单元的数据换到根结点。但这样互换后一般会破坏堆的条件，因此需要对根结点再做依次筛选运算，即令v=1再调用一次函数sift，就又可形成新的满足条件的堆。 第七章 排序

随着数组末端存放的由堆中取出的数据越来越多，堆的结点数逐渐减少，到取出了(n-1)个数据，堆中只剩下一个结点，这个数据一定是全部数据中最小的一个，堆排序即全部结束。 图7.6所示是利用堆进行排序的前几步，排序前的初始情况如图7.5所示的已构建好的堆。图中虚线以下为已从根结点逐个取出的有序数据，以上则为剩下的完全二叉树的结点。 第七章 排序

图7.6 堆排序 第七章 排序

第七章 排序

第七章 排序

第七章 排序

第七章 排序

堆排序算法 void heapsort (sqlist r, int n) { int i; for (i=n/2; i>=1; i--) sift (r, i, n); /* 初始建堆*/ for (i=n; i>=2; i--) { /*进行n-1次循环，完成堆排序*/ r[0]=r[i]; /*将第1个元素同当前区间内最后一个元素互换*/ r[i]=r[1]; r[1]=r[0]; sift (r, 1, i-1); /*筛选r[1]结点，得到(n-1)个结点的堆*/ } 堆排序算法 第七章 排序

堆排序算法分析 整个堆排序过程的时间复杂性是n与h的乘积数量级，考虑到h与n的关系，其复杂性为O(nlogn)。 堆排序适合于待排序的数据较多的情况，对于存在相同关键字的记录的情况，堆排序是不稳定的。 返回 第七章 排序

7.4 快速排序 快速排序是由冒泡排序改进而得到的，又称为分区交换排序，是目前内部排序中速度较快的方法。 基本思想：在待排序的n个数据中任取一个数据（通常取第一个数据），把该数据放入合适的位置，使得数据序列被此数据分割成两部分，所有比该数据小的放置在前一部分，所有比它大的放置在后一部分，即该数据排在这两部分的中间。此数据在进一步的运算过程中不必再动，以后的排序运算只需在划分成的每部分里进行，两部分之间也不会再有数据交换。 第七章 排序

图7.7所示为一个快速排序的例子，图中的方括号表示待排序部分，下面有横线的数据则是某次进行划分时所选的数据。 第一次划分以后，再用相同的算法对划成的两部分分别进行类似的运算，即从每一部分中任选一个数据将其划分成更小的两部分。依此递归地做下去，直至每个小部分中的数据个数为一个，排序过程就结束了。 图7.7所示为一个快速排序的例子，图中的方括号表示待排序部分，下面有横线的数据则是某次进行划分时所选的数据。 第七章 排序

图7.7 快速排序 第七章 排序

一趟快速排序采用从两头向中间扫描的办法。 假设原始数据已存于一个一维数组r中，具体的做法是：设两个指示器i和j，初始时i指向数组中的第一个数据，j指向最末一个数据。i先不动使j逐步前移，每次对二者所指的数据进行比较，当遇到r[i]大于r[j]的情况时，就将二者对调位置；然后令j固定使i逐步后移做数据比较，当遇到r[i]大于r[j] 时，又进行位置对调；然后又是i不动使j前移作数据比较；……； 如此反复进行，直至i与j两者相遇为止。 第七章 排序

图7.8所示是第一趟进行划分时的比较和互换过程。 图中括号中的数据表示正进行比较的两个数据，左面一个的下标为i，右面一个的下标为j。 第七章 排序

图7.8 一趟数据比较和互换 第七章 排序

快速排序算法 void quicksort (sqlist r, int s, int t) { int i=s, j=t; if (s<t) do r[0] =r[s]; /*r[0]暂存选出的数据*/ while( j>1 && r[j].key >=r[0].key) j--; if (i<j) r[i]=r[j]; i++; } 快速排序算法 第七章 排序

快速排序算法续 while (i<j && r[i].key <=r[0].key) i++; if (i<j) { r[j]=r[i]; j--; } }while (i<j); r[i]=r[0]; quicksort(r,s,j-1); /*递归处理前一部分*/ quicksort(r,j+1,t); /*递归处理后一部分*/ 快速排序算法续 第七章 排序

快速排序分析 快速排序的时间复杂性为O(nlogn)，对n较大的情况，这种算法是平均情况速度最快的排序算法，但当n很小时，此方法往往比其他简单排序方法还要慢。 快速排序是不稳定的，对于有相同关键字的记录，排序以后次序可能会颠倒。 返回 第七章 排序

7.5 归并排序 归并是指将若干个已排序好的有序表合并成一个有序表。两个有序表的归并称为二路归并。 归并排序就是利用归并过程，开始时先将n个数据看成n个长度为1的已排好序的表，将相邻的表成对合并，得到长度为2的（n/2）个有序表，每个表含有2个数据；进一步再将相邻表成对合并，得到长度为4的（n/4）个有序表；……；如此重复做下去，直至所有数据均合并到一个长度为n的有序表为止，就完成了排序。 第七章 排序

图7.9 二路归并排序 第七章 排序

下面是将两个有序表归并的函数Merge，设待归并的两个表存于数组r中，其中一个的数据安排在下标从m到n单元中，另一个安排在下标从（n+1）到h单元中，归并后得到的一个有序表，存入辅助数组r2中。归并过程是依次比较这两个有序表中相应的数据，按照“取小”原则复制到r2之中即可。 第七章 排序

归并排序算法 void merge (sqlist r, r2, int m, n, h) { int i, j, k; k=m; i=m; j=n+1; /* k为r2的指示器，i,j分别为两个有序表的指示器*/ while ( i<=n && j<=h) if (r[i].key <= r[j].key) r2[k]=r[i]; i++; } 归并排序算法 第七章 排序

归并排序算法续 else { r2[k]=r[j]; j++; } k++; if (i>n) while (j<=h) 归并排序算法续 第七章 排序

j++; k++; } else while (i<=n) { r2[k]=r[i]; i++; 归并排序算法续 第七章 排序

图7.10 两个有序表的归并 第七章 排序

上面的函数只是归并两个有序表,在进行二路归并的每一趟归并过程中是将多对相邻的表进行归并。 现在讨论一趟的归并。设已将数组r中的n个数据分成一对对长度为s的有序表，要求将这些表两两归并，归并成一些长度为2s的有序表，并把结果置入辅助数组r2中。 第七章 排序

如果n不是2s的整数倍，虽然前面进行归并的表长度均为s，最后不可能再剩下一对长度都是s的表，此时可有两种情况： 一种情况是剩下一个长度为s的表和一个长度小于s的表，由于上述的归并函数merge并不要求待归并的两个表必须长度相同，仍可将二者归并，只是归并后的表的长度小于其它表的长度2s； 再一种情况是只剩下一个表，它的长度小于或等于s，由于没有另一个表与它归并，只能将它直接抄到数组r2中，准备参加下一趟的归并。 第七章 排序

一趟归并的函数 void mergepass (sqlist r, r2, int n, s) { int i, t; i=1; /*i为每一对待合并有序表的第一单元下标，初值为1*/ while ( i<=n-2*s+1) merge(r, r2, i, i+s-1, i+2*s-1); i=i+2*s /*i向后移2s，准备下一次归并*/ } 第七章 排序

一趟归并的函数续 if (i+s-1<n) merge(r, r2, i, i+s-1,n); /*一个长度为s的表与一个长度小于s的表合并*/ else /*只剩下一个长度不大于s的表*/ for (t=i; t=n; t++) r2[t]=r[t]; } 第七章 排序

二路归并排序函数 void mergesort (sqlist r, int n) { sqlist r2; int s=1; while (s<n) mergepass (r, r2,n,s); s=2*s; mergepass (r2, r,n,s); } 第七章 排序

归并排序分析 二路归并排序的时间复杂性为O(nlogn)，与堆排序和快速排序平均情况的时间复杂性是相同数量级。 归并排序是稳定的排序方法。 返回 第七章 排序

7.6 基数排序 基数排序(Radix sort)最初是用于在卡片排序机上处理穿孔卡片的一种排序方法。基数排序是采用“分散”的办法排序。 设每张卡片对应着一个多位数的关键字，在卡片排序机中对卡片进行多趟“分散”过程，每一趟逐张检查卡片关键字的某一位数，将此位数取值相同的卡片放入同一片盒中。 一趟“分散”过程结束后，在此排列基础上，再进行下一趟检查另一位数的“分散”。 对关键字的检查从低位到高位进行，到检查最高位的一趟“分散”过程结束，最后将卡片“收集”起来即排序完毕。 第七章 排序

设一组关键字的个数为n（即卡片的张数），每个关键字的位数为d，每位数可能有rd种取值，则这种排序方法需进行d趟“分散”，每趟检查n张卡片的某一位数，并按此位数值的不同，将卡片分别放到rd个卡片盒中。 每位数可能取值的数目rd称为基数(Radix)，例如对于十进制数的每一位可能有0到9十种取值，故基数为10；而二进制的每一位数只能有0和1两种取值，则基数为2。 图7.11所示为基数排序过程的一个例子。 第七章 排序

图7.11 基数排序 第七章 排序

第七章 排序

第七章 排序

为每个“盒”设置一个链接队列，并将各队列的队首和队尾指针分别存于两个一维数组中。 开始时，将原始数据构成一个链接队列，设各“盒”的队列均为空队列。然后将原始数据队列中各结点，按所考虑的关键字某位数的值插入到相应“盒”的队列中去。 当一趟结束时，再把各“盒”的队列依次首尾相连，链接成一个链接队列，以此作为下一趟的输入。 如此反复进行，直至做完d趟，即排序结束。 第七章 排序

数据类型 设基数排序中记录的数据类型如下： struct element { int key[d]; /*d为关键字的位数*/ int next; }; element rsqlist[n]; 第七章 排序

基数排序算法 void radixsort (rsqlist r, int d, int n,int p) { /*d为关键字的位数，n为待排序的数据个数，p指向链表中的第一个结点*/ int i,j,t; int f[rd], e[rd]; /*队列的头、尾指示器，rd是基数，十进制为10*/ for (i=1; i<=n-1; i++) r[i].next=i+1; r[n].next=0; p=1; /*原始数据串成静态链表，头指针为p*/ 第七章 排序

基数排序算法续 for ( i=d; i>0; i--) /*从关键字的最后一位开始*/ { for (j=0; j<rd; j++) f[j]=0; /* 队列指示器置初值*/ while (i!=0) /*进行分配*/ t=r[p].key[i]; if (f[t]==0) f[t]=p; else r[e[t]].next=p; 第七章 排序

基数排序算法续 e[t]=p; p=r[p].next; } j=0; while (f[j]==0) j++; /*寻找第一个非空队列*/ p=f[j]; t=e[j]; while (j<rd) 第七章 排序

基数排序算法续 { j++; if (f[j]!=0) r[t].next=f[j]; t=e[j]; } /*进行收集*/ } 第七章 排序

图7.12 初始状态 现以图7.11所示的三位十进制数序列306，028，009，948，505，917，721，430，390为例说明radixsort函数的执行过程。 第七章 排序

第一趟分配后各队列情况 第七章 排序

第七章 排序

第一趟收集后的情况 第七章 排序

第三趟分配后各队列情况 第七章 排序

第七章 排序

第三趟收集后的情况 第七章 排序

基数排序分析 采用基数排序需进行d趟关键字的分散和收集过程，每趟运算时间为O(n+rd)，故总的时间复杂性为O(d(n+rd))。若基数rd相同，对于关键字数目较多但位数较少的情况，采用基数排序较为适用。 基数排序是稳定的排序方法。 返回 第七章 排序

例7.1 已知序列{60,20,31,1,5,44,55,61,200,30,80,150,4,29},写出采用快速排序算法排序的每一趟的结果。 第七章 排序

例7.1解答 解: 快速排序各趟的结果如下: [60 20 31 1 5 44 55 61 200 30 80 150 4 29] [29 20 31 1 5 44 55 4 30] 60 [80 150 200 61] [4 20 5 1] 29 [44 55 31 30] 60 [61] 80 [200 150] [1] 4 [5 20] 29 [30 31] 44 [55] 60 61 80 150 [200] 1 4 5 [20] 29 30 [31] 44 55 60 61 80 150 200 1 4 5 20 29 30 31 44 55 60 61 80 150 200 第七章 排序

例7.2 已知序列{26,5,77,1,61,11,59,15,48,19}写出采用归并排序算法排序的每一趟的结果。 解: 快速排序各趟的结果如下: [26] [5] [77] [1] [61] [11] [59] [15] [48] [19] [5 26] [1 77] [11 61] [15 59] [19 48] [1 5 26 77 ] [11 15 59 61] [19 48] [1 5 11 15 26 59 61 77] [19 48] [1 5 11 15 19 26 48 59 61 77] 第七章 排序

例7.3 设计一个用单链表作存储结构的选择排序算法。 解:依题义单链表定义如下: struct node { int key; struct node *next; }; 第七章 排序

实现本题功能的函数如下: void select(node *head) { node *p,*q,*min; int temp; p=head; while(p!=NULL) min=p; q=p->next; while(q!=NULL) 第七章 排序

if(q->key<min->key) min=q; } temp=p->key; { if(q->key<min->key) min=q; } temp=p->key; p->key=min->key; min->key=temp; p=p->next; 返回 第七章 排序

小 结 排序 冒泡排序 直接选择排序 简单插入排序 堆排序 快速排序 归并排序 基数排序 返回 第七章 排序

习题与练习 一、基本知识题 1. 解释下列概念 (1) 排序 (2) 内部排序 (3) 堆 (4) 稳定排序 2. 回答下面问题 (1) 5000个无序的数据，希望用最快速度挑选出其中前10个最大的元素，在快速排序、堆排序、归并排序和基数排序中采用哪种方法最好？为什么？ (2) 大多数排序算法都有哪两个基本操作？ 第七章 排序

3. 已知序列{17，25，55，43，3，32，78，67，91}，请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。 4. 已知序列{491，77，572，16，996，101，863，258，689，325}，请分别给出采用快速排序、堆排序和基数排序法对该序列作递增排序时每一趟的结果。 5. 已知序列{86，94，138，62，41，54，18，32}，请给出采用插入排序法对该序列作递增排序时，每一趟的结果。 6. 已知序列{27，35，11，9，18，30，3，23，35，20}，请给出采用归并排序法对该序列作递增排序时的每一趟的结果。 第七章 排序

二、算法设计题 1. 一个线性表中的元素为全部为正或者负整数，试设计一算法，在尽可能少的时间内重排该表，将正、负整数分开，使线性表中所有负整数在正整数前面。 2. 设计一个用单链表作存储结构的直接插入排序算法。 3. 试设计一个算法实现双向冒泡排序。（双向冒泡排序就是在排序的过程中交替改变扫描方向。） 4. 设一个一维数组A[n]中存储了n个互不相同的整数，且这些整数的值都在0到n-1之间，即A中存储了从0到n-1这n个整数。试编写一算法将A排序，结果存放在数组B[n]中，要求算法的时间复杂性为O(n)。 返回 第七章 排序