文章目錄

• • 復習概要
  • 算法思想
  • 算法流程
  • 算法復雜度分析及穩(wěn)定性
  • 希爾排序代碼正常版
  • 希爾排序與插入排序代碼對比
  • 希爾排序個人青春版（別看以免走上歧途）

復習概要

算法思想與流程

分這么多組分別插入排序有什么用？為什么不直接整個插入排序？

時間復雜度

優(yōu)化

要眼熟插入排序那一段的代碼，和原本的插入排序對比著看！

插入排序那一段多了一層循環(huán)是干什么的，怎么是三層循環(huán)？

希爾的步長序列生成方式？

算法思想

我覺得完全沒必要按照行和列的思想去理解希爾排序

因為一句話概括希爾排序就是，每隔幾個元素一組，分組進行插入排序，然后重新分組，直到每個元素都是一組

內(nèi)層先標記這是第幾組，然后就是最簡單的插入排序思想，只不過是對同一組（列）里的元素的插入排序，請想象元素之間的距離變成stepSequence了，不是1了，而且組的第一個元素索引是col（第幾組，初始為0）不是0了，第一個無序元素的位置就是col+stepSequence了，把所有組分別進行插入排序就結束了

外層就是不斷縮小分組所需的步長（元素增量），然后循環(huán)內(nèi)層

步長：就是隔幾個一組

建議和普通插入排序的代碼結合著看，很容易就理解了

話說希爾排序居然是用發(fā)明者名字命名的

希爾排序比之間插入排序強的地方是，總共處理的逆序對數(shù)量比直接插入排序少了，每次分組排序同時會解決一些額外的逆序對。

算法流程

輸入數(shù)組： 29 15 12 10 9 8 7 6 5 3 2 1 希爾排序正常版 (每隔幾個元素就取出一個看作一組)(也就是列)步長為6,每組有l(wèi)ength/步長 個元素 [29] 15 12 10 9 8 [7] 6 5 3 2 1 7 [15] 12 10 9 8 29 [6] 5 3 2 1 7 6 [12] 10 9 8 29 15 [5] 3 2 1 7 6 5 [10] 9 8 29 15 12 [3] 2 1 7 6 5 3 [9] 8 29 15 12 10 [2] 1 7 6 5 3 2 [8] 29 15 12 10 9 [1] 7 6 5 3 2 1 29 15 12 10 9 8 (每隔幾個元素就取出一個看作一組)(也就是列)步長為3 [7] 6 5 [3] 2 1 [29] 15 12 [10] 9 8 3 [15] 12 7 [9] 8 10 [6] 5 29 [2] 1 3 2 [12] 7 6 [8] 10 9 [5] 29 15 [1] 3 2 1 7 6 5 10 9 8 29 15 12 (每隔幾個元素就取出一個看作一組)(也就是列)步長為1 [3] [2] [1] [7] [6] [5] [10] [9] [8] [29] [15] [12] 1 2 3 5 6 7 8 9 10 12 15 29

算法復雜度分析及穩(wěn)定性

希爾排序最好時間復雜度和插入排序相同為O（n）

最壞時間復雜度和平均時間復雜度取決于步長序列

希爾本人的步長序列生成法（length/2的k次冪）最壞時間復雜度為O（n2），目前最好的最壞時間復雜度的步長序列生成法可以做到O（n的4/3次方），如下，k=1，2，3.。。。注意是最壞時間復雜度（even代表奇數(shù)，odd代表偶數(shù)）

希爾排序不穩(wěn)定，空間復雜度O（1），為原地算法

希爾排序代碼正常版

//產(chǎn)生步長序列（按照希爾本人的生成方式） void stepSequenceGenerator(vector<int> array, vector<int> &stepSequence) {for (int i = 2; i < array.size(); i = i * 2){stepSequence.push_back(array.size() / i);} }void sort(vector<int> array, int stepSequence) {//col：當前是第幾組（列）for (int col = 0; col < stepSequence; col++){//下面其實就是最簡單的插入排序的代碼，只不過是對同一組（列）里的元素的插入排序//請想象元素之間的距離變成stepSequence了，不是1了，而且組的第一個元素索引是col不是0了，第一個無序元素的位置就是col+stepSequence了for (int chaosBeginIndex = col + stepSequence; chaosBeginIndex < array.size(); chaosBeginIndex = chaosBeginIndex + stepSequence){for (int insertEIndex = chaosBeginIndex; insertEIndex > col; insertEIndex = insertEIndex - stepSequence){if (array[insertEIndex] < array[insertEIndex - stepSequence]){int temp = array[insertEIndex];array[insertEIndex] = array[insertEIndex - stepSequence];array[insertEIndex - stepSequence] = temp;}}}vectorPrint(array);} }void shellSort(vector<int> &array) {vector<int> stepSequence;stepSequenceGenerator(array, stepSequence);for (int i = 0; i < stepSequence.size(); i++){cout << "(每隔幾個元素就取出一個看作一組)(也就是列)步長為" << stepSequence[i] << endl;sort(array, stepSequence[i]);} } 輸入數(shù)組： 29 15 12 10 9 8 7 6 5 3 2 1 希爾排序正常版 (每隔幾個元素就取出一個看作一組)(也就是列)步長為6 7 15 12 10 9 8 29 6 5 3 2 1 7 6 12 10 9 8 29 15 5 3 2 1 7 6 5 10 9 8 29 15 12 3 2 1 7 6 5 3 9 8 29 15 12 10 2 1 7 6 5 3 2 8 29 15 12 10 9 1 7 6 5 3 2 1 29 15 12 10 9 8 (每隔幾個元素就取出一個看作一組)(也就是列)步長為3 3 15 12 7 9 8 10 6 5 29 2 1 3 2 12 7 6 8 10 9 5 29 15 1 3 2 1 7 6 5 10 9 8 29 15 12 (每隔幾個元素就取出一個看作一組)(也就是列)步長為1 1 2 3 5 6 7 8 9 10 12 15 29 算法用時：（微秒） [AlgoTime: 12002 us]

