希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：

插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達(dá)到線性排序的效率；
但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位；

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄

算法步驟

1. 選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列個數(shù) k，對序列進行 k 趟排序；

3. 每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。進行依次直接插入排序。
   注： 每次列排序之后，逆序?qū)Χ荚跍p少

Python

class Solution:
    def MySort(self , arr ):
        # write code here
        n = len(arr)
        # 步長為3
        gap = int(n/3)
        while gap > 0: 
            # 以gap為界限，往后取
            for i in range(gap,n): 
                # 得到第i個
                temp = arr[i] 
                j = i 
                #arr[j-gap] 第i個對應(yīng)的前半部分書元素
                t = arr[j-gap]
                while  j >= gap and t > temp: 
                    # 后面的小，就和前面的交換
                    arr[j] = arr[j-gap] 
                    # 換了以后再去換gap之間的變過的數(shù)
                    j -= gap 
                arr[j] = temp 
            gap = int(gap/3)
        return arr

Java

public class ShellSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 對 arr 進行拷貝，不改變參數(shù)內(nèi)容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int gap = 1;
        while (gap < arr.length/3) {
            gap = gap * 3 + 1;
        }

        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }

        return arr;
    }
}