摘要：遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。算法實(shí)現(xiàn)實(shí)現(xiàn)分配排序計(jì)數(shù)排序計(jì)數(shù)排序與之前的算法采用的是完全不同的一種視角，它注重的是元素應(yīng)該存在的位置，而不再是兩個(gè)元素之間的大小關(guān)系。

原文鏈接：http://kasheemlew.github.io/2...

想象一下插隊(duì)的過程...

一個(gè)人通過插隊(duì)的方式排到前面，而將原本在他前面的人擠到了后面的位置。
對(duì)數(shù)排序時(shí)也是這樣，為了從小到大排序，需要將一個(gè)數(shù)放到前面，而將那些比它大的數(shù)擠到了后面，從而實(shí)現(xiàn)了排序的目的。

當(dāng)一個(gè)數(shù)列A開始進(jìn)行排序時(shí)就已經(jīng)被劃分成了兩個(gè)部分--有序的和無序的，由于只有一個(gè)數(shù)的數(shù)列可以被看作已經(jīng)有序，所以將數(shù)列A中的第一個(gè)元素看作有序的部分(圖中6)，后面的其他數(shù)看作無序的部分(圖中5，3，1，8，7，2，4)

從前到后掃描有序的部分，將無序部分中的第一個(gè)元素插入到有序的部分中合適的位置(3插到5，6的前面)

然后將有序序列中該數(shù)后面的數(shù)依次后移一位(5，6后移一位)，形成新的有序部分(3, 5, 6)

重復(fù)直到遍歷完整個(gè)數(shù)列。

O(n)用于存儲(chǔ)整個(gè)數(shù)列，O(1)輔助，暫存操作數(shù)，用于插入。

最好：已經(jīng)有序的情況下，只需要遍歷數(shù)列一次，為O(n)。

最壞：反序情況下比較次數(shù)依次是1 + 2 + 3 + ... + (N - 1)，即(1/2)n(n-1)次。O(n^2)。

平均：O(n^2)

根據(jù)上述的排序過程，易用數(shù)組進(jìn)行實(shí)現(xiàn)，這里不再贅述。但使用鏈表實(shí)現(xiàn)中每次后移的過程會(huì)大大降低排序的效率，以下兩種實(shí)現(xiàn)可以

struct LIST * InsertionSort(struct LIST * pList)
{
    if(pList == NULL || pList->pNext == NULL) {
        return pList;
    }
    struct LIST * head = NULL; // head為有序部分的第一個(gè)元素
    while(pList != NULL) {
        struct LIST * current = pList;
        pList = pList->pNext;
        if(head == NULL || current->iValue < head->iValue) {
            // 插入有序部分的第一個(gè)位置
            current->pNext = head;
            head = current;
        } else {
            // 插入有序部分的中間位置
            struct LIST * p = head;
            while(p != NULL) {
                if(p->pNext == NULL || current->iValue < p->pNext->iValue) {
                    current->pNext = p->pNext;
                    p->pNext = current;
                    break;
                }
                p = p->pNext;
            }
        }
    }
    return head;
}

采用從后向前遍歷插入的方法，并利用Python中的切片，每次插入一個(gè)數(shù)之后不必再使用后移的方式調(diào)整有序序列的位置，而是直接拼接切片并返回。

def insertion_sort(alist):
    length = len(alist)
    if length == 1:
        return alist
    b = insertion_sort(alist[1:])
    for index in range(len(b)):
        if alist[0] <= b[index]:
            return b[:index] + [alist[0]] + b[index:]
    return b + [alist[0]]

這次不再將最小的數(shù)放到最前面，讓后面的數(shù)自動(dòng)往后面移位，而是每次選擇出最小的數(shù)，和排在第一個(gè)的數(shù)進(jìn)行交換。從而達(dá)到將較小的數(shù)排在前面的目的。

以從小到大排序?yàn)槔?

在未排序序列中找到最小元素，存放到排序序列的起始位置，

再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到已排序序列的末尾。

重復(fù)第二步，直到所有元素均排序完畢。

O(n)用于存儲(chǔ)整個(gè)數(shù)列，O(1)輔助，暫存操作數(shù)，用于交換。

