排序有很多種，其中的7種比較類排序是面試中經常問到的內容，因此十分重要！下面將由博主用盡可能簡單明了易懂的方式帶大家去理解它，最終掌握這幾個排序方式后，你就會翻越資料結構之排序這座高山，看到那美麗的來之不易的雨后彩虹啦！
先跟著我一起好好學，學到文末后你就會發現驚喜啦！

在這里插入圖片描述

排序

排序的基本概念
- 定義
- 演算法穩定性
- 應用
插入排序
- 原理
- 實作
- 排序性能分析
希爾排序
- 原理
- 實作
- 排序性能分析
選擇排序
- 原理
- 實作
- 排序性能分析
堆排序
- 原理
- 實作
- 排序性能分析
冒泡排序
- 原理
- 實作
- 排序性能分析
快速排序
- 原理
- 基準的選取（遞回實作快速排序）
- - 挖坑法
  - 三數取中
  - 優化
歸并排序
- 原理
- 遞回實作
- - 實作代碼
  - 測驗
  - 排序性能分析
- 非遞回實作
- 利用歸并實作外部排序
- - 外部排序基本概念
  - 利用歸并思想實作
  - 演算法效率分析
總結
恭喜你掌握了!

排序的基本概念

定義

排序是日常生說中包括計算機中經常進行的一項操作，其目的是將一組"無序"的記錄序列調整為"有序"的記錄序列，
注意：
1.平時背景關系中所提到的排序，默認指的是排升序，而非降序
2.所有的排序演算法不是只能排數字，任何型別的資料都可以排，只要指定了排序的規則即可，比如可以按進制排

演算法穩定性

如果經過排序后，排序演算法能保證其相對位置不發生變化，則我們稱該演算法是具備穩定性的排序演算法，在這里插入圖片描述
如上圖，排好序后紅色的3位于黑色的3之前，相對位置發生了改變，則認為這個排序是不穩定的

應用

在這里插入圖片描述
生活中排序的應用有很多，例如大學的排名，成績的排名等等

插入排序

原理

在一個已經排好的有序資料序列中插入一個數，且要求插入后此資料序列仍然有序，這個時候就要用到一種的排序方法——插入排序法，一般也稱直接插入排序，
排序思想

一般來說，插入排序都采用in-place在陣列上實作，具體演算法描述如下：

從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從后向前遍歷
如果該元素（已排序）大于新元素，將該元素移到下一位置
重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
將新元素插入到該位置后
重復步驟2~5
如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目，該演算法可以認為是插入排序的一個變種，稱為二分查找插入排序，

實作

在這里插入圖片描述
實作代碼：

