思路

  • 希尔排序使用一个序列h1, h2, ···, ht，叫做增量序列。只要h1 = 1，任何增量序列都是可行的。
  • 在使用增量hk的一趟排序后，对于每一个位置i，有A[i] ≤ A[i + k]，即所有间隔hk的元素都是已排序的。此时称文件是hk-排序的。
  • 一个hk-排序的文件保持它的hk-排序性。一般做法是，对于hk, hk + 1, ···, N - 1中对应的每一个位置i，把其上的元素放到i, i - hk, i - 2hk, ···中间的正确位置上。
  • 一趟hk排序的作用就是对hk个独立的子数组执行一次插入排序。
  • 流行的增量序列：
    • 希尔排序 - 图1
    • 希尔排序 - 图2

时间复杂度

  • o(N²)

代码

  1. public int[] SortAsc(int[] arr, int Length)
  2. {
  3.     for (int Step = Length / 2; Step > 0; Step /= 2)
  4.     {
  5.         for (int i = Step; i < Length; i++)
  6.         {
  7.             var tmp = arr[i];
  8.             int j = i;
  9.             for (; j >= Step; j -= Step)    //j >= Step 防止j -= Step时造成j - Step为负数。换句话说即：当j逐渐减小时，若比Step下标小，
  10.                                             //则意味着上一个j表示的元素已经是该组插入排序的第一个元素
  11.             {
  12.                 if (arr[j - Step] > tmp) arr[j] = arr[j - Step];
  13.                 else break;
  14.             }
  15.             arr[j] = tmp;
  16.         }
  17.     }
  19.     return arr;
  20. }