基本思想
先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把待排序的全部記錄分成dx個(gè)組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插人排序。然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序。直至所取的增量dt=1(dt<dt-x<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?p>算法實(shí)現(xiàn)希爾排序算法，java實(shí)現(xiàn)，代碼如下所示：
public abstract class Sorter { public abstract void sort(int[] array); } public class ShellSorter extends Sorter { @Override public void sort(int[] array) { int d = array.length; do { d /= 2; shellPass(array, d); // 根據(jù)逐漸減小的間隔增量，循環(huán)調(diào)用一趟排序 } while (d > 1); } /** * 希爾一趟排序 * @param d 間隔增量 */ PRivate void shellPass(int[] array, int d) { Integer tmp; for (int i = d; i < array.length; i++) { // 數(shù)組下標(biāo)從0開(kāi)始，初始i=d表示一趟排序中第二個(gè)元素 tmp = array[i]; // array[i]的拷貝 // 如果待處理的無(wú)序區(qū)第一個(gè)元素array[i] < 有序區(qū)最大的元素array[i-d] // 需要將有序區(qū)比array[i]大的元素向后移動(dòng) if (array[i] < array[i - d]) { int j = i - d; while (j >= 0 && tmp < array[j]) { array[j + d] = array[j]; // 將左側(cè)有序區(qū)中元素比array[i]大的array[j+d]后移 j -= d; } // 如果array[i] >= 左側(cè)有序區(qū)最大的array[i-d]，或者經(jīng)過(guò)掃描移動(dòng)后，找到一個(gè)比array[i]小的元素 // 將右側(cè)無(wú)序區(qū)第一個(gè)元素tmp = array[i]放到正確的位置上 array[j + d] = tmp; } } } }排序過(guò)程
希爾排序的過(guò)程如下：
首先初始化間隔d為待排序數(shù)組的長(zhǎng)度，無(wú)需排序。減小d，對(duì)于每次得到的間隔d，執(zhí)行多組排序，使得原始數(shù)組間隔為d的一個(gè)子數(shù)組為有序，該數(shù)組通過(guò)類(lèi)似直接插入排序的算法來(lái)執(zhí)行排序。直到，d減小為1的時(shí)候，整個(gè)數(shù)組為有序。這里，采用二分的策略來(lái)得到間隔d。下面通過(guò)例子來(lái)說(shuō)明，執(zhí)行希爾排序的過(guò)程，如下所示：假設(shè)待排序數(shù)組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數(shù)組大小為20。整個(gè)排序過(guò)程的分組情況，如下所示：
1 | {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49} |
2 | {37,5,34,76,26,9,0,37,55,49, 94,12,68,83,90,37,12,65,76,76} |
3 | {9,0,34,55,26, 37,5,37,76,49, 37,12,65,76,76, 94,12,68,83,90} |
4 | {5,0, 9,12,12, 37,26, 37,34,49, 37,55, 65,68,76, 76,76, 90,83,94} |
5 | {0, 5, 9, 12,12, 26, 34, 37, 37,37, 49, 55, 65, 68,76, 76, 76, 83, 90,94} |
下面說(shuō)明詳細(xì)過(guò)程：首先，初始化d = 20。在循環(huán)中反復(fù)得到間隔d，根據(jù)d執(zhí)行一趟希爾排序。
對(duì)于d = 20/2 = 10：根據(jù)d = 10來(lái)對(duì)數(shù)組排序，將原始數(shù)組分成2塊： {94,12,34,76,26,9,0,37,55,76}與{37,5,68,83,90,37,12,65,76,49}，也就是對(duì)如下數(shù)組分別進(jìn)行直接插入排序：{array[0],array[10]} = {94,37}{array[1],array[11]} = {12,5}{array[2],array[12]} = {34,68}{array[3],array[13]} = {76,83}{array[4],array[14]} = {26,90}{array[5],array[15]} = {9,37}{array[6],array[16]} = {0,12}{array[7],array[17]} = {37,65}{array[8],array[18]} = {55,76}{array[9],array[19]} = {76,49}第一趟希爾排序后，各個(gè)子數(shù)組變?yōu)椋簕37,5,34,76,26,9,0,37,55,49}與{94,12,68,83,90,37,12,65,76,76}，即：array = {37,5,34,76,26,9,0,37,55,49,94,12,68,83,90,37,12,65,76,76}，
對(duì)于d = 10/2 = 5：根據(jù)d = 5來(lái)對(duì)數(shù)組排序，將第一趟希爾排序后的數(shù)組分成4塊 ：{37,5,34,76,26}、{9,0,37,55,49}、{94,12,68,83,90}與{37,12,65,76,76}，也就是對(duì)如下數(shù)組分別進(jìn)行直接插入排序：{array[0],array[5],array[10],array[15]} = {37,9,94,37}{array[1],array[6],array[11],array[16]} = {5,0,12,12}{array[2],array[7],array[12],array[17]} = {34,37,68,65}{array[3],array[8],array[13],array[18]} = {76,55,83,76}{array[4],array[9],array[14],array[19]} = {26,49,90,76}第二趟希爾排序后，各個(gè)子數(shù)組變?yōu)椋簕9,0,34,55,26}、{37,5,37,76,49}、{37,12,65,76,76}與{94,12,68,83,90}，即：array = {9,0,34,55,26,37,5,37,76,49,37,12,65,76,76,94,12,68,83,90}。
對(duì)于d = 5/2 = 2：根據(jù)d = 2來(lái)對(duì)數(shù)組排序，將第二趟希爾排序后的數(shù)組分成10塊： {9,0}、{34,55}、{26,37}、{5,37}、{76,49}、{37,12}、{65,76}、{76,94}、{12,68}與{83,90}，也就是對(duì)如下數(shù)組分別進(jìn)行直接插入排序：{array[0],array[2],array[4],array[6],array[8],array[10],array[12],array[14],array[16],array[18]} = {9,34,26,5,76,37,65,76,12,83}{array[1],array[3],array[5],array[7],array[9],array[11],array[13],array[15],array[17],array[19]} = {0,55,37,37,49,12,76,94,68,90}第三趟希爾排序后，各個(gè)子數(shù)組變?yōu)椋簕5,0}、{9,12}、{12,37}、{26,37}、{34,49}、{37,55}、{65,68}、{76,76}、{76,90}與{83,94}，即：array = ：{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}。
對(duì)于d = 2/2 = 1：根據(jù)d = 1來(lái)對(duì)數(shù)組排序，將第二趟希爾排序后的數(shù)組分成20塊：{5}、{0}、{9}、{12}、{12}、{37}、{26}、{37}、{34}、{49}、{37}、{55}、{65}、{68}、{76}、{76}、{76}、{90}、{83}、{94}，也就是對(duì)如下數(shù)組分別進(jìn)行直接插入排序：{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}第四趟希爾排序以后，數(shù)組已經(jīng)有序：array = {0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90,94}。因?yàn)?d= 1，希爾排序結(jié)束。
算法分析
希爾排序是基于插入排序的一種算法， 它的時(shí)間復(fù)雜度與增量序列的選取有關(guān)，例如：
希爾提出了增量序列 h1 ，h2 ，……，ht ，只要h1=1，任何增量序列都是可行的，使用希爾增量排序的時(shí)間復(fù)雜度為O(n^2)。Hibbard提出了一個(gè)增量序列：2^k-1，使用Hibbard增量排序的時(shí)間復(fù)雜度為O(n^(3/2))。Sedgewick提出了幾種增量序列：9*4i – 9*2i +1 或者是 4i – 3* 2i + 1，最壞運(yùn)行時(shí)間為O(n^(4/3))，對(duì)這些增量序列的平均運(yùn)行時(shí)間猜測(cè)為O(n^(7/6))。但是現(xiàn)今仍然沒(méi)有人能找出希爾排序的精確下界。希爾排序沒(méi)有快速排序算法快O(nlogn)，因此中等大小規(guī)模表現(xiàn)良好，對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。但是比O(n^2)復(fù)雜度的算法快得多。此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時(shí)快速排序在最壞的情況下執(zhí)行的效率會(huì)非常差。專(zhuān)家們提倡，幾乎任何排序工作在開(kāi)始時(shí)都可以用希爾排序，若在實(shí)際使用中證明它不夠快，再改成快速排序這樣更高級(jí)的排序算法。本質(zhì)上講，希爾排序算法是直接插入排序算法的一種改進(jìn)，減少了其復(fù)制的次數(shù)，速度要快很多，原因是，當(dāng)n值很大時(shí)數(shù)據(jù)項(xiàng)每一趟排序需要的個(gè)數(shù)很少，但數(shù)據(jù)項(xiàng)的距離很長(zhǎng)。當(dāng)n值減小時(shí)每一趟需要和動(dòng)的數(shù)據(jù)增多，此時(shí)已經(jīng)接近于它們排序后的最終位置。 正是這兩種情況的結(jié)合才使希爾排序效率比插入排序高很多。
時(shí)間復(fù)雜度希爾排序的效率很大程度上依賴(lài)于增量序列的選擇，好的增量序列有如下共同特征：
最后一個(gè)增量必須為1。應(yīng)該盡量避免序列中的值（尤其是相鄰的值）互為倍數(shù)的情況。有人通過(guò)大量的實(shí)驗(yàn)，給出了較好的結(jié)果：當(dāng)n較大時(shí)，比較和移動(dòng)的次數(shù)約在n^1.25到1.6*n^1.25之間。另外，希爾排序的時(shí)間性能優(yōu)于直接插入排序，原因是：
當(dāng)文件初態(tài)基本有序時(shí)直接插入排序所需的比較和移動(dòng)次數(shù)均較少。當(dāng)n值較小時(shí)，n和的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度O(n)和最壞時(shí)間復(fù)雜度0()差別不大。在希爾排序開(kāi)始時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來(lái)增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過(guò)序，使文件較接近于有序狀態(tài)，所以新的一趟排序過(guò)程也較快。因此，希爾排序在效率上較直接插入排序有較大的改進(jìn)。
空間復(fù)雜度因?yàn)橄柵判蛞蕾?lài)于增量序列，從而導(dǎo)致排序的趟數(shù)不固定，對(duì)于不同的增量執(zhí)行一趟希爾排序，只用到一個(gè)輔助變量，所以空間復(fù)雜度為O(n)。
排序穩(wěn)定性由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，通過(guò)上述元素76可以看到，希爾排序不穩(wěn)定。
因此，希爾排序是不穩(wěn)定的。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