希爾排序與插入排序代碼對比

void sort2nd(vector<int> array, int stepSequence) {//col：當前是第幾組（列）for (int col = 0; col < stepSequence; col++){//下面其實就是最簡單的插入排序的代碼，只不過是對同一組（列）里的元素的插入排序//請想象元素之間的距離變成stepSequence了，不是1了，而且組的第一個元素索引是col不是0了，第一個無序元素的位置就是col+stepSequence了for (int chaosBeginIndex = col + stepSequence; chaosBeginIndex < array.size(); chaosBeginIndex = chaosBeginIndex + stepSequence){for (int insertEIndex = chaosBeginIndex; insertEIndex > col; insertEIndex = insertEIndex - stepSequence){if (array[insertEIndex] < array[insertEIndex - stepSequence]){int temp = array[insertEIndex];array[insertEIndex] = array[insertEIndex - stepSequence];array[insertEIndex - stepSequence] = temp;}}}vectorPrint(array);} }void insertionSort1th(vector<int> &array) //這里以數(shù)組左側作為有序的那一邊 {// chaosBeginIndex：未排序序列的起始元素下標// insertEIndex：拿去插入有序序列的那個元素的下標，就是未排序序列的起始元素，但隨著交換位置，下標會改變for (int chaosBeginIndex = 1; chaosBeginIndex < array.size(); chaosBeginIndex++)//外循環(huán)控制從第二個元素開始插入到有序序列里，直到最后一個元素{for (int insertEIndex = chaosBeginIndex; insertEIndex > 0; insertEIndex--)//內(nèi)循環(huán)控制從未排序序列的首元素開始，逐漸與有序序列元素比較和交換位置，找到有序序列中的合適位置{if (array[insertEIndex] < array[insertEIndex - 1]){int temp = array[insertEIndex];array[insertEIndex] = array[insertEIndex - 1];array[insertEIndex - 1] = temp;}else{break;}}vectorPrint(array);} }

希爾排序個人青春版（別看以免走上歧途）

看輸出就能看出來，我改寫了插入排序，可以自由選擇一段進行插入排序，然后又建了一個空容器，把元素按組排序壓入容器，然后覆蓋主數(shù)組，但是毫無意義，看輸出就知道，把一組元素放到一起又會導致不同組之間產(chǎn)生新的逆序對

void insertionSort1th(vector<int> &array, int begin, int end) //這里以數(shù)組左側作為有序的那一邊 {// chaosBeginIndex：未排序序列的起始元素下標// insertEIndex：拿去插入有序序列的那個元素的下標，就是未排序序列的起始元素，但隨著交換位置，下標會改變for (int chaosBeginIndex = begin + 1; chaosBeginIndex <= end; chaosBeginIndex++)//外循環(huán)控制從第二個元素開始插入到有序序列里，直到最后一個元素{for (int insertEIndex = chaosBeginIndex; insertEIndex > begin; insertEIndex--)//內(nèi)循環(huán)控制從未排序序列的首元素開始，逐漸與有序序列元素比較和交換位置，找到有序序列中的合適位置{if (array[insertEIndex] < array[insertEIndex - 1]){int temp = array[insertEIndex];array[insertEIndex] = array[insertEIndex - 1];array[insertEIndex - 1] = temp;}else{break;}}} }void sort(vector<int> &array, int stepSequence) {vector<int> temp;for (int j = 0; j < stepSequence; j++){int i = 0;for (int index = j; index < array.size(); index = index + stepSequence){temp.push_back(array[index]);i = i + 1;}insertionSort1th(temp, temp.size() - i, temp.size() - 1);vectorPrint(temp);}array = temp; }void shellSort(vector<int> &array) {vector<int> stepSequence;stepSequenceGenerator(array, stepSequence);for (int i = 0; i < stepSequence.size(); i++){cout << "(每隔幾個元素就取出一個看作一組)(也就是列)步長為" << stepSequence[i] << endl;sort(array, stepSequence[i]);} } 輸入數(shù)組： 29 15 12 10 9 8 7 6 5 3 2 1 希爾排序個人青春版 (每隔幾個元素就取出一個看作一組)(也就是列)步長為6 7 29 7 29 6 15 7 29 6 15 5 12 7 29 6 15 5 12 3 10 7 29 6 15 5 12 3 10 2 9 7 29 6 15 5 12 3 10 2 9 1 8 (每隔幾個元素就取出一個看作一組)(也就是列)步長為3 3 7 9 15 3 7 9 15 1 5 10 29 3 7 9 15 1 5 10 29 2 6 8 12 (每隔幾個元素就取出一個看作一組)(也就是列)步長為1 1 2 3 5 6 7 8 9 10 12 15 29 算法用時：（微秒） [AlgoTime: 9002 us]

總結

以上是生活随笔為你收集整理的希尔排序（缩小增量排序）（插入排序的优化版） C++代码实现及算法分析 恋上数据结构笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。