這篇文章是我在學習數(shù)據(jù)結(jié)構(gòu)時作筆記的用途午衰，這篇文章會紀錄下我學習的幾種排序算法，以及在學習的時候會加上配圖說明宦言！

相關(guān)的定義和基礎(chǔ)

如果某組信息在內(nèi)存空間中存儲，則稱為表(list)响疚。如果存儲于外存中則稱為文件(file)忿晕。把信息中的對象稱為記錄，每個記錄的信息劃分為更小的單元宾巍，稱為域咕幻。
??順序查找對關(guān)鍵字域沒有任何限制，而折半查找需要關(guān)鍵字有序的排列顶霞。其中折半查找可以使用二叉查找樹來描述肄程。

??二叉查找樹的特征
其左子樹不大于根節(jié)點值，右子樹不小于根節(jié)點值选浑。而且各個子樹還是一棵二叉查找樹蓝厌。

內(nèi)部排序是指在表的規(guī)模足夠小，能夠全部放在內(nèi)存中排序的方法古徒。外部排序指數(shù)據(jù)規(guī)模太大拓提，不能全部放在內(nèi)存中時舀寓。這篇文章中我主要紀錄的是內(nèi)部排序算法篡撵，其中包含了：插入排序锰镀、快速排序花鹅、堆排序真友、歸并排序、基數(shù)排序。

插入排序

插入排序類似于玩紙牌時航厚，每次拿一張牌赦抖，將這張牌放在合適的位置要尔，使手中所有紙牌按順序排列匆帚。

void insertion_sort(ele list[], int n){
    /// 最壞情況時間復雜度：O(n*n)
    int i,j;
    ele next;
    for (i = 1; i < n; i++) {
        next = list[i];
        for (j = i - 1; j >= 0 && next.key < list[j].key; j--) {/// 說明不是按照升序排列
            list[j+1] = list[j];
        }
        list[j+1] = next;
    }
}

最壞情況的時間復雜度為：O(n*n)嫉晶，還可以通過檢查輸入表的相對無序性來估計插入排序的計算時間诈火。為了計算相對無序性，需要測量每個記錄是左無序(LOO)的區(qū)域長度。
如果為左無序記錄的個數(shù)淮菠，則插入排序的計算時間為O((k+1)n)碎赢。

??插入排序適用范圍：
當只有少數(shù)紀錄是LOO紀錄時枕赵，插入排序的運行效果很好恋谭。

快速排序

快速排序是平均時間性能非常好的排序方法。在學習快速排序時借鑒了阮一峰的解讀则酝、坐在馬桶上學算法和排序算法動畫演示迟杂。

• 1.找一個基準點（一般是第一個元素），把小于該基準點的放在左邊稱為S1吧雹，大于基準點的放在右邊稱為S2。將S1中找一個基準點摸吠，然后做和上面類似的，左邊稱為S1-1，然后一直遞歸下去S1-1-...1。右邊稱為S1-2肚逸。同理遞歸操作集合中其他的元素务冕。

• 2.在上一條中提到的基準點箩退，我說一般是第一個元素啥刻，這里說一下時間復雜度為O(n*n)的情況，如果在排序之前該組數(shù)據(jù)已經(jīng)是有序排列（升序和降序）的情況收厨。那么怎么選擇基準點呢进栽？一般是找最右邊和最左邊和中間數(shù)字找一個中位數(shù)。

圖解分析

測試一組數(shù)據(jù)：26,5,37,1,61,11,59,14,48,19,55;下圖中提到的i,j在圖中可能看得不清楚恭垦，所以我說明一下：i 用于紀錄在一次移動過程中小于基準點數(shù)據(jù)的下標快毛。j 則相反，它是紀錄大于基準點數(shù)據(jù)的下標番挺。

• 1）唠帝、第一次以26為基準點的元素移動情況：

• 2）、上一步得到的最后序列中操作26左邊部分的的元素：11、5豁鲤、19、1乎赴、14摔竿。
  

• 3）、同樣來操作26左邊部分的的元素：59灾挨、61邑退、48、37劳澄、55地技。

