《数据结构第11章内排序》由会员分享，可在线阅读，更多相关《数据结构第11章内排序（64页珍藏版）》请在金锄头文库上搜索。
1、第11章 内 排 序11.6 基数排序本章小结11.1 排序的基本概念 11.2 插入排序11.3 交换排序 11.4 选择排序11.5 归并排序11.7 各种内排序方法的比较和选择11.1 排序的基本概念 所谓排序，就是要整理表中的记录，使之按关键字递增(或递减)有序排列。其确切定义如下：输入：n个记录，R0,R1,Rn-1，其相应的关键字分别为k0,k1,kn-1。输出：Rp0,Rp1,Rpn-1，使得kp0kp1kpn-1（或kp0kp1kpn-1)。当待排序记录的关键字均不相同时，排序的结果是惟一的，否则排序的结果不一定惟一。如果待排序的表中具有相同关键字的记录之间的相对次序经过排序后
2、保持不变，则称这种排序方法是稳定的；反之，则称这种排序方法是不稳定的。在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；反之,若排序过程中要进行数据的内、外存交换，则称之为外排序。 待排序的顺序表类型的类型定义如下：typedef int KeyType; /*定义关键字类型*/typedef struct /*记录类型*/KeyType key; /*关键字项*/InfoType data; /*其他数据项,类型为 InfoType*/ RecType; /*排序的记录类型定义*/ 内部排序的方法内部排序的过程是一个逐步扩大记录的有序 序列范围的过程。
3、基于不同的“扩大” 有序序列范围的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法1. 插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。l直接插入排序lshell排序2. 交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。l冒泡排序l快速排序3. 选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。l直接选择排序l堆排序4. 归并类通过“归并”两个或两个以上的记录有序子序列，逐步增
4、加记录有序序列的长度。5. 其它方法如：基数排序11.2 插入排序基本思想：每次将一个待排序的记录，按其关键字大小插 入到前面已经排好序的子表中的适当位置，直到全 部记录插入完成为止。两种插入排序方法：(1)直接插入排序(2)希尔排序。11.2.1 直接插入排序假设待排序的记录存放在数组R0n-1中，排序过程的某一中间时刻，R被划分成两个子区间:R0i-1：已排好序的有序区，Rin-1：当前未排序的部分，不妨称其为无序 区。有序序列区无 序 序 列 区有序序列区无 序 序 列 区例 设待排序的表有10个记录，其关键字分别为 9,8,7,6,5,4,3,2,1,0。采用直接插入排序方法进行排序
5、的过程如下: 94 38 72160598 7void InsertSort(RecType R,int n) /*对R0n-1按递增有序进行直接插入排序*/ int i,j;RecType temp;for (i=1;i=0 i=0 /*Rj与Rj+d交换*/Rj=Rj+d;Rj+d=temp;j=j-d;d=d/2; /*递减增量d*/ 例11.2 设待排序的表有10个记录，其关键字分别为 9,8,7,6,5,4,3,2,1,0。说明采用希尔排序方法进行排序的过程。11.3 交换排序交换排序的基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换， 直到没有反序的记录为止
6、。两种交换排序:(1)冒泡排序(2)快速排序11.3.1 冒泡排序基本思想：通过无序区中相邻记录关键字间的比较和位置的 交换，使关键字最小的记录如气泡一般逐渐往上“漂浮” 直至“水面”。整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较，且使关键字较小的记录换至关键字较 大的记录之上，使得经过一趟冒泡排序后，关键字最小 的记录到达最上端，接着，再在剩下的记录中找关键字 次小的记录，并把它换在第二个位置上。依次类推，一 直到所有记录都有序为止。1987654329876543209876543201987654013201239876549876501234012345987601234
7、56987109801234567void BubbleSort(RecType R,int n) int i,j;RecType temp;for (i=0;ii;j-)/*比较找本趟最小关键字的记录*/if (Rj.keyi;j-)/*比较,找出最小关键字的记录*/if (Rj.keyi if (i=1;i-) /*循环建立初始堆*/sift(R,i,n); for (i=n;i=2;i-) /*进行n-1次循环,完成推排序*/ temp=R1; /*将第一个元素同当前区间内R1对换*/R1=Ri;Ri=temp;sift(R,1,i-1); /*筛选R1结点,得到i-1个结点的堆*/建堆
8、是一个从下往上进行“筛选”的过程。40554973816436122798例如: 排序之前的关键字序列为123681734998817355现在，左/右子树都已经调整为堆，最后只要调整 根结点，使整个二叉树是个“堆”即可。98494064361227 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 988149735564122740是大顶堆12但在 98 和 12 进行互换之后，它就不是堆了。因此，需要对它进行“筛选”98比较9836例11.6 设待排序的表有10个记录,其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行排序的过程。堆排
9、序过程：11.5 归并排序归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。 将两个有序表直接归并为一个有序表的算法Merge() ：例 设待排序的表有8个记录，其关键字分别为 18,2,20,34,12,32,6,16。说明采用归并排序方法进 行排序的过程。 18 2 20 3412 32 6 16第1趟218 203412 32 6 16第2趟2182034 6121632第3趟2 61216 18203234一次归 并merge一趟归并 mergepass二路归并 mergesortvoid Merge(RecType R,
10、int low,int mid,int high) RecType *R1;int i=low,j=mid+1,k=0; /*k是R1的下标,i、j分别为第1、2段的下标*/R1=(RecType *)malloc(high-low+1)*sizeof(RecType);while (i=0;i-) /*从低位到高位做d趟排序*/ for (j=0;jdatai-0; /*找第k个链队*/ if (headk=NULL) /*进行分配,即采用尾插法建立单链表*/ headk=p; tailk=p; else tailk-next=p; tailk=p; p=p-next; /*取下一个待排序的
11、元素*/ 分 配p=NULL;for (j=0;jnext=headj;t=tailj; t-next=NULL;/*最后一个结点的next域置NULL*/ 收 集例11.8 设待排序的表有10个记录，其关键字分别为 75,23,98,44,57,12,29,64,38,82。说明采用基数排序方法进行排序的过程。 75 23 98 44 57 12 29 64 38 82 head0 head1 head2 head3 head4 head5 head6 head7 head8 head9 tail0tail1tail2tail3tail4tail5tail6tail7tail8tail912
12、82 23 75 57 29 4464 9838 12 82 23 44 64 75 57 98 38 29 head0 head1 head2 head3 head4 head5 head6 head7 head8 head9 tail0tail1tail2tail3tail4tail5tail6tail7tail8tail912 23 29 38 44 57 64 75 82 98 12 29 2338 75 98 44 57 64 82 12 82 23 44 64 75 57 98 38 29 11.7 各种内排序方法的比较和选择本章介绍了多种排序方法，将这些排序方法总结为表11.1。
13、通常可按平均时间将排序方法分为三类：（1）平方阶O(n2)排序，一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶O(nlog2n)排序，如快速、堆和归并排序；（3）线性阶O(n)排序，如基数排序。 排序方法时间复杂度空间复杂度稳定性复杂性 平均情况最坏情况最好情况直接插入排 序O(n2)O(n2)O(n)O(1)稳定简单希尔排序O(nlog2n)O(nlog2n) O(1) 不稳定较复杂冒泡排序O(n2)O(n2)O(n)O(1) 稳定简单快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不稳定较复杂直接选择排 序O(n2)O(n2)O(n2)O(1)
14、 不稳定简单堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1) 不稳定较复杂归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定较复杂基数排序O(d(n+r)O(d(n+r)O(d(n+r)O(n+r)稳定较复杂本章小结本章基本学习要点如下：(1) 理解排序的基本概念,包括排序的稳定性、内排序和外排序之间的差异。(2) 重点掌握插入排序算法,包括直接插入排序和希尔排序的过程和算法实现。(3) 重点掌握交换排序算法,包括冒泡排序和快速排序的过程和算法实现。(4) 重点掌握选择排序算法,包括直接选择排序和堆排序的过程和算法实现。(5) 掌握归并排序的过程和算法实现。(6) 掌握基数排序的过程和算法实现。(7) 灵活运用各种排序算法解决一些综合应用问题。