由于一共有n個(gè)位置要進(jìn)行選擇，每次選擇時(shí)又要對(duì)剩下為放入合適位置的數(shù)進(jìn)行便利，所以時(shí)間復(fù)雜度不分最好和最壞，依次比較(N-1)+(N-2)+ ... +1次，即(N-1+1)*N/2 = (N^2)/2, 為O(n^2)。

def selection_sort(alist):
    length = len(alist)
    for index in range(length):
        m = index
        for i in range(index, length):
            if alist[i] < alist[m]:
                m = i
        alist[m], alist[index] = alist[index], alist[m]
    return alist

歸并算法主要通過拆分和合并兩個(gè)步驟來完成對(duì)數(shù)列的排序，將需要排序的數(shù)列拆分成盡量小的序列，然后重新合并，合并時(shí)按順序排列，最終形成有序序列。

申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列

設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

重復(fù)步驟3直到某一指針到達(dá)序列尾

將另一序列剩下的所有元素直接復(fù)制到合并序列尾

假設(shè)序列共有n個(gè)元素：

將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作，形成n/2個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素

將上述序列再次歸并，形成n/4個(gè)序列，每個(gè)序列包含四個(gè)元素

重復(fù)步驟2，直到所有元素排序完畢

以遞歸法為例：

遞歸算法的時(shí)間由子問題的時(shí)間和合并子問題的時(shí)間兩部分構(gòu)成，最小子問題不需要合并，因此n=1時(shí)即為?(1)。

進(jìn)而得出以下方程:
T(n)所要合并的的數(shù)列為原來數(shù)列中所有的數(shù)(n個(gè))，所以時(shí)間為cn。T(n/2)為T(n)劃分出的子問題，它所處理的數(shù)列中數(shù)的個(gè)數(shù)是n/2個(gè)，故T(n/2)=2T(n/4)+cn/2，類推得到下圖。

圖中樹的深度顯然為(logn)+1，每一層所有的問題所需要的合并時(shí)間的和都是cn，因此總時(shí)間為cn(logn)+cn，時(shí)間復(fù)雜度為O(nlogn)。

根據(jù)上面的推導(dǎo)，歸并排序的時(shí)間復(fù)雜度為O(nlogn)。

迭代法：O(n)存儲(chǔ)整個(gè)數(shù)列，O(1)輔助，用于交換。

遞歸法：O(n)存儲(chǔ)整個(gè)數(shù)列，O(n)輔助，用于子問題存儲(chǔ)子問題的序列。

對(duì)于C++，可以使用模板使得函數(shù)適用于所有的類型的數(shù)據(jù)。

template
void merge_sort(T arr[], int len) {
    T* a = arr;
    T* b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

def merge_sort(alist):
    """合并函數(shù)"""
    if len(alist) <= 1:
        return alist
    middle = len(alist)//2
    left = merge_sort(alist[:middle])
    right = merge_sort(alist[middle:])
    print left + right
    return merge(left, right)

def merge(left, right):
    """主排序函數(shù)"""
    l, r = 0, 0
    result = []
    while l
堆排序
堆是什么
堆可以看成是二叉樹的一種，也可以看成是元素有優(yōu)先權(quán)區(qū)別的隊(duì)列。

任意節(jié)點(diǎn)小于(或大于)它的所有后裔(樹中的子節(jié)點(diǎn))，最小元(或最大元)在的根上。

堆總是一棵完全樹。（每一層必須從左往右排，并且排完一層之后才能排下一層）


像這樣：?

(左邊是一個(gè)小頂堆，右邊是大頂堆。)
根據(jù)上面所說的，只有一個(gè)數(shù)的序列一定可以構(gòu)成一個(gè)堆。
排序過程
以從小到大排為例：
最大堆調(diào)整：將末端的子節(jié)點(diǎn)進(jìn)行調(diào)整，使得子節(jié)點(diǎn)小于父節(jié)點(diǎn)。
前面說過，只有一個(gè)數(shù)的序列一定可以構(gòu)成一個(gè)堆，下面考慮三個(gè)數(shù)的情況。

如果要讓這個(gè)子二叉樹成為堆，只需要將樹根與較大的子節(jié)點(diǎn)進(jìn)行交換即可(7和15交換)。
如果將根中的數(shù)與子節(jié)點(diǎn)交換的過程看作是下沉的過程，那么它必須下沉到?jīng)]有子節(jié)點(diǎn)比它小的位置，因?yàn)榻粨Q的過程中始終使較大的數(shù)移到上一層的位置，所以不會(huì)對(duì)其他數(shù)的排序造成影響。