public static void insertSort(int[] array) {
        for(int i = 1;i < array.length;i++) {//n-1
            int tmp = array[i];
            int j = i-1;
            for(; j >= 0;j--) {//n-1
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else{
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

排序性能分析

若目標是把n個元素的序列升序排列，那么采用插入排序的最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需n-1次即可，最壞情況就是，序列是降序排列，那么此時需要進行的比較共有（1/2）*n(n-1)次，插入排序的賦值操作是比較操作的次數減去n-1次，因為n-1次回圈中，每一次回圈的比較都比賦值多一個，多在最后那一次比較并不帶來賦值），平均來說插入排序演算法復雜度為O（n^2)，因而，插入排序不適合對于資料量比較大的排序應用，但是，如果需要排序的資料量很小，或者若已知輸入元素大致上按照順序排列，那么還是比較適合使用插入排序的
總結

時間復雜度：最好：O（N）；最壞O（N^2）

空間復雜度O（1）

穩定性：穩定

當一組資料的資料量比較少且趨于有序時，用插入排序比較好

資料越有序越快

希爾排序

原理

希爾排序(Shell’s Sort)又稱“縮小增量排序”(Diminishing Increment Sort)，它也是一種屬插入排序類的方法，但在時間率上較前述幾種排序方法有較大的改進，從對直接插入排序的分析得知，其演算法時間復雜度為O(n^2)，但是，若待排記錄序列為“正序”時，其時間復雜度可提高至O(n)，它的基本思想是：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序，

簡單來說，希爾排序主要的思想是對一組資料進行預排序，當資料逐漸接近有序時再進行整體排序，這樣演算法的效率會大大提升

希爾排序的分析是一個復雜的問題，因為它的時間是所取“增量”序列的函式，這涉及一些微學上尚未解決的難題，因此，到目前為止尚未有人求得一種最好的增量序列，增量序列可以有各種取法，但需注意：應使增量序列中的值沒有除1之外的公因子，并且最后一個增量值必須等于1，

實作

在這里插入圖片描述

當gap > 1時都是預排序，目的是讓陣列更接近于有序，當gap == 1時，陣列已經接近有序的了，這樣就會很快，這樣整體而言，可以達到優化的效果

實作代碼：

 public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
public static void shellSort(int[] array) {
        //處理gap
        int gap = array.length;
        while (gap > 1) {
            gap  = gap / 3 + 1;//+1 保證最后一個序列是 1  除幾都行
            // gap /= 2;
            shell(array,gap);
        }
    }

排序性能分析

由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序程序中，相同的元素可能在各自的插入排序中移動，可理解為元素可能會跳躍式移動，所以最后其穩定性就會被打亂，因此shell排序是不穩定的，
時間復雜度：不同的增量序列會產生不同的時間復雜度，比如有人提出當增量序列為在這里插入圖片描述
是，其時間復雜度為
其中t為排序趟數，且：
總結：

穩定性：不穩定

時間復雜度：不確定，但可以記為N^(1.3) 到N^(1.5) 之間

選擇排序

原理

選擇排序（Selection sort）是一種簡單直觀的排序演算法，它的作業原理是每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的資料元素排完，

實作

在這里插入圖片描述
實作代碼：

 public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[i]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

排序性能分析

選擇排序較為簡單，其最好的情況和最壞的情況下程式執行的次數是一樣的，因此時間復雜度是一個定值
總結

時間復雜度：O（N² )

空間復雜度：O（1）

堆排序

原理

堆排序是利用堆這種資料結構設計出的一種排序演算法，其是選擇排序的一種，它利用大頂堆(小頂堆)堆頂元素是最大值(最小值)這一特性，使得每次從無序中選擇最大值(最小值)變得簡單，
排升序要建大堆；排降序要建小堆，

具體步驟如下
step1：先將帶排序的陣列構造成一個大根堆，假設有如下陣列：int[] array2={2,3,4,1,6,5};

在這里插入圖片描述
構造成大根堆如下：

step2：將堆頂元素與堆尾元素交換：在這里插入圖片描述
step3：將除6以外其他的所有元素繼續構造大根堆：
以此類推，然后再將堆頂元素與堆中倒數第二個元素交換，換完之后除了倒數第一個和倒數第二個元素以外，其他元素繼續構造成大堆，最侄訓得到有序的陣列
在這里插入圖片描述
同理，如果要從大到小排，則構建小堆即可！

實作

public static void siftDown(int[] array,int root,int len) {
        int parent = root;
        int child = 2*parent+1;
        while (child < len) {
            //找到左右孩子的最大值
            //1、前提是你得有右孩子
            if(child+1 < len && array[child] < array[child+1]) {
                child++;
            }
            //child的下標就是左右孩子的最大值下標
            if(array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    public static void createHeap(int[] array) {
        //從小到大排序 -》 大根堆
        for (int i = (array.length-1 - 1) / 2;  i >= 0 ; i--) {
            siftDown(array,i,array.length);
        }
    }
    public static void heapSort(int[] array) {
        createHeap(array);//O(n)
        int end = array.length-1;
        while (end > 0) {//O(N*logN)
            int tmp = array[end];
            array[end] = array[0];
            array[0] = tmp;
            siftDown(array,0,end);
            end--;
        }
    }

排序性能分析

時間復雜度：O(N* log(N))（最好和最壞的都是這個）

空間復雜度：O（1）（在整個調整的程序中并沒有重新定義陣列）

穩定性：不穩定

這個堆排序我上一篇博客中有詳細地講過哦，相信大家看完后一定會有識訓的有關堆的相關知識點
在這里插入圖片描述

冒泡排序

原理

冒泡排序（Bubble Sort）是一種簡單的排序演算法，它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來，一直重復進行上述步驟，直到沒有元素再需要交換，也就是說該數列已經排序完成，

實作

在這里插入圖片描述

public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
        }
    }

排序性能分析

時間復雜度：最好/最壞：O（N² ），若優化，則最好的情況下時間復雜度為O（n）

空間復雜度：O（1）

穩定性：穩定

優化方法

 public static void bubbleSort(int[] array) {
        // boolean flg = false;
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
            if(flg == false) {
                break;
            }
        }
    }

設定一個flg，若當前排序時已經有序，可以提前結束本次回圈

快速排序

原理

快速排序是對冒泡排序的一種改進，
排序前首先選擇一個基準值（pivot）將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再對左右兩個區間選取基準值，重復此步驟，采用分治思想，對左右兩個小區間按照同樣的方式處理，直到小區間的長度為1，代表已經有序，或者小區間的長度為0，代表沒有資料，排序完成！整個排序程序可以遞回進行，也可以非遞回進行（如使用堆疊）

基準的選取（遞回實作快速排序）

挖坑法

定義兩個變數，假如陣列的首元素位置下標是low，陣列的尾元素位置下標是high，挖坑法為固定位置選取基準法，比如讓low下標的元素作為基準，讓其存到臨時變數tmp當中，然后將high從后往前遍歷，找比tmp的值小的數字，若找到，則將這個值存到low下標對應的位置中，接著讓low從左到右遍歷去找比tmp的值大的元素，若找到，則將其值存到high下標對應的位置中，以此回圈，直到low和high相遇，那么就把tmp的值放到相遇位置作為基準即可，這樣即可實作把要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小了
在這里插入圖片描述
實作代碼：

public static int partition(int[] array,int low,int high) {
        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] >= tmp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }

有了基準后，就可以進行快速排序的下一步了，然后再對左右兩個小區間選取基準值進行排序，下面我們將使用遞回的方法：

import java.util.Arrays;

public class TestDemo {
    public static int partition(int[] array,int low,int high) {
        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] >= tmp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }
    public static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static void quickSort1(int[] array) {
        quick(array,0,array.length-1);
    }

    public static void main(String[] args) {
        int[] array={12,5,37,41,55,28,6,1,69,17};
        quickSort1(array);
        System.out.println(Arrays.toString(array));
    }
}