• 4）、通過上訴三步得到如下結(jié)果秒拔，然后使用遞歸的方式分別對基準點11莫矗、59的左右元素進行相同的排序操作。

最后結(jié)果如下：

最后結(jié)果

編碼實現(xiàn)

C語言實現(xiàn)

void quick_sort(int list[], int left, int right);
void quicksort(int list[], int n){
    quick_sort(list, 0, n - 1);
}

void swap(int *lhs,int *rhs){
    int temp = *lhs;
    *lhs = *rhs;
    *rhs = temp;
}
#define AfterMove 1
void quick_sort(int list[], int left, int right){
    
    if (left >= right) {
        return;
    }
    int pivot = list[left];/// 這里我就簡單的取最左邊為基準點
#if AfterMove
    /// 哨兵i,j
    int i = left + 1;
    int j = right;
    while (i < j) {
        /// 先移動i
        while (list[i] < pivot) {
            i++;
        }///找出當前不滿足條件的元素所在的位置
        /// 再移動j
        while (list[j] > pivot) {
            j--;
        }
        if (i < j) {/// 進行元素位置互換
            swap((list + i), (list + j));
        }
    }
    if (*(list + left) > *(list + j)) {
        swap((list + left), (list + j));
    }
#else
    /// 哨兵i,j
    int i = left;
    int j = right + 1;
    do {
        /// 先移動i
        while (list[++i] < pivot) {}///找出當前不滿足條件的元素所在的位置
        /// 再移動j
        while (list[--j] > pivot) {}
        if (i < j) {/// 進行元素位置互換
            swap((list + i), (list + j));
        }
    } while (i < j);
    /// 交換基準點和j位置元素
    swap((list + left), (list + j));
#endif
    /// 遞歸處理當前基準點左右兩邊元素
    quick_sort(list, left, j-1);/// 左邊
    quick_sort(list, j+1, right);/// 右邊
}

調(diào)用砂缩，以及最后的結(jié)果打幼餮琛：

int list[11] = {26,5,37,1,61,11,59,14,48,19,55};
quicksort(list, 11);
for (int i = 0; i < 11; i++) {
  printf("Quick Sort Result is :%d\n",list[i]);
}
Quick Sort Result is :1
Quick Sort Result is :5
Quick Sort Result is :11
Quick Sort Result is :14
Quick Sort Result is :19
Quick Sort Result is :26
Quick Sort Result is :37
Quick Sort Result is :48
Quick Sort Result is :55
Quick Sort Result is :59
Quick Sort Result is :61

Swift實現(xiàn)

swift -v
Apple Swift version 3.1 (swiftlang-802.0.53 clang-802.0.42)

var list:Array<Int> =  [19,30,1,5,13,37,15,29,40,5]

func QuicSort(list:inout Array<Int>){
    __quick_sort(list: &list, left: 0, right: list.count - 1)
}

func __swap(_ lhs:inout Int,_ rhs:inout Int){
    let tmp = lhs
    lhs = rhs
    rhs = tmp
}

func __quick_sort(list:inout Array<Int> ,left:Int ,right:Int) -> Void{
    if left >= right {
        return
    }
    var pivot:Int = list[left]
    /**
    var i:Int = left + 1
    var j:Int = right
    while i < j {
        while list[i] < pivot {
            i = i + 1
        }
        while list[j] > pivot {
            j = j - 1
        }

        if i < j {
            __swap(&list[i], &list[j])
        }
    }
    if list[left] > list[j] {
        __swap(&list[left], &list[j])
    }
    */
    var i:Int = left
    var j:Int = right+1
    
    while i < j{
        repeat{
            i = i + 1
        }while list[i] < pivot
        
        repeat{
            j = j - 1
        }while list[j] > pivot
        
        if i < j {
            __swap(&list[i], &list[j])
        }
    }
    __swap(&list[left], &list[j])
 
    __quick_sort(list: &list, left: left, right:j - 1)/// 左邊
    __quick_sort(list: &list, left: j + 1, right: right)/// 右邊
}

QuicSort(list: &list)
print(list)/// [1, 5, 5, 13, 15, 19, 29, 30, 37, 40]

歸并排序

