# 基礎排序 2020竹C, jeeeerrrpop --- ## 生活中的例子 - 一堆散落的紙有頁碼，我們想把它重新排成一本書。 - 要把學生的成績由大到小排序。 - ........ --- {%youtube WaNLJf8xzC4%} --- 給你一個長度為n的序列 你要把他們由小到大排序 --- ## Swap 先介紹基於比較、交換的演算法。 ```python= a, b = b, a ``` --- 何謂演算法？ 我們能自己想到排序演算法嗎？ --- ## Bubble Sort - 從序列的最前面開始，一次比較陣列中兩兩相鄰的元素，然後根據將大的移到後面。 - 當我們比較過所有元素一次後，可以確保數值最大的元素在最後面。 - 接著扣掉陣列中的最後一個元素，接著重複上面的步驟進行兩兩比較。 --- ## Bubble Sort ```cpp 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 ```cpp 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 ```cpp 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 [Quick Sort](http://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html) --- ## Merge Sort [Merge Sort](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html) --- ## 複雜度分析 - 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)$ [優質文章](https://tmt514.github.io/algorithm-analysis/sorting/comparison-based-sorting.html#定理-18) --- ## 不基於比較的排序方法 - Counting Sort - Bucket sort - radix sort --- ## Counting Sort - 假如數值介於 0 ~ 999，我們就開一個長度為1000的陣列去記每一種數字出現幾次。 - 最後由小到大輸出 --- ## Counting Sort ```cpp 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](https://neoj.sprout.tw/problem/369/) --- 既然都有 $O(nlogn)$ 的排序演算法了，那些$O(n^2)$的演算法根本不會被用到吧？ --- 當序列長度不大的時候，Insertion Sort等等反而會比Quick Sort, Merge Sort還來得有效率。 [reference](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html) --- 我不想自己寫SortQQ [std::sort](http://www.cplusplus.com/reference/algorithm/sort/) --- ```cpp #include <algorithm> int a[1000]; std::sort(a, a + 5); ``` --- 酷酷的影片 {%youtube kPRA0W1kECg%} --- Homework [neoj 2219](https://neoj.sprout.tw/problem/2219/)