排序（插入排序、快排、歸并、基數(shù)排序）

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

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

如果某組信息在內(nèi)存空間中存儲(chǔ)，則稱為表(list)。如果存儲(chǔ)于外存中則稱為文件(file)。把信息中的對(duì)象稱為記錄，每個(gè)記錄的信息劃分為更小的單元，稱為域。
??順序查找對(duì)關(guān)鍵字域沒(méi)有任何限制，而折半查找需要關(guān)鍵字有序的排列。其中折半查找可以使用二叉查找樹(shù)來(lái)描述。

??二叉查找樹(shù)的特征
其左子樹(shù)不大于根節(jié)點(diǎn)值，右子樹(shù)不小于根節(jié)點(diǎn)值。而且各個(gè)子樹(shù)還是一棵二叉查找樹(shù)。

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

插入排序

插入排序類似于玩紙牌時(shí)，每次拿一張牌，將這張牌放在合適的位置，使手中所有紙牌按順序排列。

void insertion_sort(ele list[], int n){
    /// 最壞情況時(shí)間復(fù)雜度：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--) {/// 說(shuō)明不是按照升序排列
            list[j+1] = list[j];
        }
        list[j+1] = next;
    }
}

最壞情況的時(shí)間復(fù)雜度為：O(n*n)，還可以通過(guò)檢查輸入表的相對(duì)無(wú)序性來(lái)估計(jì)插入排序的計(jì)算時(shí)間。為了計(jì)算相對(duì)無(wú)序性，需要測(cè)量每個(gè)記錄是左無(wú)序(LOO)的區(qū)域長(zhǎng)度。
如果為左無(wú)序記錄的個(gè)數(shù)，則插入排序的計(jì)算時(shí)間為O((k+1)n)。

??插入排序適用范圍：
當(dāng)只有少數(shù)紀(jì)錄是LOO紀(jì)錄時(shí)，插入排序的運(yùn)行效果很好。

快速排序

快速排序是平均時(shí)間性能非常好的排序方法。在學(xué)習(xí)快速排序時(shí)借鑒了阮一峰的解讀、坐在馬桶上學(xué)算法和排序算法動(dòng)畫(huà)演示。

  • 1.找一個(gè)基準(zhǔn)點(diǎn)（一般是第一個(gè)元素），把小于該基準(zhǔn)點(diǎn)的放在左邊稱為S1，大于基準(zhǔn)點(diǎn)的放在右邊稱為S2。將S1中找一個(gè)基準(zhǔn)點(diǎn)，然后做和上面類似的，左邊稱為S1-1，然后一直遞歸下去S1-1-...1。右邊稱為S1-2。同理遞歸操作集合中其他的元素。

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

圖解分析

測(cè)試一組數(shù)據(jù)：26,5,37,1,61,11,59,14,48,19,55;下圖中提到的i,j在圖中可能看得不清楚，所以我說(shuō)明一下：i 用于紀(jì)錄在一次移動(dòng)過(guò)程中小于基準(zhǔn)點(diǎn)數(shù)據(jù)的下標(biāo)。j 則相反，它是紀(jì)錄大于基準(zhǔn)點(diǎn)數(shù)據(jù)的下標(biāo)。

  • 1）、第一次以26為基準(zhǔn)點(diǎn)的元素移動(dòng)情況：


自此以第一個(gè)為基準(zhǔn)點(diǎn)的元素移動(dòng)完成，需要注意的是：先由i移動(dòng)，當(dāng)i移動(dòng)停止時(shí)，移動(dòng)j。在i和j的移動(dòng)完成之后，需要i<j才能進(jìn)行位置交換。

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

  • 3）、同樣來(lái)操作26左邊部分的的元素：59、61、48、37、55。

  • 4）、通過(guò)上訴三步得到如下結(jié)果，然后使用遞歸的方式分別對(duì)基準(zhǔn)點(diǎn)11、59的左右元素進(jìn)行相同的排序操作。

最后結(jié)果如下：


最后結(jié)果

編碼實(shí)現(xiàn)

