《第10章 内排序》由会员分享，可在线阅读，更多相关《第10章 内排序（90页珍藏版）》请在金锄头文库上搜索。
1、第10章 内 排 序,10.6 基数排序,10.1 排序的基本概念,10.2 插入排序,10.3 交换排序,10.4 选择排序,10.5 归并排序,10.7 各种内排序方法的比较和选择,10.1 排序的基本概念 所谓排序，是要整理表中的记录，使之按关键字递增（或递减）有序排列。其确切定义如下： 输入：n个记录,R0,R1,Rn-1,其相应的关键字分别为k0,k1,kn-1。 输出：Ri,0,Ri,1,Ri,n-1,使得ki,0ki,1ki,n-1 (或ki,0ki,1ki,n-1)。,本章仅考虑递增排序,当待排序记录的关键字均不相同时，排序的结果是惟一的,否则排序的结果不一定唯一。如果待排序的
2、表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的；反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。,在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。,算法的稳定性,内排序和外排序,内排序的基本方法,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,正序和反序若待排序的表中元素已按关键字排好序，称此表中元素为正序；
3、反之，若待排序的表中元素的关键字顺序正好和排好序的顺序相反，称此表中元素为反序。,排序的分类根据排序算法是否基于关键字的比较，将排序算法分为基于比较的排序算法和不基于比较的排序算法。像插入排序、交换排序、选择排序和归并排序都是基于比较的排序算法；而基数排序是不基于比较的排序算法。,待排序的顺序表类型的类型定义如下： typedef int KeyType; /定义关键字类型 typedef struct /记录类型 KeyType key; /关键字项 InfoType data; /其他数据项,类型为InfoType RecType; /排序的记录类型定义,存放数据的结构：,10.2 插入排
4、序 插入排序的基本思想是：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。 两种插入排序方法： （1）直接插入排序（含二分插入排序） （2）希尔排序,10.2.1 直接插入排序 假设待排序的记录存放在数组R0.n-1中，排序过程的某一中间时刻，R被划分成两个子区间R0.i-1和Ri.n-1，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。 直接插入排序的基本操作是将当前无序区的第1个记录Ri插入到有序区R0.i-1中适当的位置上，使R0.i变为新的有序区。这种方法通常称为增量法，因为它每次使有序区
5、增加1个记录。,R0,j,Ri,j=i-1,插入位置,在有序区中插入Ri的过程,void InsertSort(RecType R,int n) /对R0.n-1按递增有序进行直接插入排序 int i,j;RecType temp; for (i=1;i=0 /在j+1处插入Ri ,例10.1 设待排序的表有10个记录，其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用直接插入排序方法进行排序的过程。,对于直接插入排序：,最好的情况（关键字在记录序列中顺序有序）：,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）：,“比较”的次数：,2(n-1),“移动”的次数：,“移动
6、”的次数：,总的平均比较和移动次数约为,直接插入排序算法稳定性证明：另外，当ij且Ri.key=Rj.key时，本算法将Ri插入在Rj的后面，使Ri和Rj的相对位置保持不变，所以直接插入排序是一种稳定的排序方法。, Rj Ri ,有序区,Ri插入在Rj的后面,10.2.2 折半插入排序,查找采用折半查找方法，称为二分插入排序或折半插入排序。void InsertSort1(RecType R,int n)int i,j,low,high,mid; RecType tmp; for (i=1;i=high+1;j-)/记录后移 Rj+1=Rj;Rhigh+1=tmp;/插入 ,折半插入排序的元素
7、移动次数与直接插入排序相同，不同的仅是变分散移动为集合移动。在R0.i-1中查找插入Ri的位置，折半查找的平均关键字比较次数为log2(i+1)-1，平均移动元素的次数为i/2+2，所以平均时间复杂度为：,就平均性能而言，折半查找优于顺序查找，所以折半插入排序也优于直接插入排序。折半插入排序的空间复杂度为O(1)。,10.2.3 希尔排序 希尔排序也是一种插入排序方法,实际上是一种分组插入方法。 基本思想： 先取定一个小于n的整数d1作为第一个增量，把表的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序； 然后取第二个增量d2（d1），重复上述的分组和排
8、序，直至所取的增量dt=1（dtdt-1d20) for (i=gap;i=0 /减小增量 ,例10.2 设待排序的表有10个记录,其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用希尔排序方法进行排序的过程。,希尔排序的时间复杂度约为O(n1.3)。为什么希尔排序比直接插入排序好？例如：有10个元素要排序。,希尔排序,直接插入排序,大约时间=102=100,d=5：分为5组，时间约为5*2220,d=2：分为2组，时间约为2*5250,d=1：分为1组，几乎有序，时间约为10,80,希尔排序算法不稳定的反例希尔排序法是一种不稳定的排序算法。例如，若希尔排序分为两组：3,10,7,
9、8,20和5,8,2,1,6，显然，第1组的8排列在第2组的8的后面，两组采用直接插入排序后的结果为：3,7,8,10,20和1,2,5,6,8，这样第1组的8排列到第2组的8的前面，它们的相对位置发生了改变。,思考题：希尔排序中的有序区是全局有序吗？,10.3 交换排序 交换排序的基本思想：两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。 两种交换排序: （1）冒泡排序 （2）快速排序,10.3.1 冒泡排序 冒泡排序的基本思想：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。 整个算法是从最下
10、面的记录开始，对每两个相邻的关键字进行比较,且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。,void BubbleSort(RecType R,int n) int i,j;RecType temp; for (i=0;ii;j-) /比较找本趟最小关键字的记录 if (Rj.keyRj-1.key) temp=Rj; /Rj与Rj-1进行交换 Rj=Rj-1; Rj-1=temp; , 全局有序区 Ri Rn-1,用交换找最小记录放到Ri处,
11、例10.3 设待排序的表有10个记录,其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用冒泡排序方法进行排序的过程。,思考题：冒泡排序中的有序区是全局有序吗？,在有些情况下，在第i（in-1）趟时已排好序了，但仍执行后面几趟的比较。实际上，一旦算法中某一趟比较时不出现记录交换，说明已排好序了，就可以结束本算法。 为此得到改进冒泡排序算法如下：,void BubbleSort(RecType R,int n) int i,j; bool exchange;RecType temp; for (i=0;ii;j-)/比较,找出最小关键字的记录 if (Rj.keyRj-1.key) t
12、emp=Rj; Rj=Rj-1;Rj-1=temp; exchange=true; if (exchange=false) return; /中途结束算法 ,最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟冒泡,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟冒泡,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,n-1,10.3.2 快速排序 快速排序是由冒泡排序改进而得的。 基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它
13、大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位)，这个过程称作一趟快速排序。,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,无 序 的 记 录 序 列,无序记录子序列(1),无序子序列(2),基准,一次划分,分别进行快速排序,需要确定排序的序列，采用什么存储结构？,s,t,low,high,设 Rs=52 为枢轴,将 Rhigh.key 和基准的关键字进行比较，要求Rhigh.key 基准的关键字,将 Rlow.key 和基准的关键字进行比较，要求Rlow.key 基准的关键字,high,23,low,80,high,14,low,52,