歸并排序：也是遞歸（迭代）、合并排序庵芭。主要是經(jīng)過兩步妹懒，將一組元素分解成多個子序列，然后使用遞歸或者迭代的方式合并成一個整體序列双吆，在合并的過程對每個子序列進行排序眨唬。

將一組無序的序列分解成多個子序列

/// 將一個數(shù)組分割成length為1的n個子序列（n為原數(shù)組長度）会前，第一步分割子序列
void __merge_sort(int list[], int n){
    int length = 1;
    int tmp_list[n];
    /// 做分割序列，并對每個子序列進行合并
    while (length < n) {
        __merge_pass(list, tmp_list, length, n);
        length *= 2;
        __merge_pass(tmp_list, list, length, n);
        length *= 2;
    }
}

將子序列合并

void __merge_pass(int list[], int tmp[], int length, int n){
    /// 將子序列兩兩進行merge
    int i;
    for (i = 0; i < n - 2*length; i += 2*length) {
        __merge(list, tmp, i, i + length, i + 2*length - 1);
    }
    
    if (i + length < n) {/// 說明當前這個子序列单绑，后面還跟了一個子序列（<n）回官。所以需要merge最后兩個子序列
        __merge(list, tmp, i, i + length, n - 1);
    }else{/// 當前只有一個子序列，直接放入即可
        for (int j = i; j < n; j++) {
            tmp[j] = list[j];
        }
    }
}

在合并子序列時候進行排序

/// ls := left_start
/// rs := right_start
/// re := right_end
void __merge(int list[], int tmp[],int ls,int rs,int re){
    int i,j;
    i = ls;
    j = rs;
    int k = i;/// tmp的下標標量
    while (i < rs && j <= re) {
        tmp[k++] = list[i] <= list[j] ? list[i++] : list[j++];
    }
    while (i < rs) {
        tmp[k++] = list[i++];
    }
    while (j <= re) {
        tmp[k++] = list[j++];
    }
}

調(diào)用

int merge_list[10] = {26,5,77,1,61,11,59,15,48,19};
__merge_sort(merge_list, 10);
for (int i = 0; i < 10; i++) {
  printf("merge_list Sort Result is :%d\n",merge_list[i]);
}

歸并排序存在的最大問題就是需要一個額外的空間來進行排序搂橙！

堆排序

堆排序放在最大堆一節(jié)做說明歉提！

基數(shù)排序

