From Gossip@caterpillar

Algorithm Gossip: Shell 排序法 - 改良的插入排序

說明

插入排序法由未排序的後半部前端取出一個值，插入已排序前半部的適當位置，概念簡單但速度不快。

排序要加快的基本原則之一，是讓後一次的排序進行時，儘量利用前一次排序後的結果，以加快排序的速度，Shell排序法即是基於此一概念來改良插入排序法。

解法

Shell排序法最初是D.L Shell於1959所提出，假設要排序的元素有n個，則每次進行插入排序時並不是所有的元素同時進行時，而是取一段間隔。

Shell首先將間隔設定為n/2，然後跳躍進行插入排序，再來將間隔n/4，跳躍進行排序動作，再來間隔設定為n/8、n/16，直到間隔為1之後的最後一次排序終止，由於上一次的排序動作都會將固定間隔內的元素排序好，所以當間隔越來越小時，某些元素位於正確位置的機率越高，因此最後幾次的排序動作將可以大幅減低。

舉個例子來說，假設有一未排序的數字如右：89 12 65 97 61 81 27 2 61 98

數字的總數共有10個，所以第一次我們將間隔設定為10 / 2 = 5，此時我們對間隔為5的數字進行排序，如下所示：
Shell 排序

畫線連結的部份表示要一起進行排序的部份，再來將間隔設定為5 / 2的商，也就是2，則第二次的插入排序對象如下所示：

再來間隔設定為2 / 2 = 1，此時就是單純的插入排序了，由於大部份的元素都已大致排序過了，所以最後一次的插入排序幾乎沒作什麼排序動作了：

將間隔設定為n / 2是D.L Shell最初所提出，在教科書中使用這個間隔比較好說明，然而Shell排序法的關鍵在於間隔的選定，例如Sedgewick證明選用以下的間隔可以加快Shell排序法的速度：

其中4*(2^j)² + 3*(2^j) + 1不可超過元素總數n值，使用上式找出j後代入4*(2^j)² + 3*(2^j) + 1求得第一個間隔，然後將2^j除以2代入求得第二個間隔，再來依此類推。

後來還有人證明有其它的間隔選定法可以將Shell排序法的速度再加快；另外Shell排序法的概念也可以用來改良氣泡排序法。

實作：C Java Python Scala Ruby

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAX 10 
#define SWAP(x,y) {int t; t = x; x = y; y = t;} 

void shellSort(int[]); 

int main(void) { 
    srand(time(NULL)); 
    
    int number[MAX] = {0};  

    printf("排序前："); 
    int i; 
    for(i = 0; i < MAX; i++) { 
        number[i] = rand() % 100; 
        printf("%d ", number[i]); 
    } 

    shellSort(number); 
    
    printf("\n排序後："); 
    for(i = 0; i < MAX; i++) { 
        printf("%d ", number[i]); 
    } 

    return 0; 
} 

void shellSort(int number[]) { 
    int gap = MAX / 2; 

    while(gap > 0) { 
        int k;
        for(k = 0; k < gap; k++) { 
            int i;
            for(i = k+gap; i < MAX; i+=gap) { 
                int j;
                for(j = i - gap; j >= k; j-=gap) { 
                    if(number[j] > number[j+gap]) { 
                        SWAP(number[j], number[j+gap]); 
                    } 
                    else 
                        break; 
                } 
            } 
        } 

        gap /= 2; 
    } 
}

Java

public class Sort {
    public static void sort(int[] number) {
        int gap = number.length / 2; 

        while(gap > 0) { 
            for(int k = 0; k < gap; k++) { 
                for(int i = k+gap; i < number.length; i+=gap) { 
                    for(int j = i - gap; j >= k; j-=gap) { 
                        if(number[j] > number[j+gap]) { 
                            swap(number, j, j+gap); 
                        } 
                        else 
                            break; 
                    } 
                } 
            } 

            gap /= 2; 
        } 
    }
    
    private static void swap(int[] number, int i, int j) {
        int t = number[i]; 
        number[i] = number[j]; 
        number[j] = t;
    }
}

Python

def sort(number):
    gap = len(number) // 2
    while gap > 0:
        for k in range(gap):
            for i in range(k + gap, len(number), gap):
                for j in range(i - gap, k - 1, -gap):
                    if number[j] > number[j + gap]:
                        number[j], number[j + gap] \
                                   = number[j + gap], number[j]
                    else:
                        break
        gap //= 2

Scala

object Sort {
    def shell(number: Array[Int]) {
        def sort(k: Int, gap: Int, j: Int) {
            if(j >= k && number(j) > number(j + gap)) 
                swap(number, j, j + gap)
            if(j - gap >= k) 
                sort(k, gap, j - gap)
        }
        def gapDown(gap: Int) {
            if(gap > 0) {
                for(
                    k <- 0 until gap;
                    i <- k + gap until (number.length, gap)
                ) sort(k, gap, i - gap)
                gapDown(gap / 2)
            }
        }
        gapDown(number.length / 2)
    }
    
    private def swap(number: Array[Int], i: Int, j: Int) {
        val t = number(i)
        number(i) = number(j)
        number(j) = t
    }
}

Ruby

def sort(number)
    gap = number.length / 2
    while gap > 0
        gap.times { |k|
            (k + gap).step(number.length - 1, gap) { |i|
                (i - gap).step(k, -gap) { |j|
                    if number[j] > number[j + gap]
                        number[j], number[j + gap] = 
                            number[j + gap], number[j]
                    else
                        break
                    end
                }
            }
        }
        gap /= 2
    end
end