排序_希尔排序

 1 void shellSort(LineList R[], int n)
 2 {
 3     int i, j, d;
 4     d = n / 2;
 5 
 6     while (d > 0)
 7     {
 8         for (i = d + 1; i <= n; i++)
 9         {
10             if (R[i].key < R[i - d].key)
11             {
12                 R[0].key = R[i].key;
13                 for (j = i - d; j > 0 && R[0].key < R[j].key; j = j - d)
14                 {
15                     R[j + d] = R[j];
16                 }
17                 R[j + d] = R[0];
18             }
19         }
20         d = d / 2;
21     }
22 }

下标从0开始的算法如下：

 1 void insertSort(ElementType A[], int N)
 2 {
 3     int p, i;
 4     ElementType tmp;
 5 
 6     /* 希尔增量序列 */
 7     for (D = N / 2; D > 0; D /= 2)
 8     {
 9         /* 插入排序 */
10         for (p = D; p < N; p++)
11         {
12             tmp = A[p];
13             for (i = p; i >= D && A[i - D] > tmp; i -= D)
14             {
15                 A[i] = A[i - D];
16             }
17 
18             A[i] = tmp;
19         }
20     }
21 }

另外还有sedgewick序列的方法

 1 void ShellSort( ElementType A[], int N )
 2 { 
 3      /* 希尔排序 - 用Sedgewick增量序列 */
 4      int Si, D, p, i;
 5      ElementType tmp;
 6 
 7      /* 这里只列出一小部分增量 */
 8      int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
 9       
10      for ( Si = 0; Sedgewick[Si] >= N; Si++ ) 
11          ; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
12  
13      for ( D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si] )
14     {
15         /* 插入排序*/
16          for ( p = D; p < N; p++ ) 
17         { 
18              tmp = A[P];
19              for ( i = p; i >= D && A[i - D] > tmp;  i -= D )
20             {
21                  A[i] = A[i-D];
22             }
23              A[i] = tmp;
24          }
25     }
26 }