C語(yǔ)言實(shí)現(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];/// 這里我就簡(jiǎn)單的取最左邊為基準(zhǔn)點(diǎn)
#if AfterMove
    /// 哨兵i,j
    int i = left + 1;
    int j = right;
    while (i < j) {
        /// 先移動(dòng)i
        while (list[i] < pivot) {
            i++;
        }///找出當(dāng)前不滿足條件的元素所在的位置
        /// 再移動(dòng)j
        while (list[j] > pivot) {
            j--;
        }
        if (i < j) {/// 進(jìn)行元素位置互換
            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 {
        /// 先移動(dòng)i
        while (list[++i] < pivot) {}///找出當(dāng)前不滿足條件的元素所在的位置
        /// 再移動(dòng)j
        while (list[--j] > pivot) {}
        if (i < j) {/// 進(jìn)行元素位置互換
            swap((list + i), (list + j));
        }
    } while (i < j);
    /// 交換基準(zhǔn)點(diǎn)和j位置元素
    swap((list + left), (list + j));
#endif
    /// 遞歸處理當(dāng)前基準(zhǔn)點(diǎn)左右兩邊元素
    quick_sort(list, left, j-1);/// 左邊
    quick_sort(list, j+1, right);/// 右邊
}

調(diào)用，以及最后的結(jié)果打?。?/p> 

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實(shí)現(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)過(guò)兩步，將一組元素分解成多個(gè)子序列，然后使用遞歸或者迭代的方式合并成一個(gè)整體序列，在合并的過(guò)程對(duì)每個(gè)子序列進(jìn)行排序。

將一組無(wú)序的序列分解成多個(gè)子序列

/// 將一個(gè)數(shù)組分割成length為1的n個(gè)子序列（n為原數(shù)組長(zhǎng)度），第一步分割子序列
void __merge_sort(int list[], int n){
    int length = 1;
    int tmp_list[n];
    /// 做分割序列，并對(duì)每個(gè)子序列進(jì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){
    /// 將子序列兩兩進(jì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) {/// 說(shuō)明當(dāng)前這個(gè)子序列，后面還跟了一個(gè)子序列（<n）。所以需要merge最后兩個(gè)子序列
        __merge(list, tmp, i, i + length, n - 1);
    }else{/// 當(dāng)前只有一個(gè)子序列，直接放入即可
        for (int j = i; j < n; j++) {
            tmp[j] = list[j];
        }
    }
}

在合并子序列時(shí)候進(jìn)行排序

/// 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的下標(biāo)標(biāo)量
    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]);
}

歸并排序存在的最大問(wèn)題就是需要一個(gè)額外的空間來(lái)進(jìn)行排序！

堆排序

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

基數(shù)排序

對(duì)于基數(shù)排序，其中有兩個(gè)重要的概念，分別是：MSD（主位優(yōu)先排序）、LSD（次位優(yōu)先排序）。什么會(huì)有這兩種不同的排序方式呢？因?yàn)榛鶖?shù)排序主要是針對(duì)于待排序列紀(jì)錄中存在多個(gè)關(guān)鍵字。針對(duì)這不同的關(guān)鍵字，導(dǎo)致我們?cè)谂判驎r(shí)可以有主位和次位之分！
??在基數(shù)排序中，把排序關(guān)鍵字用基數(shù)r分解為多個(gè)數(shù)位。當(dāng)r=10時(shí)，就得到十進(jìn)制的分解結(jié)果。當(dāng)r=2時(shí)，就得到二進(jìn)制的分解結(jié)果。
??下面通過(guò)一系列十進(jìn)制數(shù)排序來(lái)說(shuō)明一下基數(shù)排序。在排序的一系列數(shù)字中最大為3位數(shù):
[179、208、306、93、859、984、55、9、271、33

  • 1）、 第一遍排序個(gè)位數(shù)
    將上訴的數(shù)字根據(jù)個(gè)位數(shù)的大小，分別填入對(duì)應(yīng)的鏈表中。比如當(dāng)個(gè)位數(shù)是9的數(shù)字有179，859，9三個(gè)數(shù)字，每掃描一邊數(shù)字將前一個(gè)數(shù)字的link字段賦值為當(dāng)前數(shù)字，在下面代碼中展示的并不是直接使用ptr->link = ptr，而是用front數(shù)組來(lái)保存第一個(gè)元素，并由rear數(shù)組來(lái)更新相應(yīng)的鏈表link字段（具體代碼可看下面??地代碼實(shí)現(xiàn)）。
    在放入各自鏈表完成之后，我們需要根據(jù)現(xiàn)有的順序，重新放入ptr指針中，以便進(jìn)行根據(jù)十位上的數(shù)字再進(jìn)行一次排序
271 -> 93 -> 33 -> 984 -> 55 -> 306 -> 208 -> 179 -> 859 -> 9
  • 2）、 對(duì)十位上的數(shù)字進(jìn)行排序
    經(jīng)過(guò)第一排序之后得到數(shù)字序列，并對(duì)該序列上的數(shù)字根據(jù)十位上的數(shù)字同第一步一樣再進(jìn)心排序，得到的結(jié)果是:
306 -> 208 -> 9 -> 33 -> 55 -> 859 -> 271 ->179 ->984 -> 93
  • 3）、對(duì)百位上的數(shù)字進(jìn)行排序
    同樣是根據(jù)上一步得到的順序，在該序列的基礎(chǔ)上對(duì)序列中數(shù)字百位上的數(shù)字排序，結(jié)果如下：
9 -> 33 -> 55 -> 93 -> 179 -> 208 -> 271 -> 306 -> 859 -> 984

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

代碼實(shí)現(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排序，需要有三個(gè)基數(shù)：從個(gè)位數(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ù)字中第個(gè)／十／百位上的數(shù)字
            if (!front[digit]) {
                front[digit] = ptr;/// 保證該數(shù)位上有數(shù)據(jù)時(shí)，front數(shù)組對(duì)應(yīng)的鏈表元素指向第一個(gè)
            }else{
                rear[digit]->link = ptr;/// 這一步實(shí)際上是紀(jì)錄ptr->link的
            }
            rear[digit] = ptr;///rear始終只想該鏈表的最后一個(gè)數(shù)據(jù)
        }
        ptr = NULL;
        ///3.每一輪按照基數(shù)放在對(duì)應(yīng)的數(shù)組里面之后，需要將其取出，按照在front數(shù)組中的順序鏈接ptr
        for (k = RADIX_SIZE - 1; k >= 0; i--) {
            /// 這里解釋一下為什么要用倒敘的方式？為了讓代碼簡(jiǎn)單，我們從位數(shù)上數(shù)字最大的開(kāi)始，依次向前來(lái)鏈接鏈表
            rear[k]->link = ptr;
            ptr = front[k];
        }
    }
    return ptr;
}

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