建立最大堆：將堆所有數(shù)據(jù)重新排序。

堆排序：移除位在第一個(gè)數(shù)據(jù)(實(shí)際操作中將其放到數(shù)列的最后)，對(duì)其他的數(shù)繼續(xù)進(jìn)行堆排序。



效率分析
時(shí)間復(fù)雜度
堆排序的時(shí)間主要由堆調(diào)整和建堆兩部分構(gòu)成。

堆調(diào)整

  當(dāng)前節(jié)點(diǎn)與兩個(gè)子節(jié)點(diǎn)各比較一次之后與較大的進(jìn)行一次交換，并對(duì)被交換的子節(jié)點(diǎn)進(jìn)行遞歸操作。所以有T(n)=T(n-1)+3; T(1)=3，樹高h=logn，所以T(h)=3h=3O(logn)，堆調(diào)整的時(shí)間復(fù)雜度為O(logn)。

建堆

  樹高h=logn。最后一層的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，不用進(jìn)行操作。對(duì)深度為于h-1層的節(jié)點(diǎn)，比較2次，交換1次，這一層最多有2^(h-1)個(gè)節(jié)點(diǎn)，總共操作次數(shù)最多為3(1*2^(h-1))；對(duì)深度為h-2層的節(jié)點(diǎn)，總共有2^(h-2)個(gè)，每個(gè)節(jié)點(diǎn)最多比較4次，交換2次，所以操作次數(shù)最多為3(2*2^(h-2))。另a:s=3*[2^(h-1) + 2*2^(h-2)+ 3*2^(h-3) + … + h*2^0]，b:2s=3*[2^(h) + 2*2^(h-1)+ 3*2^(h-2) + … + h*2^1]，a-b得s=3*[2^h + 2^(h-1) + 2^(h-2) + … + 2 - h]=3*[2^(h+1)-2-h]，又因?yàn)?b>2^(h+1)=n+1，所以總時(shí)間約為3n，建堆的時(shí)間復(fù)雜度O(n)。


綜上：堆排序的時(shí)間等于第一次建堆加上后面n-1次堆調(diào)整，由于n的減小，后面的O(log2(n))中的n也會(huì)減小，所以用小于等于號(hào)T(n) <=  O(n)  + (n - 1)*O(log2(n))，時(shí)間復(fù)雜度為O(nlogn)
空間復(fù)雜度
O(n)存儲(chǔ)整個(gè)數(shù)列，O(1)輔助，用于交換。
算法實(shí)現(xiàn)
Python實(shí)現(xiàn)
def swap(array, a, b):
    """交換函數(shù)"""
    temp = array[a]
    array[a] = array[b]
    array[b] = temp

def sift_down(array, last_index):
    """堆調(diào)整函數(shù)"""
    index = 0
    while True:
        left_index = 2*index + 1
        right_index = 2*index + 2
        if left_index > last_index:
            break
        else:
            if right_index > last_index:
                next_index = left_index
            else:
                if array[left_index] >= array[right_index]:
                    next_index = left_index
                else:
                    next_index = right_index
        if array[next_index] <= array[index]:
            break
        temp = array[index]
        array[index] = array[next_index]
        array[next_index] = temp
        index = next_index
        print("next_index: ", next_index)

def heap_sort(array, length):
    """堆排序主函數(shù)"""
    last_node = (length - 2) / 2
    for i in range(last_node, 0, -1):
        sift_down(array, length-1)

    for i in range(length-1, 1, -1):
        swap(array, 0, i)
        sift_down(array, i-1)
    swap(array, 0, 1)
快速排序