列印的結果為：在這里插入圖片描述
排序完成！
性能分析

時間復雜度：
最好情況：O（N*logN）（每一次排序時分割區間都是均勻的）
最壞情況：O（N²）（對已經有序的一對資料排序）

空間復雜度：
最好：O（logN）
最壞：O（N）

穩定性：不穩定

三數取中

對于上述用挖坑法遞回進行快速排序時，因為空間復雜度為O（n），那么當資料足夠多時且越趨于有序而導致排序分割的區間不均勻時，那可能會堆疊溢位（因為遞回是在堆疊上開辟記憶體的），因此，我們可以用三數取中來實作讓排序的區間更趨于均勻，從而提升演算法的效率，
具體思路：
讓low下標等于陣列首元素位置，讓high等于陣列最后一個元素的位置，定義一個mid使其等于陣列的中間位置，然后讓low下標的值等于這三個下標對應的值第二大的，即中間大小的值
實作代碼：

mport java.util.Arrays;

public class TestDemo {
    public static int partition(int[] array,int low,int high) {
        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] >= tmp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }
    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void selectPivotMedianOfThree(int[] array,int start,int end,int mid) {
        //array[mid] <= array[start] <= array[end]
        if(array[mid] > array[start]) {
            swap(array,start,mid);
        }// array[mid] <= array[start]
        if(array[start] > array[end]) {
            swap(array,start,end);
        }// array[start] <= array[end]
        if(array[mid] > array[end]) {
            swap(array,start,end);
        }// array[mid] <= array[end]
    }
    public static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int mid = (start+end)/2;
        selectPivotMedianOfThree(array,start,end,mid);
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static void quickSort1(int[] array) {
        quick(array,0,array.length-1);
    }

    public static void main(String[] args) {
        int[] array={12,5,37,41,55,28,6,1,69,17};
        quickSort1(array);
        System.out.println(Arrays.toString(array));
    }
}

優化

