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

更新時間：2017年05月12日 16:44:45 投稿：lqh

這篇文章主要介紹了C++ 算法之希爾排序算法詳解及實例的相關(guān)資料,需要的朋友可以參考下

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

希爾排序算法

定義：

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

算法思想：

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

時間復(fù)雜度：

O(N)

空間復(fù)雜度：

O(1)

性能：

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

優(yōu)勢：

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

缺點：

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

代碼實現(xià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; 
}

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章:

相關(guān)文章

c++字符串分割的方法
這篇文章主要介紹了c++字符串分割的方法，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下
2020-08-08
C++實現(xiàn)LeetCode(90.子集合之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(90.子集合之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
2021-07-07
這篇文章主要介紹了MFC程序?qū)ξ募奶幚矸椒?需要的朋友可以參考下
2014-08-08