快速排序類似于上體育課排隊(duì)的過程，總是以一個(gè)人為基準(zhǔn)，其他人根據(jù)身高分列在他的兩邊。在快速排序中也有一個(gè)基準(zhǔn)--樞軸(pivot)，其他的數(shù)根據(jù)大小排在它的兩邊。之所以叫快速排序，是因?yàn)榭焖倥判蛟谧詈们闆r和一般情況下的時(shí)間復(fù)雜度都是最低的。
排序過程


從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot），

重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。



效率分析
時(shí)間復(fù)雜度

平均：，時(shí)間復(fù)雜度為O(logn)

最好：Partition每次劃分均勻，遞歸樹的深度為logn+1，即僅需遞歸logn次，第一次Partiation對(duì)整個(gè)數(shù)列掃描一遍，做n次比較。然后，獲得的樞軸將數(shù)組一分為二，各自還需要T（n/2）的時(shí)間。類推得到：
T(n)=2T(n/2)+n; T(1)=0


T(n)=2(2T（n/4）+n/2)+n=4T（n/4）+2n 

T(n)=4(2T(n/8)+n/4)+2n=8T(n/8)+3n

所以  T（n）≤nT（1）+（log2n）×n= O(nlogn) 
最壞：每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列，遞歸樹除了葉節(jié)點(diǎn)之外的節(jié)點(diǎn)都只有一個(gè)子節(jié)點(diǎn)，每次都要與剩下的所有數(shù)進(jìn)行比較。

空間復(fù)雜度

平均：O(n)存儲(chǔ)整個(gè)數(shù)列，O(logn)輔助

最好：O(n)存儲(chǔ)整個(gè)數(shù)列，O(logn)輔助

最壞：O(n)存儲(chǔ)整個(gè)數(shù)列，O(n)輔助


輔助空間來源于遞歸造成的?？臻g的使用。
算法實(shí)現(xiàn)
Python實(shí)現(xiàn)
def Partition(r, low, high):
    pivot = r[low]
    while low < high:
        while low < high and r[high] >= pivot:
            high -= 1
        if low < high:
            r[low] = r[high]
            low += 1
        while low < high and r[low] <= pivot:
            low += 1
        if low < high:
            r[high] = r[low]
            high -= 1
    r[low] = pivot
    return low

def QuickSort(r, low, high):
    if low < high:
        pivotkey = Partition(r, low, high)
        QuickSort(r, low, pivotkey-1)
        QuickSort(r, pivotkey+1, high)
分配排序
計(jì)數(shù)排序
計(jì)數(shù)排序與之前的算法采用的是完全不同的一種視角，它注重的是元素應(yīng)該存在的位置，而不再是兩個(gè)元素之間的大小關(guān)系。
排序過程


找出待排序的數(shù)組中最大和最小的元素

統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項(xiàng)

對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）

反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1