利用遞回法求基準進行快速排序時，當分割的區間越來越小時，其區間內的資料越趨于有序，因此我們可以設定一個區間范圍，然后在這個區間范圍進行直接插入排序，排好序之后就不再遞回了，這樣可以大大提高演算法的效率
直接插入排序部分代碼：

 //判斷兩個下標之間的資料個數
        if(end-start+1 <= 100) {
            insertSort2(array,start,end);//這里要呼叫之前寫好的直接插入排序的代碼
            return;//這里一定要return

利用堆疊（非遞回實作快速排序）

除了上面我們可以利用遞回實作快速排序，我們也可以利用非遞回實作快速排序，其步驟如下：

先選取基準（pivot），以挖坑法為例，

找到基準后，把基準左區間兩端的下標和右區間兩端的下標放入堆疊里

判斷堆疊是否為空，若不為空，則彈出堆疊頂兩個元素，

繼續進行步驟一

注意：當一個區間至少有兩個元素的時候才可以入堆疊，

實作動圖（以找到基準為例）

在這里插入圖片描述

實作代碼：

  public static void quickSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = array.length-1;
        int pivot = partition(array,start,end);
        //左邊有2個元素及以上
        if(pivot > start+1) {
            stack.push(0);
            stack.push(pivot-1);
        }
        if(pivot < end-1) {
            stack.push(pivot+1);
            stack.push(end);
        }
        while (!stack.empty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array,start,end);
            //左邊有2個元素及以上
            if(pivot > start+1) {
                stack.push(0);
                stack.push(pivot-1);
            }
            if(pivot < end-1) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

歸并排序

原理

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序演算法,該演算法是采用分治法（Divide andConquer）的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并
在這里插入圖片描述

遞回實作

實作代碼

import java.util.Arrays;

public class Test {
    public static void merge(int[] array,int low,int mid,int high) {
        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = high;
        int[] tmp = new int[high-low+1];
        int k = 0;//代表tmp陣列的下標:
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            //情況1：說明第2個歸并段沒有了資料 把第1個歸并段剩下的資料 全部拷貝過來
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2) {
            //情況2：說明第1個歸并段沒有了資料 把第2個歸并段剩下的資料 全部拷貝過來
            tmp[k++] = array[s2++];
        }
        //tmp陣列當中 存盤的就是當前歸并好的資料
        for (int i = 0; i < tmp.length; i++) {
            array[i+low] = tmp[i];
        }
    }
    public static void mergeSortInternal(int[] array,int low,int high) {
        if(low >= high) {
            return;
        }
        int mid = (low+high) / 2;
        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid+1,high);
        //合并的程序
        merge(array,low,mid,high);
    }
    public static void mergeSort1(int[] array) {
        mergeSortInternal(array, 0,array.length-1);
    }

測驗

在這里插入圖片描述

排序性能分析

時間復雜度：O（N*logN）（N代表陣列元素的個數，logN代表了二叉樹的高度）

空間復雜度：O（N）（開辟了長度為N的臨時陣列）

穩定性：穩定

非遞回實作

 public static void merge(int[] array,int gap) {
        int[] tmp = new int[array.length];
        int k = 0;
        int s1 = 0;
        int e1 = s1+gap-1;
        int s2 = e1+1;
        int e2 = s2+gap-1 < array.length ?  s2+gap-1 : array.length-1;
        //保證有兩個歸并段
        while (s2 < array.length) {
            while (s1 <= e1 && s2 <= e2) {
                if(array[s1] <= array[s2]) {
                    tmp[k++] = array[s1++];
                }else {
                    tmp[k++] = array[s2++];
                }
            }
            while (s1 <= e1) {
                tmp[k++] = array[s1++];
            }
            while (s2 <= e2) {
                tmp[k++] = array[s2++];
            }
            //一組完了 確定新的區間的開始和結束
            s1 = e2+1;
            e1 = s1+gap-1;
            s2 = e1+1;
            e2 = s2+gap-1 < array.length ?  s2+gap-1 : array.length-1;
        }
        //e2 > array.length
        while (s1 <= array.length-1) {
            tmp[k++] = array[s1++];
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i] = tmp[i];
        }
    }
    public static void mergeSort(int[] array) {
        for (int i = 1; i < array.length; i*=2) {
            merge(array,i);
        }
    }

歸并排序速度僅次于快速排序，為穩定排序演算法，一般用于對總體無序，但是各子項相對有序的數列

