摘要：遞歸地把小于基準值元素的子數列和大于基準值元素的子數列排序。算法實現實現分配排序計數排序計數排序與之前的算法采用的是完全不同的一種視角，它注重的是元素應該存在的位置，而不再是兩個元素之間的大小關系。

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

想象一下插隊的過程...

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

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

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

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

重復直到遍歷完整個數列。

O(n)用于存儲整個數列，O(1)輔助，暫存操作數，用于插入。

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

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

平均：O(n^2)

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

struct LIST * InsertionSort(struct LIST * pList)
{
    if(pList == NULL || pList->pNext == NULL) {
        return pList;
    }
    struct LIST * head = NULL; // head為有序部分的第一個元素
    while(pList != NULL) {
        struct LIST * current = pList;
        pList = pList->pNext;
        if(head == NULL || current->iValue < head->iValue) {
            // 插入有序部分的第一個位置
            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中的切片，每次插入一個數之后不必再使用后移的方式調整有序序列的位置，而是直接拼接切片并返回。

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]]

這次不再將最小的數放到最前面，讓后面的數自動往后面移位，而是每次選擇出最小的數，和排在第一個的數進行交換。從而達到將較小的數排在前面的目的。

以從小到大排序為例:

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

再從剩余未排序元素中繼續尋找最小元素，然后放到已排序序列的末尾。

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

O(n)用于存儲整個數列，O(1)輔助，暫存操作數，用于交換。

由于一共有n個位置要進行選擇，每次選擇時又要對剩下為放入合適位置的數進行便利，所以時間復雜度不分最好和最壞，依次比較(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

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

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

重復步驟3直到某一指針到達序列尾

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

假設序列共有n個元素：

將序列每相鄰兩個數字進行歸并操作，形成n/2個序列，排序后每個序列包含兩個元素

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

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

以遞歸法為例：

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

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

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

根據上面的推導，歸并排序的時間復雜度為O(nlogn)。

迭代法：O(n)存儲整個數列，O(1)輔助，用于交換。

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

對于C++，可以使用模板使得函數適用于所有的類型的數據。

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):
    """合并函數"""
    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):
    """主排序函數"""
    l, r = 0, 0
    result = []
    while l
堆排序
堆是什么
堆可以看成是二叉樹的一種，也可以看成是元素有優先權區別的隊列。

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

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


像這樣：?

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

如果要讓這個子二叉樹成為堆，只需要將樹根與較大的子節點進行交換即可(7和15交換)。
如果將根中的數與子節點交換的過程看作是下沉的過程，那么它必須下沉到沒有子節點比它小的位置，因為交換的過程中始終使較大的數移到上一層的位置，所以不會對其他數的排序造成影響。

建立最大堆：將堆所有數據重新排序。

堆排序：移除位在第一個數據(實際操作中將其放到數列的最后)，對其他的數繼續進行堆排序。



效率分析
時間復雜度
堆排序的時間主要由堆調整和建堆兩部分構成。

堆調整

  當前節點與兩個子節點各比較一次之后與較大的進行一次交換，并對被交換的子節點進行遞歸操作。所以有T(n)=T(n-1)+3; T(1)=3，樹高h=logn，所以T(h)=3h=3O(logn)，堆調整的時間復雜度為O(logn)。

建堆

  樹高h=logn。最后一層的節點沒有子節點，不用進行操作。對深度為于h-1層的節點，比較2次，交換1次，這一層最多有2^(h-1)個節點，總共操作次數最多為3(1*2^(h-1))；對深度為h-2層的節點，總共有2^(h-2)個，每個節點最多比較4次，交換2次，所以操作次數最多為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]，又因為2^(h+1)=n+1，所以總時間約為3n，建堆的時間復雜度O(n)。


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

def sift_down(array, last_index):
    """堆調整函數"""
    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):
    """堆排序主函數"""
    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)
快速排序

快速排序類似于上體育課排隊的過程，總是以一個人為基準，其他人根據身高分列在他的兩邊。在快速排序中也有一個基準--樞軸(pivot)，其他的數根據大小排在它的兩邊。之所以叫快速排序，是因為快速排序在最好情況和一般情況下的時間復雜度都是最低的。
排序過程


從數列中挑出一個元素，稱為"基準"（pivot），

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

遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。



效率分析
時間復雜度

平均：，時間復雜度為O(logn)

