希爾排序的簡單概念，希爾排序的時間複雜度是什麼

希爾排序的時間複雜度是什麼?

1樓：胡鬧鬧旅遊

希爾排序時間複雜度是 o(n^(，空間複雜度為常數階 o(1)。希爾排序沒有時間複雜度為 o(n(logn)) 的快速排序算模廳數法。

快，因此對中等大小規模表現良好，但對規模非常大的資料排序不是最優選擇，總之比一般 o(n^2 ) 複雜度的演算法快得多。希爾排序(shell sort

是插入排序的一種，它是針對直接插入排序演算法的改進。

概念及其伏粗介紹：希爾排旦首序又稱縮小增量排序，因於 1959 年提出而得名。它通過比較相距一定間隔的元素來進行，各趟比較所用的距離隨著演算法的進行而減小，直到只比較相鄰元素的最後一趟排序為止。

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

希爾排序的思想

2樓：教育之家

希爾排序演算法思想：希爾排序是按照下標增量進行分組，對每組使用插入排序演算法進行排序，隨著增量減少，每組包含的關鍵字越來越多，增量減到1時，整個序列被分為一組，演算法終止。

我們以增序排序為例，希爾排序基本步驟：選擇初始增量gap=length/2，縮小增量繼續以gap=gap/2的方式進行，直到增量gap=1為止，增量的每次變化都會將原始序列劃分為若干組，分別對每一組進行插入排序。

每一次通過增量劃分組進行插入排序巨集觀上小的數移到了前面，大的數移歷廳激到了後面，最後增量gap=1進行插入排序後就是最終的有序序列。

由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。

發展歷史

希爾伏啟排序按其設計者希爾（donald shell）的名字命名，該演算法由希爾在1959年所發表的**「a high-speed sorting procedure」中所描述。

1961年，ibm公司的女程式設計師marlene metzner norton（瑪琳·梅茨納·諾頓）首次使用fortran語言程式設計實現了希爾排序演算法。在其程式中使用了一種簡易有效的方法設定希爾排序所需的增量序列：第乙個增肢襪量取待排序記錄個數的一半，然後逐次減半，最後乙個增量為1。

該演算法後來被稱為shell-metzner演算法，metzner本人在2003年的一封電子郵件中說道：「我沒有為這種演算法做任何事，我的名字不應該出現在演算法的名字中。」

希爾排序的組內排序採用的是

3樓：手可彈棉花啊

希爾排序。的組內使用的是直接插入排序。

希爾排序的思想是：先將待排元素序列分割成若干個子序列（由相隔某個「增量」的元素組成），分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。

簡單來說，希爾排序又叫遞減增量排序演算法。

它是在直接插入排序演算法的基礎上進行改進而來的，綜合來說它的效率肯定是要高於直接插入排序演算法的；希爾排序是一種不穩定的排序演算法。

直接插入排序的兩種性質：

1、當待排序的原序列中大多數元素都已有序的情況下，此時進行的元素比較和移動的次數較少；

2、當原序列的長度很小時，即便它的所有元素都是無序的，此時進行的元素比較和移動的次數還是很少。