[演算法] 希爾排序法(Shell Sort)
YehYeh\'s Notepad yehyeh@gmail.com 

[演算法(Algorithm)] 希爾排序法(Shell Sort)

  • 由D.L Shell於1959年提出
  • 希爾排序法又名增量遞減排序排序法 (diminishing increment sort)、謝耳排序法
  • 希爾排序法為插入排序法的改良
  • 希爾排序法的概念
    1. 將資料排列成二維陣列
    2. 對二維陣列的每一行做排序
    3. 利用前一次排序的結果來加快排序
  • 希爾排序作法：
    • 由大到小選定數個間距(Gap)，最後一個Gap一定要是1
    • 將資料依指定的間距(Gap)分組，進行插入排序
    • Gap的選擇對執行效率有很大的影響
  • 常見的Gap
    • Shell原本的Gap：N/2、N/4、...1(反覆除以2)
    • Hibbard的Gap：1、3、7、...、2k-1
    • Knuth的Gap: 1、4、13、...、(3k - 1) / 2
    • Sedgewick的Gap: 1、5、19、41、109、...
  • 假設有15筆資料(0~14)，Gap分別選用5,2,1
    • 第一回合 Gap=5 :
      • 對位置0, 5, 10作插入排序
      • 對位置1, 6, 11作插入排序
      • 對位置2, 7, 12作插入排序
      • 對位置3, 8, 13作插入排序
      • 對位置4, 9, 14作插入排序
    • 第二回合 Gap=2 :
      • 對位置0, 2, 4, 6, 8, 10, 12, 14作插入排序
      • 對位置1, 3, 5, 7, 9, 11, 13作插入排序
    • 第三回合 Gap=1 :
      • 分別對位置0, 1, 2, 3, ..., 14作插入排序
  • 假設資料為45,84,77,83,55,49,91,64,91,5,37,31,70,38,51，Gap分別選用5,2,1
    • 第一回合 Gap=5：
      • 依Gap將資料分組，各組分別進行插入排序(下面顏色相同者為同一組)
        0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
        45 84 77 83 55 49 91 64 91 5 37 31 70 38 51
      • 排序後
        0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
        37 31 64 38 5 45 84 70 83 51 49 91 77 91 55
      • 若將資料依Gap排列(5個一列)，可以發現每行(顏色相同者)的順序都是已排好的
        37 31 64 38 5
        45 84 70 83 51
        49 91 77 91 55
    • 第二回合 Gap=2：
      • 依Gap將資料分組，各組分別進行插入排序(下面顏色相同者為同一組)
        0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
        37 31 64 38 5 45 84 70 83 51 49 91 77 91 55
      • 排序後
        0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
        5 31 37 38 49 45 55 51 64 70 77 91 83 91 84
      • 若將資料依Gap排列(2個一列)，可以發現每行(顏色相同者)的順序都是已排好的
        5 31
        37 38
        49 45
        55 51
        64 70
        77 91
        83 91
        84
    • 第三回合 Gap=1：排序後
      0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
      5 31 37 38 45 49 51 55 64 70 77 83 84 91 91
  • 時間複雜度(Time Complexity)
    • Best Case：Ο(n)
    • Worst Case：依選用的GAP而定，Ο(n2) ~ Ο(n1.5)
    • Average Case：Ο(n5/4)
  • 空間複雜度(Space Complexity)：θ(1)
  • 穩定性(Stable/Unstable)：不穩定(Unstable)
  • Demo:
  • 演算法 (Gap=n/2) 
    var shellSort = function(data){ 
    var i, j, tmp;
    var gap = parseInt(data.length/2);      
    for( ; gap > 0; gap = parseInt(gap/2)){                             
        for(var i = gap; i < data.length; i++){    //插入排序法 
            tmp = data[i];
            for(j = i; j >= gap && tmp < data[j-gap]; j-=gap){
                data[j] = data[j-gap];
            }
            data[j] = tmp;
        }   
    }
};

    var swap = function(data, i, j){ 
    var tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
};
    
var shellSort = function(data){
    var gap = parseInt(data.length/2);
    while(gap>0){
        for(var k = 0; k < gap; k++){
            for(var i = k + gap; i < data.length; i += gap){
                for(var j = i - gap; j >= k; j -= gap){
                    if(data[j] > data[j+gap])
                        swap( data, j, j+gap);
                    else
                        break;
                }
            }
        }
        gap = parseInt(gap/= 2);
    }
};