算法分析 (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< span; k++) /共span个小组 组内是直接插入排序,区别是每次不是增1而是增span for(i=k;i< n-span; i=i+span) {temp=a[i计span}; whiled>-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 < numOfD; m++) //共numOfD次循环 { span = d[m]; //取本次的增量值 for(k = 0; k < span; k++) //共span个小组 { //组内是直接插入排序，区别是每次不是增1而是增span for(i = k; i < n-span; i = i+span) { temp = a[i+span]; j = i; while(j > -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) 希尔排序的排序过程