利用歸并實作外部排序

外部排序基本概念

本篇本章前段我們討論了的排序方式都屬于基于比較類的排序，也是計算機的內部排序：

內部排序指的是待排序記錄存放在計算機隨機存盤器中進行排序的程序

而計算機中還有一種排序，就是外部排序：

外部排序值的是排序記錄的數量很大，以致記憶體一次不能容納全部記錄，在排序程序中尚需堆外村進行訪問的排序程序

利用歸并思想實作

外部排序基本上由兩個相對獨立的階段組成，首先，按可用記憶體大小，將外存上含n個記錄的檔案分成若干長度為l的子檔案或段(segment)，依次讀入記憶體并利用有效的內部排序方法對它們進行排序，并將排序后得到的有序子檔案重新寫入外存，通常稱這些有序子檔案為歸并段或順串(run)；然后，對這些歸并段進行逐趟歸并，使歸并段(有序的子檔案)逐漸由小至大，直至得到整個有序檔案為止，顯然，第一階段的作業是前面排序部分已經討論過的內容，現在主要討論第二階段即歸并的程序，先從一個具體例子來看外排中的歸并是如何進行的？
假設有一個含10000個記錄的檔案，首先通過10次內部排序得到10個初始歸并段R1～R10，其中每一段都含1000個記錄，然后對它們作如下圖所示的兩兩歸并，直至得到一個有序的檔案為止，

在這里插入圖片描述

從上圖可見，由10個初始歸并段到一個有序檔案，共進行了4趟歸并，每一趟從m個歸并段得到【m/2】個歸并段，這種歸并方法稱為2-路平衡歸并，
將兩個有序段歸并成一個有序段的程序，若在記憶體進行，則很簡單，merge程序便可實作此歸并，但是，在外部排序中實作兩兩歸并時，不僅要呼叫merge程序，而且要進行外存的讀/寫，這是由于我們不可能將兩個有序段及歸并結果段同時存放在記憶體中的緣故，因為對外存上資訊的讀/寫是以“物理塊”為單位的，假設在上例中每個物理塊可以容納200個記錄，則每一趟歸并需進行50次“讀”和50次“寫”，4趟歸并加上內部排序時所需進行的讀/寫使得在外排中總共需進行500次的讀/寫，

演算法效率分析

一般情況下，外部排序所需總的時間=內部排序（產生初識歸并段）所需總的時間（mt[IS]）+外部資訊讀寫的時間（dt[IO]）+內部歸并所需得時間（s*ut[mg]）
其中：t[IS]是為得到一個初始歸并段進行內部排序所需時間的均值；t[IO]是進行一次外存讀/寫時間的均值；ut[mg]是對u個記錄進行內部歸并所需時間；m為經過內部排序之后得到的初始歸并段的個數；s為歸并的趟數；d為總的讀/寫次數，由此，上例10000個記錄利用2-路歸并進行外排所需總的時間為：
10×t[IS]+500×t[IO]+4×10 000t[mg]
其中t[IO]取決于所用的外存設備，顯然，t[IO]較t[mg]要大得多，因此，提高外排的效率應主要著眼于減少外存資訊讀寫的次數d，

總結

在這里插入圖片描述

恭喜你掌握了!

在這里插入圖片描述
你，看見那美麗的彩虹了嗎?就在那櫻花盛開的地方~??

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/297830.html

標籤：java

上一篇：聊聊spring事務失效的12種場景，太坑了

下一篇：世界這么大，你的那一個他肯定會出現，Python表白代碼大集合(附上原始碼）

據說跟我學完【常見排序演算法】后會看見一道雨后彩虹??

排序

排序的基本概念

定義

演算法穩定性

應用

插入排序

原理

實作

排序性能分析

希爾排序

原理

實作

排序性能分析

選擇排序

原理

實作

排序性能分析

堆排序

原理

實作

排序性能分析

冒泡排序

原理

實作

排序性能分析

快速排序

原理

基準的選取（遞回實作快速排序）

挖坑法

三數取中

優化

歸并排序

原理

遞回實作

實作代碼

測驗

排序性能分析

非遞回實作

利用歸并實作外部排序

外部排序基本概念

利用歸并思想實作

演算法效率分析

總結

恭喜你掌握了!