排序算法---插入排序

1.直接插入排序

 1 void insetSort(int *arr, int n)
 2 {
 3     int i, j, k;
 4     
 5     for(i = 1; i < n; i++)
 6     {
 7         for(j = i - 1; j >= 0; j--)
 8         {
 9             if(arr[j] < arr[i])
10             {
11                 break;
12             }
13         }
14         
15         if(j != i - 1)
16         {
17             int temp = arr[i];
18             
19             for(k = i - 1; k > j; k--)
20             {
21                 arr[k + 1] = arr[k];
22             }
23             
24             arr[k + 1] = temp;
25         }
26     }
27 }

2.希尔排序

 1 void insetSort(int *arr, int n, int dk)
 2 {
 3     int i, j, k;
 4     
 5     for(i = dk; i < n; i++)
 6     {
 7         for(j = i - dk; j >= 0; j -= dk)
 8         {
 9             if(arr[j] < arr[i])
10             {
11                 break;
12             }
13         }
14         
15         if(j != i - dk)
16         {
17             int temp = arr[i];
18             
19             for(k = i - dk; k > j; k -= dk)
20             {
21                 arr[k + dk] = arr[k];
22             }
23             
24             arr[k + dk] = temp;
25         }
26     }
27 }
28 
29 void shellSort(int *arr, int n)
30 {
31     int dk = 0;
32     
33     dk = n >> 1;
34     while(dk >= 1)
35     {
36         insetSort(arr, n, dk);
37         dk = dk >> 1;
38     }
39 
40 }

　　当希尔排序的步长为1时，就等同于直接插入排序。