基礎排序 - HackMD

生活中的例子

一堆散落的紙有頁碼，我們想把它重新排成一本書。
要把學生的成績由大到小排序。
…

給你一個長度為n的序列
你要把他們由小到大排序

Swap

先介紹基於比較、交換的演算法。

 a, b = b, a

何謂演算法？
我們能自己想到排序演算法嗎？

Bubble Sort

從序列的最前面開始，一次比較陣列中兩兩相鄰的元素，然後根據將大的移到後面。
當我們比較過所有元素一次後，可以確保數值最大的元素在最後面。
接著扣掉陣列中的最後一個元素，接著重複上面的步驟進行兩兩比較。

Bubble Sort

void BubbleSort(int arr[], int n) {
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
        }
    }
}

Selection Sort

在序列中找到最小的元素，並將他與第一個元素交換。
在序列中找到第二小的元素(也就是撇除掉第一個元素後的最小的元素)，並將他與第二個交換。
重複以上操作，直到排序好。

Selection Sort

void SelectionSort(int arr[], int n) {
    for(int i = 0; i < n - 1; i++) {
        int min = i;
        for(int j = i + 1; j < n; j++) {
            if(arr[j] < arr[min]) min = j;
        }
        swap(arr[i], arr[min]);
    }
}

Insertion Sort

想像序列中有一部分是已經排序好的，那每次新增一個元素就去看他要插在排序好的序列的哪裡。
對於陣列中第 i 個值，假設 0 ~ i - 1 都排序好了，把 i 往左比較找到第一個小於他的元素並插在他右邊。

Insertion Sort

void InsertionSort(int arr[], int n) {
    for(int i = 1; i < n; i++) {
        int j = i - 1;
        while (j >= 0 && arr[j] > arr[j + 1]) {
            swap(arr[j], arr[j + 1]);
            j--;
        }
    }
}

Quick Sort

Merge Sort

複雜度分析

Bubble Sort
- Best: \(O(n^2)\), Worst \(O(n^2)\)
Selection Sort
- Best: \(O(n^2)\), Worst \(O(n^2)\)
Insertion Sort
- Best: \(O(n)\), Worst \(O(n^2)\)
Quick Sort
- Worst \(O(n^2)\), Average \(O(nlogn)\)
Merge Sort
- \(O(nlogn)\)

Bubble Sort 若在迴圈執行時，判斷這一輪是否都沒有任何元素交換，可以把最優情況下的複雜度降低到 \(O(n)\)。
Insertion Sort 若把內層迴圈改成二分搜，就可以優化成 \(O(nlogn)\)。

有複雜度比 \(O(nlogn)\) 更好的排序方法嗎？

基於比較的排序演算法最好就是 \(O(nlogn)\)

優質文章

不基於比較的排序方法

Counting Sort
Bucket sort
radix sort

Counting Sort

假如數值介於 0 ~ 999，我們就開一個長度為1000的陣列去記每一種數字出現幾次。
最後由小到大輸出

Counting Sort

const int size = 1000;
void CountingSort(int arr[], int n) {
    int cnt[size] = {0};
    for(int i = 0; i < n; i++) {
        cnt[arr[i]]++;
    }
    int id = 0;
    for(int i = 0; i < size; i++) {
        while(cnt[i] > 0) {
            arr[id] = i;
            id++;
            cnt[i]--;
        }
    }
}

Counting Sort

時間複雜度是 \(O(n)\) 嗎?

Counting Sort

k 為數字範圍
時間複雜度 \(O(n + k)\)

上課練習

neoj 369

既然都有 \(O(nlogn)\) 的排序演算法了，那些\(O(n^2)\)的演算法根本不會被用到吧？

當序列長度不大的時候，Insertion Sort等等反而會比Quick Sort, Merge Sort還來得有效率。
reference

我不想自己寫SortQQ
std::sort

#include <algorithm>

int a[1000];
std::sort(a, a + 5);

酷酷的影片

Homework
neoj 2219