希尔排序 C++ or Java

希尔排序其实就是改进版的插入排序。插入排序在处理原本有序数量少的组合时非常快，反之速度就比较慢。因此我们想让插入排序分组处理数据，让插入排序每次处理较少的值。我们可以每隔等长的数据为一组，然后逐渐改变这个间隔长度，使之逐渐减少。这样数组会逐渐变得有序，充分发挥插入排序的优点。下面请看代码：

C++：

void shell_sort(int a[], int length)
{
   int gab = length >> 1;
   while (gab)
   {
      for (int i = gab; i < length; i = i + gab)
      {
         int j = i - gab;
         int temp = a[i];
         while (j >= 0 && temp < a[j])
         {
            a[j + gab] = a[j];
            j = j - gab;
         }
         a[j + gab] = temp;
      }
      gab = gab >> 1;
   }
}

Java：

public static void shell_sort(int a[]) {
      int length = a.length;
      int gab = length >> 1;
      while (gab != 0) {
         for (int i = gab; i < length; i = i + gab) {
            int j = i - gab;
            int temp = a[i];
            while (j >= 0 && temp < a[j]) {
               a[j + gab] = a[j];
               j -= gab;
            }
            a[j + gab] = temp;
         }
         gab = gab >> 1;
      }
   }