[ 資料結構 -- 手撕排序算法第三篇 ] 希爾排序

手撕排序算法系列之：希爾排序。

從本篇文章開始，我會介紹并分析常見的幾種排序，大緻包括插入排序，冒泡排序，希爾排序，選擇排序，堆排序，快速排序，歸并排序等。

 本篇主要來手撕希爾排序~~ 

目錄

1.常見的排序算法

2.希爾排序

3.希爾排序實作代碼

4.希爾排序測試

5.希爾排序的時間複雜度

6.希爾排序和直接插入排序效率測試

7.希爾排序特性總結​

1.常見的排序算法

1.1 插入排序基本思想

直接插入排序是一種簡單的插入排序法，其基本思想是：

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。

實際中我們玩撲克牌時，就用了插入排序的思想

2.希爾排序

2.1希爾排序（縮小增量排序）

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先標明一個整數gap，把待排序檔案中所有記錄分成個組，所有距離相差gap的記錄分在同一組内，并對每一組内的記錄進行排序。然後，取gap = gap/3+1重複上述分組和排序的工作。當gap到達=1時，所有記錄在統一組内排好序。

畫圖分析： 

如上圖所示，如果我們要預設升序排序：

2.1.1預排序階段

1、在第一趟的時候，我們取gap = 5，此時9和4,1和8,2和6,5和3,7和5分到了一組，然後我們在每組之内進行比較，如果前面的數字大于後面的數字，就交換，此時每組中較小的數字就被交換到前面，較大的數字沒交換到了後面。

2、在第二趟的時候，我們取gap = gap/3+1（除以三是一個普遍的寫法，這裡的重點是為什麼要+1，這是因為如果gap小于3的情況下，gap/3會讓gap=0,此時就會陷入死循環），這時gap= 2，4和2,5,8,5分到了一組，1,3,9,6,7分到了一組。此時，在一組内，進行排序，這一組就有序。

2.1.2插入排序階段

3、待gap = 1得時候，我們就是用插入排序，這時候經過之前的預排階段，整個數組已經變得大緻有序了，較大的數字都會被移到後面，較小的數字都會移到前面，此時是用插入排序，效率就會很高。

2.2單趟希爾排序

2.2.1思路分析

單趟希爾排序就是将差為gap的數字分為一組，較大的放在後面，較小的放在前面

for (int i = 0; i < n - gap; ++i)//++i  可以直接讓多組同時進行交換(隻是少寫個循環但是不提高任何效率)
  {
    int end = i;
    int tmp = a[end + gap];
    while (end >= 0)
    {
      if(tmp < a[end])
      { 
        a[end + gap] = a[end];
        end -= gap;
      }
      else
      {
        break;
      }
    }
    a[end + gap] = tmp;
  }      

具體插入排序的思想大家可以參考博文：​​[ 資料結構 -- 手撕算法第一篇 ]插入排序​​

3.希爾排序實作代碼

在單趟排序的基礎上，加上一個gap循環即可

void ShellSort(int* a, int n)
{
  //1.gap > 1  預排序
  //2.gap == 1 直接插入排序
  int gap = n;
  while (gap > 1)
  {
    gap = gap / 3 + 1;//後面 +1 保證當gap小于3時能讓gap == 1
    for (int i = 0; i < n - gap; ++i)//++i  可以直接讓多組同時進行交換(隻是少寫個循環但是不提高任何效率)
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        if(tmp < a[end])
        { 
          a[end + gap] = a[end];
          end -= gap;
        }
        else
        {
          break;
        }
      }
      a[end + gap] = tmp;
    }
  }
}      

4.希爾排序測試

void ShellSort(int* a, int n)
{
    //1.gap > 1  預排序
    //2.gap == 1 直接插入排序
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;//後面 +1 保證當gap小于3時能讓gap == 1
        for (int i = 0; i < n - gap; ++i)//++i  可以直接讓多組同時進行交換(隻是少寫個循環但是不提高任何效率)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if(tmp < a[end])
                { 
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

//希爾排序
void TestShellSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    ShellSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
    //希爾排序
    TestShellSort();

    return 0;
}      

測試結果：

5.希爾排序的時間複雜度

希爾排序的時間複雜度不好計算，因為gap的取值方法很多，導緻很難去計算，是以在好些書中給出的希爾排序的時間複雜度都不固定。

但是我們可以将希爾排序的時間複雜度相比較直接插入排序進行分析，在最壞情況下野就是逆序排順序，假設有N個數字。直接插入排序的時間複雜度是O(n)，但是如果使用希爾排序此時進行分組時候每個組組進行排序，在最後gap=1時時間複雜度可以認為是O(n)，是以結合起來希爾排序的時間複雜度是肯定小于O(n^2)。

但是希爾排序在一種情況下也是存在缺點的，這種情況下就是原數組本身有序，那直接插入排序的時間複雜度是O(N)，而使用希爾排序在gap>1的時候進行預排序其實是沒有作用的，但是計算機是不知道的，還是會做一遍預排序，當gap = 1的時候在直接插入排序。是以時間複雜度是大于O(N）。但是這畢竟是少數情況，大多數排序都是随機數組或是逆序排順序。

為了更好的比較希爾排序和直接插入排序的效率，我們可以生成一組随機數進行比較檢視他們所消耗的時間。

以下是兩本書中對希爾排序時間複雜度的描述：

因為我們的gap是按照Knuth提出的方式取值的，而且Knuth進行了大量的試驗統計，我們暫時就按照：

來算。

6.希爾排序和直接插入排序效率測試

6.1測試

我們建立一個數組，數組的元素個數有100000個，讓其數字全部随機生成，我們通過希爾排序和直接插入排序分别對這個數組進行排序。觀察他們所消耗的時間。

//時間對比
void TestOP()
{
  srand(time(0));
  const int N = 100000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);

  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
  }

  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();

  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();


  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);

  free(a1);
  free(a2);
}

int main()
{
  TestOP();
  return 0;
}      

6.2結論

6.2.1随機生成數

通過結果我們能夠發現，在100000個數字下，希爾排序的效率遠遠高于直接插入排序。

我們也可以改變數組大小再測試測試

 我們能夠發現當數組越大時，希爾排序比直接插入排序的效率越高。

6.2.2有序數組

 當我們讓數組變得有序我們再檢視結果：

 正如我們所分析的那樣，當數組本身有序時，希爾排序的預排序階段就會不起作用，此時希爾排序的效率不及直接插入排序。

7.希爾排序特性總結

希爾排序的特性總結：

1. 希爾排序是對直接插入排序的優化。

2. 當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。我們實作後可以進行性能測試的對比。

3. 希爾排序的時間複雜度不好計算，因為gap的取值方法很多，導緻很難去計算，是以在好些書中給出的希爾排序的時間複雜度都不固定。