????????希爾排序是插入排序的一種，又稱縮小增量排序，是直接插入排序的一種更高效改進版本，要知道什么是希爾排序首先要理解直接插入排序。

插入排序

? ? ? ? 直接插入排序，有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序，時間復雜度為O(n^2)。?

????舉個例子：是把第一個數看成有序的，然后第二個數跟第一個數比較，比第一個數小則交換位置（插入到第一個數前面），然后前兩個是有序的，如果第三個數比第二個數小，就和第二數交換，交換和后再和第一個數交換，如果比第一個小，就和第一個數交換，否則就不動了，后面再有數就還是按照這種方法，如果比他前一個數大就放這兒不動了，如果比前一個數小，就和前一個換位置，再往前比，直到不比前一個數小就停。

插入排序基思想

插入排序

希爾排序基本思想：

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

????????簡單插入排序很循規(guī)蹈矩，不管數組分布是怎么樣的，依然一步一步的對元素進行比較，移動，插入，而希爾排序在數組中采用跳躍式分組的策略，通過某個增量將數組元素劃分為若干組，然后分組進行插入排序，隨后逐步縮小增量，繼續(xù)按組進行插入排序操作，直至增量為1。希爾排序通過這種策略使得整個數組在初始階段達到從宏觀上看基本有序，小的基本在前，大的基本在后。然后縮小增量，到增量為1時，其實多數情況下只需微調即可，不會涉及過多的數據移動。

希爾排序基本思想

希爾排序