C++ 算法之希爾排序詳解及實例

2020-01-26 14:09:14

字體：大中小

來源：轉載

供稿：網友

C++ 算法之希爾排序算法詳解及實例

希爾排序算法

定義：

希爾排序是插入排序的一種，也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。

算法思想：

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序，隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰好被分為一組，算法終止。

時間復雜度：

O(N)

空間復雜度：

O(1)

性能：

希爾排序為不穩定算法（一次插入排序是穩定的，不會改變相同元素的相對順序，但是在不同的插入排序中，相同的元素可能在各自的插入排序中移動，會打亂其穩定性）

優勢：

希爾排序不需要大量的輔助空間，比直接插入排序時間要快，并且代碼很好實現。

缺點：

雖然希爾排序相對于直接插入排序要優化很多，但是O（N）的算法依舊效率不是很高，并且希爾排序不穩定。

代碼實現：

#include <iostream> #include <Windows.h> #include <assert.h>  using namespace std;  //希爾排序,從小到大排 void ShellSort(int* arr, int len)  {   assert(arr);   int gap = 3;   //先給一個初始組間距，gap為1時即為直接插入排序   for (gap = 3; gap > 0; --gap)  //不斷縮小組間距，直到gap=1   {     for (int i = 0; i < len; ++i)        {       for (int j = i + gap; j < len; j = j + gap)       {         if (arr[j-gap] > arr[j])         {           int temp = arr[j];  //將arr[j]處的值先保存起來           arr[j] = arr[j-gap];           arr[j-gap] = temp;         }       }     }   } }

#include "ShellSort.h"  void TestShellSort() {   int arr[] = { 100, 2,888, 6, 10, 5, 3, 666, 78, 9, 10000, 45, 67, 33 };   int len = sizeof(arr) / sizeof(arr[0]);   cout << "未排序序列：" << "";   for (int i = 0; i < len; ++i)   {     cout << arr[i] << "->";   }   cout << endl;   ShellSort(arr, len);   cout << "已排序序列：" << "";   for (int j = 0; j < len; ++j)   {     cout << arr[j] << "->";   }   cout << endl; }  int main() {   TestShellSort();   system("pause");   return 0; }