插入排序之五 希尔排序

Admin

希尔排序（Shell’s Sort）又称“缩小增量排序”（Diminishing Increment Sort），它也是一种属于插入排序类的方法，但在时间效率上较前述几种排序方法有较大的改进。时间复杂度为O(n^3/2)。理解：先将整个待排记录序列分割成为若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

1. void CInsertionSort::ShellSort(void)
   
2. {
   
3.     const int count = 9, length = count -1;
   
4.     int L[count] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
   
5.     const int t = 3;
   
6.     int dlta[t] = {3, 2 , 1};
   
7.     for (int k = 0; k < t; ++k)
   
8.     {
   
9.         ShellInsert(L, length, dlta[k]);
   
10.     }
    
11.     //打印排序结果。
    
12.     for (int i = 0; i <= length; ++ i)
    
13.     {
    
14.         cout << L[i] << "\t";
    
15.     }
    
16.     cout << endl;
    
17. }
    
18. 
    
19. 
    
20. void CInsertionSort::ShellInsert(int L[], int length, int dk)
    
21. {
    
22.     for (int i = dk + 1; i <= length; ++ i)
    
23.     {
    
24.         if (L[i] < L[i - dk])
    
25.         {
    
26.             L[0] = L[i];
    
27.             int j = i - dk;
    
28.             while (j > 0 && L[0] < L[j])
    
29.             {
    
30.                 L[j + dk] = L[j];
    
31.                 j -= dk;
    
32.             }
    
33.             L[j + dk] = L[0];
    
34.         }
    
35.     }
    
36. }

复制代码

和直接排序差不多，只不过是先三三比较，再两两比较，即第一轮[4]和[1]比较，[5]和[2]，[6]和[3]，[7]和[4]，[8]和[5]。简单来说是这样来比较，复杂来说，这只是第一轮的第一次比较，如果符合条件还会进行第一轮的第二次比较。即for循环的while子循环。把数值代进来用大脑跑一下就OK了。

xywv1

好好好好好好好好好好

hunme

Shell’s Sort）又称“缩小增量排序”