對于基數(shù)排序，其中有兩個重要的概念区转，分別是：MSD（主位優(yōu)先排序）苔巨、LSD（次位優(yōu)先排序）。什么會有這兩種不同的排序方式呢废离？因為基數(shù)排序主要是針對于待排序列紀錄中存在多個關(guān)鍵字侄泽。針對這不同的關(guān)鍵字，導致我們在排序時可以有主位和次位之分蜻韭！
??在基數(shù)排序中悼尾，把排序關(guān)鍵字用基數(shù)r分解為多個數(shù)位。當r=10時肖方，就得到十進制的分解結(jié)果闺魏。當r=2時，就得到二進制的分解結(jié)果俯画。
??下面通過一系列十進制數(shù)排序來說明一下基數(shù)排序析桥。在排序的一系列數(shù)字中最大為3位數(shù):
[179、208艰垂、306泡仗、93、859猜憎、984娩怎、55、9拉宗、271峦树、33

• 1）、 第一遍排序個位數(shù)
  將上訴的數(shù)字根據(jù)個位數(shù)的大小旦事，分別填入對應的鏈表中魁巩。比如當個位數(shù)是9的數(shù)字有179，859姐浮，9三個數(shù)字谷遂，每掃描一邊數(shù)字將前一個數(shù)字的link字段賦值為當前數(shù)字，在下面代碼中展示的并不是直接使用ptr->link = ptr卖鲤，而是用front數(shù)組來保存第一個元素肾扰，并由rear數(shù)組來更新相應的鏈表link字段（具體代碼可看下面??地代碼實現(xiàn)）畴嘶。
  在放入各自鏈表完成之后，我們需要根據(jù)現(xiàn)有的順序集晚，重新放入ptr指針中窗悯，以便進行根據(jù)十位上的數(shù)字再進行一次排序

271 -> 93 -> 33 -> 984 -> 55 -> 306 -> 208 -> 179 -> 859 -> 9

• 2）、 對十位上的數(shù)字進行排序
  經(jīng)過第一排序之后得到數(shù)字序列偷拔，并對該序列上的數(shù)字根據(jù)十位上的數(shù)字同第一步一樣再進心排序蒋院，得到的結(jié)果是:

306 -> 208 -> 9 -> 33 -> 55 -> 859 -> 271 ->179 ->984 -> 93

• 3）、對百位上的數(shù)字進行排序
  同樣是根據(jù)上一步得到的順序莲绰，在該序列的基礎(chǔ)上對序列中數(shù)字百位上的數(shù)字排序欺旧，結(jié)果如下：

9 -> 33 -> 55 -> 93 -> 179 -> 208 -> 271 -> 306 -> 859 -> 984

可以看出在前面三步完成之后，能夠正確將原序列經(jīng)過從小到大的順序排序蛤签。

代碼實現(xiàn)

#undef MAX_DIGIT
#define MAX_DIGIT 3

#undef RADIX_SIZE
#define RADIX_SIZE 10

typedef struct __list_node* list_node_ptr;
typedef struct __list_node{
    int key;
    list_node_ptr link;
}list_node;

/// 排序數(shù)字中最多由三位數(shù)字組成
list_node_ptr digit_sort(list_node_ptr ptr){
    if (!ptr) {
        return NULL;
    }
    list_node_ptr front[RADIX_SIZE],rear[RADIX_SIZE];
    ///1.基數(shù)排序辞友，使用lsd排序，需要有三個基數(shù)：從個位數(shù)震肮，十位數(shù)称龙，百位數(shù)
    int digit,k;
    for (int i = 0; i < MAX_DIGIT; i++) {
        for (k = 0; k < RADIX_SIZE; k++) {
            front[k] = rear[k] = NULL;
        }
        ///2.依次放入上一次順序排列的數(shù)列
        for (; ptr; ptr = ptr -> link) {
            digit = (ptr->key/(int)pow(10, i))%10;/// 拿出該數(shù)字中第個／十／百位上的數(shù)字
            if (!front[digit]) {
                front[digit] = ptr;/// 保證該數(shù)位上有數(shù)據(jù)時，front數(shù)組對應的鏈表元素指向第一個
            }else{
                rear[digit]->link = ptr;/// 這一步實際上是紀錄ptr->link的
            }
            rear[digit] = ptr;///rear始終只想該鏈表的最后一個數(shù)據(jù)
        }
        ptr = NULL;
        ///3.每一輪按照基數(shù)放在對應的數(shù)組里面之后戳晌，需要將其取出茵瀑，按照在front數(shù)組中的順序鏈接ptr
        for (k = RADIX_SIZE - 1; k >= 0; i--) {
            /// 這里解釋一下為什么要用倒敘的方式？為了讓代碼簡單躬厌，我們從位數(shù)上數(shù)字最大的開始，依次向前來鏈接鏈表
            rear[k]->link = ptr;
            ptr = front[k];
        }
    }
    return ptr;
}

內(nèi)部排序總結(jié)

說明：
1竞帽、由于快速排序是遞歸進行的扛施，所以額外的空間復雜度是O(log(N))；
2屹篓、歸并排序由于需要一個額外的temp_list疙渣，故其空間復雜度為O(N)；
3堆巧、由于快速排序妄荔、歸并排序和堆排序的時間復雜度都是O(N*log(N))，但是由于快速排序的前面系數(shù)很小谍肤。平均時間性能啦租，快速排序是最好的；

具體的使用場景：

• 1荒揣、當輸入序列部分有序時篷角，選擇插入排序；
• 2系任、基數(shù)排序的時間復雜度取決于關(guān)鍵字的規(guī)模和基數(shù)的選瓤叶住虐块；
• 3、快速排序的基準點選取也直接影響排序的時間性能嘉蕾；

因此在實際使用中贺奠，把插入排序、快速排序和歸并排序結(jié)合使用错忱，即在歸并排序中使用快速排序來處理子序列儡率，而在快速排序中使用插入排序處理在其遞歸過程中的子序列。