希爾排序

• 時(shí)間復(fù)雜度：平均O(n^1.3),最好為O(n),最壞為0(n ^ 2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定

算法解析：

• 希爾排序是直接插入排序的一種改進(jìn)，又稱做縮小增量排序
• 希爾排序是把待排序集合計(jì)算出一個(gè)增量集合Tn
• 把待排序集合分成若干個(gè)子集，然后每個(gè)子集進(jìn)行直接插入排序，知道Ti=1為止，排序結(jié)束
• 遍歷次數(shù)為增量集合的count數(shù)

舉例

有一個(gè)集合如下圖所示：

list.png

計(jì)算增量：gap = length/2

• 第一次：gap = 4，把待排序列劃分為4個(gè)子序列

  
  
  第一次.png

• 第二次 ：gap = 2，把待排序列劃分為2個(gè)子序列

  
  
  第二次.png

• 第三次：gap = 1，進(jìn)行一次直接插入排序，排序結(jié)束

排序結(jié)果：
第一次：7 3 1 2 8 5 4 10 9
第二次：1 2 4 3 7 5 8 10 9
第三次：1 2 3 4 5 7 8 9 10

C語(yǔ)言實(shí)現(xiàn)

void shellSort(int arr[],int length) {
     int gap;//間距or增量
     for (gap = length/2; gap>0; gap/=2) { //gap->1 共分幾次
         for (int i=gap; i<length; i++) {//從gap個(gè)元素開(kāi)始，直接插入排序
             if (arr[i] < arr[i-gap]) {
                 int tmp = arr[i];
                 int k = i-gap;
                 while (k>=0 && arr[k] > tmp) {
                     arr[k+gap] = arr[k];
                     k-=gap;
                 }
                 arr[k+gap] = tmp;
             }
         }
     }
}

OC實(shí)現(xiàn)

- (NSArray *)shellSort:(NSMutableArray *)arr {
    int length = arr.count;
    int gap;
    for (gap = length/2; gap>0; gap/=2) {
        for (int i = gap; i < length; i++) {
            if ([arr[i] intValue] < [arr[i-gap] intValue]) {
                NSNumber *tmp = arr[i];
                int k = i-gap;
                while (k>=0 && [arr[k] intValue] > tmp.intValue) {
                    arr[k+gap] = arr[k];
                    k-=gap;
                }
                arr[k+gap] = tmp;
            }
        }
    }
    return arr.copy;
}

以下實(shí)現(xiàn)來(lái)源于網(wǎng)絡(luò)，未驗(yàn)證

c++實(shí)現(xiàn)

void shell_sort(const int start, const int end) {
    int increment = end - start + 1;    //初始化劃分增量
    int temp{ 0 };
    do {    //每次減小增量，直到increment = 1
        increment = increment / 3 + 1;
        for (int i = start + increment; i <= end; ++i) {    //對(duì)每個(gè)劃分進(jìn)行直接插入排序
            if (numbers[i - increment] > numbers[i]) {
                temp = numbers[i];
                int j = i - increment;
                do {    //移動(dòng)元素并尋找位置
                    numbers[j + increment] = numbers[j];
                    j -= increment;
                } while (j >= start && numbers[j] > temp);
                numbers[j + increment] = temp;  //插入元素
            }
        }
    } while (increment > 1);
}

js實(shí)現(xiàn)

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //動(dòng)態(tài)定義間隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

Python 代碼實(shí)現(xiàn)

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
}

Go 代碼實(shí)現(xiàn)

func shellSort(arr []int) []int {
    length := len(arr)
    gap := 1
    for gap < gap/3 {
        gap = gap*3 + 1
    }
    for gap > 0 {
        for i := gap; i < length; i++ {
            temp := arr[i]
            j := i - gap
            for j >= 0 && arr[j] > temp {
                arr[j+gap] = arr[j]
                j -= gap
            }
            arr[j+gap] = temp
        }
        gap = gap / 3
    }
    return arr
}

Java 代碼實(shí)現(xiàn)

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

        int gap = 1;
        while (gap < arr.length) {
            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;
    }
}

PHP 代碼實(shí)現(xiàn)

function shellSort($arr)
{
    $len = count($arr);
    $temp = 0;
    $gap = 1;
    while($gap < $len / 3) {
        $gap = $gap * 3 + 1;
    }
    for ($gap; $gap > 0; $gap = floor($gap / 3)) {
        for ($i = $gap; $i < $len; $i++) {
            $temp = $arr[$i];
            for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
                $arr[$j+$gap] = $arr[$j];
            }
            $arr[$j+$gap] = $temp;
        }
    }
    return $arr;
}