2、C语言程序 void InsertSort(Data Type all, int n) /*用直接插入法对a[0]-a[n-1排序* f int i,]; Data Type temp for(=0;i<n-1;i++){ temp=a[计+1]; while(>-1 & temp. key <all key)i aj+1=all alj+1= temp
6 2、C语言程序 void InsertSort(DataType a[], int n) /*用直接插入法对a[0]--a[n-1]排序*/ { int i, j; DataType temp; for(i = 0; i < n-1; i++) { temp = a[i+1]; j = i; while(j > -1 && temp.key < a[j].key) { a[j+1] = a[j]; j--; } a[j+1] = temp; } }
7
7 void main(void) { DataType test[6]={64,5,7,89,6,24}; int i, n = 6; SeqList myList; ListInitiate(&myList); for(i = 0; i < n; i++) ListInsert(&myList, i, test[i]); InsertSort(myList.list, myList.size); for(i=0; i<n; i++) printf("%d ", myList.list[i].key); } #include <stdio.h> typedef int KeyType; typedef struct {KeyType key; } DataType; #define MaxSize 100 #include "SeqList.h
3、直接插入排序算法分析 (1)时间效率:因为在最坏情况下,所有元素的比较次数总 和为(0+1+…+n-1)→0(n2)。其他情况下也要 考虑移动元素的次数。故时间复杂度为o(n2) (2)空间效率:仅占用1个缓冲单元0(1) (3)算法的稳定性:稳定 希尔(she11)排序(又称缩小增量排序 1、基本思想:把整个待排序的数据元素分成若干个小组,对同 小组内的数据元素用直接插入法排序;小组的个数逐次缩小, 当完成了所有数据元素都在一个组内的排序后排序过程结束。 2、技巧:小组的构成不是简单地“逐段分割”,而是将相隔某 个增量dk的记录组成一个小组,让增量dk逐趟缩短(例如依次取 5,3,1),直到dk=1为止。 3、优点:让关键字值小的元素能很快前移,且序列若基本有序 时,再用直接插入排序处理,时间效率会高很多
8 (1)时间效率： 因为在最坏情况下，所有元素的比较次数总 和为（0＋1＋…＋n-1)→O(n2 )。其他情况下也要 考虑移动元素的次数。 故时间复杂度为O(n2 ) (2)空间效率：仅占用1个缓冲单元——O（1） (3)算法的稳定性：稳定 3、直接插入排序算法分析 二、希尔（shell）排序（又称缩小增量排序） 1、基本思想：把整个待排序的数据元素分成若干个小组，对同 一小组内的数据元素用直接插入法排序；小组的个数逐次缩小， 当完成了所有数据元素都在一个组内的排序后排序过程结束。 2、技巧：小组的构成不是简单地“逐段分割”，而是将相隔某 个增量dk的记录组成一个小组,让增量dk逐趟缩短（例如依次取 5,3,1），直到dk＝1为止。 3、优点：让关键字值小的元素能很快前移，且序列若基本有序 时，再用直接插入排序处理，时间效率会高很多
例2:设待排序的序列中有1个记录,它们的关键字序列T=(65, 34,25,87,12,38,56,46,14,77,92,23),请写出 希尔排序的具体实现过程 算法分析:开始时d的值较大,子序列中的对象较少,排序速度 较快;随着排序进展,d值逐渐变小,子序列中对象个数 逐渐变多,由于前面工作的基础,大多数记录已基本有序 所以排序速度仍然很快。 通常,d+1=d2(结果取整) 时间效率:O(m(log2n)2 空间效率:0(1)—因为仅占用1个缓冲单元 算法的稳定性:不稳定 下面给出希尔排序的具体实现过程:
9 例2：设待排序的序列中有12个记录，它们的关键字序列 T=(65， 34，25，87，12，38，56，46，14，77，92，23），请写出 希尔排序的具体实现过程。 算法分析：开始时d 的值较大，子序列中的对象较少，排序速度 较快；随着排序进展，d 值逐渐变小，子序列中对象个数 逐渐变多，由于前面工作的基础，大多数记录已基本有序， 所以排序速度仍然很快。 通常，di+1=di/2 (结果取整） 时间效率：O(n(log2n)2 ) 空间效率：O（1）——因为仅占用1个缓冲单元 算法的稳定性：不稳定 下面给出希尔排序的具体实现过程：
第1趟(d=6) 77 结果序列5 12 第2趟(d=3) 6546 结果序列56 14 46 87 92 (b 第3趟(d=1)【511684274625893 结果序列12 (c
10 65 34 25 87 12 38 56 46 14 77 92 23 结果序列 56 34 14 77 12 23 65 46 25 87 92 38 56 34 14 77 12 23 65 46 25 87 92 38 结果序列 56 12 14 65 34 23 77 46 25 87 92 38 56 12 14 65 34 23 77 46 25 87 92 38 结果序列 12 14 23 25 34 38 46 56 65 77 87 92 (a) (b) (c) 第1趟 (d=6) 第2趟 (d=3) 第3趟 (d=1)