效率分析
時(shí)間復(fù)雜度
需要將數(shù)組遍歷三遍，但是這三個(gè)循環(huán)不是嵌套執(zhí)行的，所以時(shí)間復(fù)雜度沒有影響。
平均：O(n+k)
空間復(fù)雜度
存放原序列和元素的計(jì)數(shù)信息：O(n+k)
計(jì)數(shù)排序的瓶頸十分明顯，對(duì)于數(shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。
算法實(shí)現(xiàn)
Python實(shí)現(xiàn)
下面是對(duì)一個(gè)序列中所有的字符進(jìn)行排序
def countSort(arr):
    output = [0 for i in range(256)]
    count = [0 for i in range(256)]

    for i in arr:
        count[ord(i)] += 1

    for i in range(256):
        count[i] += count[i-1]

    for i in range(len(arr)):
        output[count[ord(arr[i])]-1] = arr[i]
        count[ord(arr[i])] -= 1
    return output
桶排序
排序過程

設(shè)置一個(gè)定量的序列當(dāng)作空桶。

遍歷序列，把元素放到對(duì)應(yīng)的桶中去。

對(duì)每個(gè)不是空的桶子進(jìn)行排序。

將桶中的元素放回到原來的序列中去。



效率分析
時(shí)間復(fù)雜度
與計(jì)數(shù)排序類似，遍歷和桶中的排序是并列關(guān)系，不影響時(shí)間復(fù)雜度，平均O(n+k)
空間復(fù)雜度
桶的個(gè)數(shù)和每個(gè)桶中元素的個(gè)數(shù)，O(n*k)
算法實(shí)現(xiàn)
C++實(shí)現(xiàn)
C++中的vector是用來作桶的絕佳的材料。也可以用鏈表來實(shí)現(xiàn)。
void bucketSort(float arr[], int n)
{
    vector b[n];

    for (int i=0; i
基數(shù)排序
如果要將一副撲克牌恢復(fù)到原來有序的狀態(tài)，為了將撲克牌恢復(fù)成有序的狀態(tài)(就像剛買來時(shí)那樣)，我們通常先挑出相同花色的牌放在一起，然后再按照牌號(hào)的大小進(jìn)行排序，也就是依次按照牌的不同屬性進(jìn)行排序。

而在基數(shù)排序中，通常將數(shù)的不同的位看作是不同的屬性，也就是依次根據(jù)各個(gè)位上數(shù)字的大小進(jìn)行排序。
排序過程

對(duì)數(shù)列中的數(shù)從最低位開始每次取一位進(jìn)行比較，先比較個(gè)位，然后比較十位...

根據(jù)選中的位對(duì)元素進(jìn)行計(jì)數(shù)排序

重復(fù)上述過程，直到取完所有位


效率分析
時(shí)間復(fù)雜度
假設(shè)最大的數(shù)一共有k位，每取一位進(jìn)行比較都要講所有的數(shù)遍歷一遍，因此為O(kN)
空間復(fù)雜度
計(jì)數(shù)列表的空間和用做中間列表的存儲(chǔ)的空間，O(k+N)
算法實(shí)現(xiàn)
Python實(shí)現(xiàn)
def countingSort(arr, exp1):
    """計(jì)數(shù)排序函數(shù)"""
    n = len(arr)
    output = [0] * (n) # 最終的數(shù)列，先用0占位
    count = [0] * (10) # 每個(gè)數(shù)進(jìn)行計(jì)數(shù)的列表，初始化為0

    for i in range(0, n):
        index = (arr[i]/exp1)
        count[ (index)%10 ] += 1
    for i in range(1,10):
        count[i] += count[i-1]
    i = n-1
    while i>=0:
        index = (arr[i]/exp1)
        output[ count[ (index)%10 ] - 1] = arr[i]
        count[ (index)%10 ] -= 1
        i -= 1

    # 將arr修改為按這一位排序過后的順序
    i = 0
    for i in range(0,len(arr)):
        arr[i] = output[i]


def radixSort(arr):
    max1 = max(arr)
    exp = 1
    while max1/exp > 0: # 從個(gè)位開始每次取一位，進(jìn)行計(jì)數(shù)排序
        countingSort(arr,exp)
        exp *= 10
其他
冒泡排序

冒泡排序與氣泡上升的過程相似，氣泡上升的過程中不斷吸收空氣而變大，只不過冒泡排序中的元素不會(huì)發(fā)生變化，而是較大的數(shù)與較小數(shù)交換了位置。冒泡排序是一種用時(shí)間換空間的算法。

排序過程

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。


效率分析
時(shí)間復(fù)雜度
外層循環(huán)n-1次，內(nèi)層循環(huán)n-i次。內(nèi)層循環(huán)總的次數(shù)用等差數(shù)列求和公式是(1+(n-1))*(n-1)/2=n*(n-1)/2≈n^2/2，外層循環(huán)賦值次數(shù)為常數(shù)設(shè)為a，內(nèi)層循環(huán)賦值次數(shù)也是常數(shù)設(shè)為b，所以f(n)≈a * n + b * n^2/2，時(shí)間復(fù)雜度是O(n^2)
空間復(fù)雜度
O(n)存儲(chǔ)整個(gè)數(shù)列，O(n)輔助，用于交換。
算法實(shí)現(xiàn)
Python實(shí)現(xiàn)
def bubble_sort(alist):
    length = len(alist)
    for index in range(length-1):
        for i in range(0, length-index-1):
            if alist[i] > alist[i+1]:
                alist[i+1], alist[i] = alist[i], alist[i+1]
    return alist
優(yōu)化: 添加標(biāo)記，在排序完成時(shí)停止排序，可以使最好情況下的時(shí)間復(fù)雜度為O(n)
def bubble_sort_flag(alist):
    length = len(alist)
    for index in range(length):
        flag = True
        for i in range(0, length-index-1):
            if alist[i] > alist[i+1]:
                alist[i+1], alist[i] = alist[i], alist[i+1]
                flag = False
        if flag:
            return alist
    return alist
希爾排序

Donald Shell設(shè)計(jì)的算法，也稱遞減增量排序算法，利用了插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，可以達(dá)到線性排序的效率的特點(diǎn)，對(duì)算法進(jìn)行了優(yōu)化。
希爾排序通過步長(zhǎng)來控制調(diào)整順序時(shí)的比較的兩個(gè)數(shù)之間的間隔，在排序開始階段使用較大的步長(zhǎng)可以使一個(gè)元素可以一次性地朝最終位置前進(jìn)一大步，然后再換用較小的步長(zhǎng)，進(jìn)行更加精確的調(diào)整。
算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時(shí)插入排序較快）。

排序過程
與插入排序類似，只不過不再是按照原序列的順行依次進(jìn)行判斷了，而是在無序序列中每次間隔步長(zhǎng)個(gè)元素取元素，對(duì)其進(jìn)行插入。
步長(zhǎng)選擇

希爾增量
步長(zhǎng)選擇為n2并且對(duì)步長(zhǎng)取半直到步長(zhǎng)達(dá)到1。
Sedgewick增量
1, 5, 19, 41, 109,...，根據(jù)而得出。
斐波那契增量
斐波那契數(shù)列除去0和1將剩余的數(shù)以黃金分割比的兩倍的冪進(jìn)行運(yùn)算得到的數(shù)列：1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…
效率分析
時(shí)間復(fù)雜度

平均: 根據(jù)選擇的步長(zhǎng)的不同而不同，通常為O(n^2)，但比起他時(shí)間復(fù)雜度為O(n^2)的算法更快。

最好：序列已經(jīng)有序，遍歷一遍即可，為O(n)。

最壞：O(n^2)


空間復(fù)雜度
O(n)用于存儲(chǔ)整個(gè)數(shù)列，O(1)輔助，暫存操作數(shù)，用于插入。
算法實(shí)現(xiàn)
Python實(shí)現(xiàn)
def shell_sort(alist):
    length = len(alist)
    gap = length / 2
    while gap > 0:
        for i in range(gap, length):
            temp = alist[i]
            j = i
            # 插入排序
            while j >= gap and alist[j-gap] > temp:
                alist[j] = alist[j-gap]
                j -= gap
            alist[j] = temp
        gap = gap / 2
    return alist
梳排序(Comb Sort)
梳排序的基本思想和 希爾排序 一樣，都是通過在排序開始階段用較大的步長(zhǎng)進(jìn)行排序，使得一個(gè)元素可以一次性地朝最終位置前進(jìn)一大步。相對(duì)于 希爾排序 對(duì) 插入排序 進(jìn)行改良，梳排序 則是 冒泡排序 的延伸。
排序過程
梳排序基于冒泡排序，但是沒次與固定距離處的數(shù)的比較和交換,這個(gè)固定距離是待排數(shù)組長(zhǎng)度除以1.3(一個(gè)魔數(shù)))得到近似值,下次則以上次得到的近似值再除以1.3,直到距離小至3時(shí),以1遞減。

效率分析
時(shí)間復(fù)雜度

平均：?((n^2)/(2^p))，p為數(shù)據(jù)的增量。

最好：?(nlogn)

最壞：O(n^2)


空間復(fù)雜度
O(n)用于存儲(chǔ)整個(gè)數(shù)列，O(1)輔助，用于交換。
算法實(shí)現(xiàn)
Python實(shí)現(xiàn)
def comb_sort(alist):
    shrink = 1.3
    gap = len(alist)

    while True:
        gap = int(gap / shrink)
        i = 0
        if gap < 1:
            break
        else:
            while i + gap < length:
                if alist[i] > alist[i+gap]:
                    alist[i], alist[i+gap] = alist[i+gap], alist[i]
                i += 1
    return alist