插入排序(1)直接插入排序：直接插入排序的基本操作是将当前无序区的第1个记录R[i]插入到有序区R[0..i-1]中适当的位置上,使R[0..i]变为新的有序区
(2)希尔排序：取一个小于n的整数d1(一般为n/2)，作为第一个增量,将n个记录分成d1个子序列，所有距离为d1的倍数放在同一组中，在组中进行直接插入排序，然后取第二个变量(一般为d1/2),重复上述步骤，直到增量为1，即所有记录放在同一组中进行直接插入排序为止。举例说明： S:9 8 7 6 5 4 3 2 1 0第一次，d=5 4 3 2 1 0 9 8 7 6 5 分为5个子序列,进行子序列直接插入排序，{9,4}{8,3}{7,2}{6,1}{5,0}第二次，d=2 0 1 2 3 4 5 6 7 8 9 分为两个子序列，进行子序列直接插插入排序，{4,2,0,8,6}{3,1,9,7,5}第三次，d=1 0 1 2 3 4 5 6 7 8 9
注意：这里分为子序列并不是取出重新存储，而是在原来的位置上进行子序列的直接插入排序
仔细分析下：d=5时，S:9 8 7 6 5 4 3 2 1 0
[9] (8) {7} <6> /5/ [4] (3) {2} <1> /0/
相同符号包含的是同一子序列，即{S[0],S[5]}, {S[1],S[6]}, {S[2],S[7]}, {S[3],S[8]}, {S[4],S[9]}分别为子序列
进行直接插入排序,S[0]>S[5],则交换S[0] = 4，S[5] = 9
S[1]>S[6],则交换S[1] = 3, S[6] = 8......
得到排列: 4 3 2 1 0 9 8 7 6 5.
d=d/2=2;
d=2时，S: 4 3 2 1 0 9 8 7 6 5
[4] (3) [2] (1) [0] (9) [8] (7) [6] (5) S[0],S[2],S[4],S[6],S[8]为一个子序列，进行直接插入排序后，为S[0]=0,S[2]=2,S[4]=4,S[6]=6,S[8]=8.
同样，S[1]S[3]S[5]S[7]S[9]为另一个子序列，进行直接插入排序后为:S[1]=1,S[3]=3,S[5]=5,S[7]=7,S[9]=9.
得到排列，0 1 2 3 4 5 6 7 8 9
再下来就是d=1,同理。效率分析：
直接插入排序：最好情况，只需比较n-1次，移动0次；最坏情况，比较(n)(n-1)/2次,时间复杂度为o(n^2),希尔排序：平均时间复杂度O(log2n)代码如下：UNIX环境 2011-02-11
#include <stdio.h> #include <string.h> #include <stdlib.h> void directInsert(int a[], int len)//按增序排序 { int i,j,temp; for(i = 1; i < len; i++) { j = i-1;//从右向左比较 temp = a[i]; while(j >= 0 && temp < a[j]) { a[j+1] = a[j];//将关键字大的后移 j--; } a[j+1] = temp; } } void ShellSort(int a[], int len) { int i, j, d, temp; d = len/2; while(d > 0) { for(i = d; i < len; i++) { j = i-d; while(j >= 0 && a[j] > a[j+d]) { temp = a[j]; a[j] = a[j+d]; j = i - d; } } d = d/2; } } void print(int a[], int len) { int i; for(i = 0; i < len; i++) printf("%d/n",a[i]); } int main(int argc, char *argv[]) { int len; int a[]={9,8,7,6,5,4,3,2,1,0}; len = sizeof(a)/sizeof(int); directInsert(a, len); print(a, len); printf("#########ShellSort##########/n"); ShellSort(a, len); print(a, len); return 0; }
