希尔排序：将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，即使用直接插入排序，使最终数组成为有序。

1. /********************************************************
   
2. *函数名称：ShellInsert
   
3. *参数说明：pDataArray 无序数组；
   
4. *          d          增量大小
   
5. *                   iDataNum为无序数据个数
   
6. *说明：    希尔按增量d的插入排序
   
7. *********************************************************/
   
8. void ShellInsert(int* pDataArray, int d, int iDataNum)
   
9. {
   
10.         for (int i = d; i < iDataNum; i += 1)    //从第2个数据开始插入
    
11.         {
    
12.                 int j = i - d;
    
13.                 int temp = pDataArray[i];    //记录要插入的数据
    
14.                 while (j >= 0 && pDataArray[j] > temp)    //从后向前，找到比其小的数的位置
    
15.                 {
    
16.                         pDataArray[j+d] = pDataArray[j];    //向后挪动
    
17.                         j -= d;
    
18.                 }
    
19. 
    
20.                 if (j != i - d)    //存在比其小的数
    
21.                         pDataArray[j+d] = temp;
    
22.         }
    
23. }
    
24. 
    
25. /********************************************************
    
26. *函数名称：ShellSort
    
27. *参数说明：pDataArray 无序数组；
    
28. *                   iDataNum为无序数据个数
    
29. *说明：    希尔排序
    
30. *********************************************************/
    
31. void ShellSort(int* pDataArray, int iDataNum)
    
32. {
    
33.         int d = iDataNum / 2;    //初始增量设为数组长度的一半
    
34.         while(d >= 1)
    
35.         {
    
36.                 ShellInsert(pDataArray, d, iDataNum);
    
37.                 d = d / 2;    //每次增量变为上次的二分之一
    
38.         }
    
39. }

复制代码

学习了············

增量设二分之一会不太稳定，我试过呢

JarryHorse 发表于 2015-4-22 20:55
增量设二分之一会不太稳定，我试过呢

那设多少比较稳定呢

帅的惊动党中央 发表于 2015-4-23 07:56
那设多少比较稳定呢

呃···希尔本身就是个不稳定的算法，增量变化越小越稳定，比如···1