最好：Partition每次劃分均勻，遞歸樹的深度為logn+1，即僅需遞歸logn次，第一次Partiation對整個數列掃描一遍，做n次比較。然后，獲得的樞軸將數組一分為二，各自還需要T（n/2）的時間。類推得到：
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) 
最壞：每次劃分只得到一個比上一次劃分少一個記錄的子序列，遞歸樹除了葉節點之外的節點都只有一個子節點，每次都要與剩下的所有數進行比較。

空間復雜度

平均：O(n)存儲整個數列，O(logn)輔助

最好：O(n)存儲整個數列，O(logn)輔助

最壞：O(n)存儲整個數列，O(n)輔助


輔助空間來源于遞歸造成的棧空間的使用。
算法實現
Python實現
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)
分配排序
計數排序
計數排序與之前的算法采用的是完全不同的一種視角，它注重的是元素應該存在的位置，而不再是兩個元素之間的大小關系。
排序過程


找出待排序的數組中最大和最小的元素

統計數組中每個值為i的元素出現的次數，存入數組 C 的第 i 項

對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）

反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1


效率分析
時間復雜度
需要將數組遍歷三遍，但是這三個循環不是嵌套執行的，所以時間復雜度沒有影響。
平均：O(n+k)
空間復雜度
存放原序列和元素的計數信息：O(n+k)
計數排序的瓶頸十分明顯，對于數據范圍很大的數組，需要大量時間和內存。
算法實現
Python實現
下面是對一個序列中所有的字符進行排序
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
桶排序
排序過程

設置一個定量的序列當作空桶。

遍歷序列，把元素放到對應的桶中去。

對每個不是空的桶子進行排序。

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



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

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

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

對數列中的數從最低位開始每次取一位進行比較，先比較個位，然后比較十位...

根據選中的位對元素進行計數排序

重復上述過程，直到取完所有位


效率分析
時間復雜度
假設最大的數一共有k位，每取一位進行比較都要講所有的數遍歷一遍，因此為O(kN)
空間復雜度
計數列表的空間和用做中間列表的存儲的空間，O(k+N)
算法實現
Python實現
def countingSort(arr, exp1):
    """計數排序函數"""
    n = len(arr)
    output = [0] * (n) # 最終的數列，先用0占位
    count = [0] * (10) # 每個數進行計數的列表，初始化為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: # 從個位開始每次取一位，進行計數排序
        countingSort(arr,exp)
        exp *= 10
其他
冒泡排序

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

排序過程

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

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。

針對所有的元素重復以上的步驟，除了最后一個。

持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。


效率分析
時間復雜度
外層循環n-1次，內層循環n-i次。內層循環總的次數用等差數列求和公式是(1+(n-1))*(n-1)/2=n*(n-1)/2≈n^2/2，外層循環賦值次數為常數設為a，內層循環賦值次數也是常數設為b，所以f(n)≈a * n + b * n^2/2，時間復雜度是O(n^2)
空間復雜度
O(n)存儲整個數列，O(n)輔助，用于交換。
算法實現
Python實現
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
優化: 添加標記，在排序完成時停止排序，可以使最好情況下的時間復雜度為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設計的算法，也稱遞減增量排序算法，利用了插入排序在對幾乎已經排好序的數據操作時，效率高，可以達到線性排序的效率的特點，對算法進行了優化。
希爾排序通過步長來控制調整順序時的比較的兩個數之間的間隔，在排序開始階段使用較大的步長可以使一個元素可以一次性地朝最終位置前進一大步，然后再換用較小的步長，進行更加精確的調整。
算法的最后一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。

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

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

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

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

最壞：O(n^2)


空間復雜度
O(n)用于存儲整個數列，O(1)輔助，暫存操作數，用于插入。
算法實現
Python實現
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)
梳排序的基本思想和 希爾排序 一樣，都是通過在排序開始階段用較大的步長進行排序，使得一個元素可以一次性地朝最終位置前進一大步。相對于 希爾排序 對 插入排序 進行改良，梳排序 則是 冒泡排序 的延伸。
排序過程
梳排序基于冒泡排序，但是沒次與固定距離處的數的比較和交換,這個固定距離是待排數組長度除以1.3(一個魔數))得到近似值,下次則以上次得到的近似值再除以1.3,直到距離小至3時,以1遞減。

效率分析
時間復雜度

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

最好：?(nlogn)

最壞：O(n^2)


空間復雜度
O(n)用于存儲整個數列，O(1)輔助，用于交換。
算法實現
Python實現
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