第10章排序 排序的基本概念 主插入排序 要」选择排序 识交换排序归并排序 点基数排序 性能比较
第10章 排序 排序的基本概念 插入排序 选择排序 交换排序归并排序 基数排序 性能比较 主 要 知 识 点
101排序的基本概念 排序是对数据元素序列建立某种有序排列的过程是把一个数据 元素序列整理成按关键字递增(或递减)排列的过程。 关键字是要排序的数据元素集合中的一个城,排序是以关键字 为基准进行的。 主关键字:数据元素值不同时该关键字的值也一定不同,是能够 惟一区分各个不同数据元素的关键字;不满足主关键字定义的关 键字称为次关键字。 内部排序是把待排数据元素全部调入内存中进行的排序 外部排序是因数量太大,把数据元素分批导入内存,排好序后 再分批导出到磁盘和磁带外存介质上的排序方法
10.1 排序的基本概念 排序是对数据元素序列建立某种有序排列的过程,是把一个数据 元素序列整理成按关键字递增（或递减）排列的过程。 关键字是要排序的数据元素集合中的一个域，排序是以关键字 为基准进行的。 主关键字:数据元素值不同时该关键字的值也一定不同，是能够 惟一区分各个不同数据元素的关键字;不满足主关键字定义的关 键字称为次关键字。 内部排序是把待排数据元素全部调入内存中进行的排序。 外部排序是因数量太大，把数据元素分批导入内存，排好序后 再分批导出到磁盘和磁带外存介质上的排序方法
比较排序算法优劣的标准: (1)时间复杂度它主要是分析记录关键字的比较次数和记录的 移动次数 (2)空间复杂度:算法中使用的内存辅助空间的多少 (3)稳定性:若两个记录A和B的关鍵字值相等,但排序后A、B 的先后次序保持不变,则称这种排序算法是稳定的
比较排序算法优劣的标准: (1)时间复杂度:它主要是分析记录关键字的比较次数和记录的 移动次数 (2)空间复杂度 :算法中使用的内存辅助空间的多少 (3)稳定性:若两个记录A和B的关键字值相等，但排序后A、B 的 先后次序保持不变，则称这种排序算法是稳定的
10.2插入排序 插入排序的基本思想是:每步将一个待排序的数据元素,按 其关键码大小,插入到前面已经排好序的一组数据元素的适当 位置上,直到数据元素全部插入为止。 常用的插入排序有直接插入排序和希尔排序两种 1直接插入排序 其基本思想是: 顺序地把待排序的数据元素按其关键字值的大小插入到 已排序数据元素子集合的适当位置
10.2插入排序 插入排序的基本思想是：每步将一个待排序的数据元素，按 其关键码大小，插入到前面已经排好序的一组数据元素的适当 位置上，直到数据元素全部插入为止。 1.直接插入排序 常用的插入排序有直接插入排序和希尔排序两种。 其基本思想是： 顺序地把待排序的数据元素按其关键字值的大小插入到 已排序数据元素子集合的适当位置
算法如下: void InsertSort DataType all, int n) /用直接插入法对a0-a{m-排序 int l, Data Type temp; for(i=0;i-1 & temp key aljkey t aj+1=aljl a[j+1]=temp;
算法如下： void InsertSort (DataType a[], int n) //用直接插入法对a[0]--a[n-1]排序 { int i, j; DataType temp; for(i=0; i -1 && temp.key < a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp; } }
算法分析 (1)时间效率:因为在最坏情况下,所有元素的比较次数总 和为(0+1+…+n-1)→O(m2)。其他情况下也要 考虑移动元素的次数。故时间复杂度为O(m2) (2)空间效率:仅占用1个附加内存单元0(1) (3)算法的稳定性:稳定
算法分析: (1)时间效率： 因为在最坏情况下，所有元素的比较次数总 和为（0＋1＋…＋n-1)→O(n2 )。其他情况下也要 考虑移动元素的次数。 故时间复杂度为O(n 2 ) (2)空间效率：仅占用1个附加内存单元——O(1) (3)算法的稳定性：稳定
初始关键字序列 89 第一次排序: 89 第二次排序: 5 7 64} 89 24 第三次排序: {5 64 6 24 第四次排序: 第五次排序 {5 6 7 24 89} 直接插入排序过程
{64} 7 89 6 24 {5 64} 89 6 24 {5 7 64} 6 24 {5 7 64 89} 24 {5 6 7 64 89} {5 6 7 24 64 89} 5 89 6 24 初始关键字序列: 第一次排序: 第二次排序: 第三次排序: 第四次排序: 第五次排序: 7 直接插入排序过程
2希尔(shel)排序(又称缩小增量排序) (1)基本思想:把整个待排序的数据元素分成若千个小咀组,对同 -小组内的数据元素用直接插入法排序;小组的个数逐次缩小, 当完成了所有数据元素都在一个组内的排序后排序过程结束。 (2)技巧:小组的构成不是简单地“逐段分割”,而是将相隔某 个增量d的记录组成一个小组让增量d逐趟缩短(例如依次取 5,3,1),直到dk=1为止 (3)优点:让关键字值小的元素能很快前移,且序列若基本有序 时,再用直接插入排序处理,时间效率会高很多
2.希尔(shell)排序(又称缩小增量排序) (1)基本思想：把整个待排序的数据元素分成若干个小组，对同 一小组内的数据元素用直接插入法排序；小组的个数逐次缩小， 当完成了所有数据元素都在一个组内的排序后排序过程结束。 (2)技巧：小组的构成不是简单地“逐段分割”，而是将相隔某 个增量dk的记录组成一个小组,让增量dk逐趟缩短（例如依次取 5,3,1），直到dk＝1为止。 (3)优点：让关键字值小的元素能很快前移，且序列若基本有序 时，再用直接插入排序处理，时间效率会高很多
算法如下: void ShellSort Data Type all, int n, int dn int numOD) /用希尔排序法对元素a0-an-1排序,dI0- dumont-1为希尔增量值 int i,j, k, m, span; Data Type temp; for(m=0; m numOfD; m++) 共 numofl次循环 span=dmi /取本次的增量值 for(k=0; k-1 && temp. key a[jl.key) aj+span =ajl J=J-span; mp
算法如下： void ShellSort (DataType a[], int n, int d[], int numOfD) //用希尔排序法对元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]为希尔增量值 { int i, j, k, m, span; DataType temp; for(m = 0; m -1 && temp.key < a[j].key) { a[j+span] = a[j]; j = j-span; } a[j+span] = temp; } } } }
65 34 25 87 12 46 结果序列=656 (a) 12 65 87 结果序列=356 23 87 38 16342425879—3 结果序列=11214232534384656 92 希尔排序的排序过程
65 34 25 87 12 38 56 46 14 77 92 23 结果序列d=6 56 34 14 77 12 23 65 46 25 87 92 38 56 34 14 77 12 23 65 46 25 87 92 38 结果序列d=3 56 12 14 65 34 23 77 46 25 87 92 38 56 12 14 65 34 23 77 46 25 87 92 38 结果序列d=1 12 14 23 25 34 38 46 56 65 77 87 92 (a) (b) (c) 希尔排序的排序过程