第 10 次社課講義 - HackMD

<style> .reveal .slides { font-size: 40px; } </style> # 南大附中資訊研究社 NFIRC 1st ## 第 10 次社課講義 2024/04/17 主講：ShiYu --- ## 課前準備 ---- ## 今日課程內容 # 排序演算法 ## 1. 氣泡排序法 ## 2. 選擇排序法 ## 3. 插入排序法 ## 進階：合併排序法 --- ## 什麼是排序演算法？ ---- ## 什麼是排序演算法？將資料以特定規則重新排列 ---- ### 上次已經教過了 C++ 內建的 sort 函式了 ## 為什麼還要學排序演算法？ ---- ### 上次已經教過了 C++ 內建的 sort 函式了 ## 為什麼還要學排序演算法？  真正去學習演算法才能培養解決問題的能力 ---- ## 在還沒學過排序演算法之前先請各位到前面以自己的方式嘗試排序一下撲克牌 --- ## 1. 氣泡排序法 Bubble Sort 每次交換相鄰元素重複直到完成排序動畫：https://visualgo.net/zh/sorting ---- ## 實際操作 ---- ## 實作 Code ```cpp= void BubbleSort() { int n = v.size(); for (int i=n; i>1; --i) { for (int j=0; j<i-1; ++j) { if (v[j] > v[j+1]) { swap(v[j],v[j+1]); } } } } ``` ---- ## 時間複雜度是多少？ ---- ## 時間複雜度是多少？有 n 個元素要浮上來每個元素都需要遍歷一次數列所以為 $n^2$ --- ## 2. 選擇排序法 Selection Sort 選擇最小的元素放到前面重複直到完成排序動畫：https://visualgo.net/zh/sorting ---- ## 實際操作 ---- ## 實作 Code ```cpp= void SelectionSort() { int n = v.size(); for (int i=0; i<n-1;++i) { int mini = i; for (int j=i; j<n; ++j) { if (v[j] < v[mini]) { mini = j; } } swap(v[i],v[mini]); } } ``` ---- ## 時間複雜度是多少？ ---- ## 時間複雜度是多少？每次找最小的元素需要遍歷整個數列要遍歷 n 次才能讓整個數列完成排序所以為 $n^2$ --- ## 3. 插入排序法 Insertion Sort 將未排序的元素依對應位置插入已排序好的序列動畫：https://visualgo.net/zh/sorting ---- ## 實際操作 ---- ```cpp= void InsertSort() { int n = v.size(); for (int i=1; i<n;++i) { int temp = v[i], j = i-1; while (j >= 0 && temp < v[j]) { v[j+1] = v[j]; j--; } v[j+1] = temp; } } ``` ---- ## 時間複雜度是多少？ ---- ## 時間複雜度是多少？要遍歷 n 個元素並往前搬動到序列中所以為 $n^2$ --- ## 進階：合併排序法 Merge Sort 一種以分治法為核心概念的排序演算法不斷的將數列切分成兩個小數列再將兩個小數列以特定方式合併成有序透過遞迴就可完成排序動畫：https://visualgo.net/zh/sorting ---- ## 實際操作 ---- ```cpp= void merge(int l, int r) { int mid = (l+r)/2, tmp[r-l+1]; for(int i=l,j=mid+1,k=0; i<=mid || j<=r; ++k) { if((v[i] <= v[j] && i <= mid) || j > r) tmp[k] = v[i++]; else tmp[k] = v[j++]; } for(int i=l,j=0; i<=r; ++i,++j) v[i] = tmp[j]; } void MergeSort(int l, int r) { if(l == r) return; int mid = (l+r)/2; MergeSort(l,mid); MergeSort(mid+1,r); merge(l,r); } ``` ---- ## 時間複雜度是多少？ ---- ## 時間複雜度是多少？每次都將數列切成兩半 $\log n$ 把兩段數列合併成一段 $n$ 所以是 $n \log n$ --- ## 這麼多種排序演算法 ## 我該選哪種？ ---- ## 比較各種排序演算法 | 排序演算法 | 最差時間複雜度 | 空間複雜度 | | --- | --- | --- | | 氣泡排序 | $O(n^2)$ | $O(1)$ | | 選擇排序 | $O(n^2)$ | $O(1)$ | | 插入排序 | $O(n^2)$ | $O(1)$ | | 合併排序 | $O(n\log n)$ | $O(n)$ | --- ## 實作練習 ### [ZJ a104. 排序](https://zerojudge.tw/ShowProblem?problemid=a104) 這題大家在之前的提單有用內建的 sort 函式寫過可以試著用氣泡、選擇、插入排序分別來寫寫看 ---- ## 進階題 ### [ZJ a233. 排序法挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233) 這題用前三種複雜度 $n^2$ 的排序演算法會 TLE 要用 Merge sort 才會過複雜度 $n \log n$ --- ## 延伸閱讀詳細介紹 10 種不同的排序演算法 ## [ShiYu Blog 文章連結](https://shiyu0318.github.io/post/Sort-Algorithm/)