2.1.6 希尔排序 Shell Sort

希尔排序可以用于大型数组，他对任意排序的数组表现也很好。

希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后的字数组都是部分有序的，这两种情况都很适合插入排序。

Python

A = [70, 90, 31, 37, 10, 1, 48, 60, 33, 80]

def shell_sort(arr):
    gap = len(arr)
    lenght = len(arr)
    while(gap > 1):
        gap = gap//2
        for i in range(gap, lenght):
            for j in range(i, 0, -gap):
                if arr[j] < arr[j-gap]:
                    arr[j], arr[j-gap] = arr[j-gap], arr[j]
    return arr

print(shell_sort(A))

Java

public class Shell{
    public static void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while(h < N /3) h = 3 * h + 1; // 1, 4, 13, 40, 121...
        while(h >= 1){
            for(int i = h; i < N; i++){
                for(int j = i; j >=h && less(a[j], a[j-h]; j -= h)
                    exch(a, j, j-h)
            }
            h = h / 3;
        }
    }
}