排序算法 平均時(shí)間復(fù)雜度 最壞時(shí)間復(fù)雜度 額外空間復(fù)雜度 穩(wěn)定性
插入排序 O(N*N) O(N*N) O(1) 穩(wěn)定
快速排序 O(N*log(N)) O(N*N) O(log(N)) 不穩(wěn)定
歸并排序 O(N*log(N)) O(N*log(N)) O(N) 穩(wěn)定
堆排序 O(N*log(N)) O(N*log(N)) O(1) 不穩(wěn)定
基數(shù)排序 O(P(N+B)) O(P(N+B)) O(N+B) 穩(wěn)定

說(shuō)明：
1、由于快速排序是遞歸進(jìn)行的，所以額外的空間復(fù)雜度是O(log(N))；
2、歸并排序由于需要一個(gè)額外的temp_list，故其空間復(fù)雜度為O(N)；
3、由于快速排序、歸并排序和堆排序的時(shí)間復(fù)雜度都是O(N*log(N))，但是由于快速排序的前面系數(shù)很小。平均時(shí)間性能，快速排序是最好的；

具體的使用場(chǎng)景：

  • 1、當(dāng)輸入序列部分有序時(shí)，選擇插入排序；
  • 2、基數(shù)排序的時(shí)間復(fù)雜度取決于關(guān)鍵字的規(guī)模和基數(shù)的選??；
  • 3、快速排序的基準(zhǔn)點(diǎn)選取也直接影響排序的時(shí)間性能；

因此在實(shí)際使用中，把插入排序、快速排序和歸并排序結(jié)合使用，即在歸并排序中使用快速排序來(lái)處理子序列，而在快速排序中使用插入排序處理在其遞歸過(guò)程中的子序列。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 將一個(gè)記錄插入到已排序好...
    依依玖玥閱讀 1,357評(píng)論 0贊 2
  • 概述 排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部...
    蟻前閱讀 5,306評(píng)論 0贊 52
  • 概述排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的...
    Luc_閱讀 2,379評(píng)論 0贊 35
  • 概述：排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部...
    每天刷兩次牙閱讀 3,829評(píng)論 0贊 15
  • 今天感覺(jué)寫(xiě)作無(wú)從下手，于是隨便從書(shū)柜里取了關(guān)于叔本華的書(shū)，隨便翻到一頁(yè)，談的是關(guān)于女性，越讀下去越感覺(jué)似乎在暗示現(xiàn)...
    宜然閱讀 4,281評(píng)論 0贊 3

友情鏈接更多精彩內(nèi)容