北一女中 資訊選手培訓營

排序演算法

Sorting Algorithm Animations http://www.sorting-algorithms.com/

排序的方法 泡沫排序法(bubble sort) 選擇排序法(selection sort) 插入式排序法(insertion sort) 謝爾排序法(shell sort) 快速排序法(quick sort) 合併排序法(merge sort) 累堆排序法(heap sort) 基數排序法(radix sort) 2019/4/8

泡沫排序法(bubble sort)

泡沫排序法(bubble sort) 假設現在我們需要將 n 筆資料 A1、A2、......、An 由大排到小。 在資料陣列中，由左向右比較，只要資料值比右邊的小，二者就交換 在第一輪比完，最右邊的是最小值 第二輪比較時比到倒數第二筆結束，出現第二小的數值 同樣的，在n-1次迴圈後，資料排序完成 時間複雜度：O(n2) 2019/4/8

氣泡排序法(Bubble Sort) 練習題 1 43 6 79 50 2

氣泡排序法(Bubble Sort)- 第一輪的比較與交換 1 43 6 79 50 2 43 1 6 79 50 2 43 6 1 79 50 2 43 6 79 1 50 2 43 6 79 50 1 2 43 6 79 50 2 1

氣泡排序法(Bubble Sort)- 第二輪的比較與交換 43 6 79 50 2 1 43 79 6 50 2 1 43 79 50 6 2 1

氣泡排序法(Bubble Sort)- Worse Case 執行次數總和為： W(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 = (3n2 - n) / 2 ∈ Ο(n2) 平方時間（quadratic time）的演算法

氣泡排序法(Bubble Sort)- Best Case 執行次數總和為 B(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + 0 = n2 ∈ Ο(n2) 複雜度依舊為平方時間

選擇排序法(Selection Sort)

選擇排序法(Selection Sort) 原理： 將資料分為「已排序」與「未排序」兩部份 從「未排序」的資料中找出最大（最小）值，放入「已排序」資料的最後端。 如是進行，直到排序結束（未排序資料為空）為止。

選擇排序法(Selection Sort) 資料由大排到小 19 58 33 41 28 14 53 84

選擇排序法(Selection Sort) 運作過程

選擇排序法(Selection Sort)

選擇排序法(Selection Sort) 最差情況 所有資料的順序剛好完全相反 使用選擇排序法將 n 筆資料排序 執行次數總和 W(n) = 1 + n + n + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + n = (3n2 + 3n - 2) / 2 ∈ Ο(n2)。

插入式排序法(insertion sort)

插入式排序法(insertion sort) http://notepad.yehyeh.net/Content/Algorithm/Sort/Insertion/1.php

插入式排序法(insertion sort) 原理： 將資料分為「已排序」與「未排序」兩個部份。 再將未排序資料中的第一筆資料插入到已排序資料的適當位置。

插入式排序法(insertion sort) 將資料分成已排序、未排序兩部份 依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置 插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入 比較時，若遇到的值比正處理的值大或相等，則將值往右移

插入式排序法(insertion sort)

插入式排序法(insertion sort) 練習題 35 42 18 91 65 70 52 55 40 82

插入式排序法(insertion sort) Best Case 執行次數總和：B(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + (n - 1) + (n - 1) = 5n - 3 ∈ Ο(n) 複雜度為線性時間

插入式排序法(insertion sort) Worse Case 資料完全反序的最差情況 執行次數總和：W(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + (n - 1) = (3n2 + 3n - 4) / 2 ∈ Ο(n2) 複雜度為平方時間

插入式排序法(insertion sort) 時間複雜度 Best Case：Ο(n) 當資料的順序恰好為由小到大時，每回合只需比較1次 Worst Case：Ο(n2) 當資料的順序恰好為由大到小時，第i回合需比i次 Average Case：Ο(n2) 第n筆資料，平均比較n/2次

快速排序法(quick sort)

快速排序法(quick sort) 排序演算法中，平均效能最佳者 基本方法：採用遞迴的觀念 選取第一個數值為基準(pivot) 將數值資料切割成兩部分： 第一部份的所有元素值都小於基準值 第二部份的所有元素值都大於基準值 兩個部分再分別執行quick sort 2019/4/8

快速排序法(quick sort) http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php

快速排序法(quick sort) 時間複雜度 最佳： O(n log n) 每次切割成平均兩半 平均：O(n log n) 最差：O(n2) 每次切割成1個與n-1個

快速排序法(quick sort) 競賽試題

合併排序法(merge sort)

合併排序法(merge sort) 將數列對分成左子數列、右子數列 分別對左子數列、右子數列作上一個步驟 ⇒ 遞迴(Recursive) 直到左子數列、右子數列被分割成只剩一個元素為止 將僅剩的一個元素作為遞迴的結果回傳 對回傳的左子數列、右子數列依大小排列合併 將合併的結果作為遞迴的結果回傳

合併排序法(merge sort) 將左子數列及右子數列依大小合併成一個新的數列 若左子數列的數值都已填到新的數列 ⇒ 將右子數列中未填過的最小值填入新數列 若右子數列的數值都已填到新的數列 ⇒ 將左子數列中未填過的最小值填入新數列 將左子數列及右子數列中，未填過的最小值填到新的數列

合併排序法(merge sort) http://notepad.yehyeh.net/Content/Algorithm/Sort/Merge/Merge.php

合併排序法(merge sort) 時間複雜度(Time Complexity) Best Case：Ο(n log n) Worst Case：Ο(n log n) Average Case：Ο(n log n) T(n) = MergeSort(左子數列) + MergeSort(右子數列) + Merge = T(n/2) + T(n/2) + c×n = O(n log2n)

合併排序法(merge sort) quick sort的缺點： 採用合併排序法 最差狀況是O(n2) 也就是無法避免切割陣列是否平均 簡化切割原則，每次都切割成一半 以遞迴方式處理 時間複雜度：O(n log n) 2019/4/8

堆積排序法(heap sort)

堆積樹(Heap Tree) 堆積樹(Heap Tree)： 二元樹的一種 ⇒ 每個父節點最多兩個子節點 堆積樹為完全二元樹(Complete Binary Tree)的一種 最小堆積(Min Heap)：父節點的值小於子節點 樹根(root)一定最所有節點的最小值 最大堆積(Max Heap)：父節點的值大於子節點 樹根(root)一定最所有節點的最大值 兄弟節點的大小不重要 堆積排序法為選擇排序法的改良

二元樹調整為Max Heap 二元樹有 floor(n/2)個內部節點 由後往前以每個內部節點為Root，作堆積化(Heapify)

堆積化(Heapify) 令Root的左、右子樹皆符合Heap，僅Root不符合Heap 令Root、左子元素、右子元素3個元素中，最大者為MaxNode 若Root = MaxNode ⇒ 結束 若左子元素或右子元素 = MaxNode 將Root與MaxNode作對調(Swap) 若對調完的Root有子節點 ⇒ 對原來的Root作Heapify

堆積化(Heapify) 範例1 二元樹調整為Max Heap 原始二元樹 http://notepad.yehyeh.net/Content/Algorithm/Sort/Heap/Heap.php

堆積化(Heapify) 範例2 二元樹調整為Max Heap 原始二元樹 http://notepad.yehyeh.net/Content/Algorithm/Sort/Heap/Heap.php

堆積化(Heapify) 競賽試題

Heap Sort Max Heap Heap Sort http://notepad.yehyeh.net/Content/Algorithm/Sort/Heap/Heap.php

堆積排序法 時間複雜度(Time Complexity) Best Case：Ο(n log n) Worst Case：Ο(n log n) Average Case：Ο(n log n) 說明： 建立MaxHeap： Ο(n) 執行n-1次Delete Max：(n-1) × Ο(log n) = Ο( n log n) Ο(n) + Ο( n log n) = Ο( n log n)

各種排序法比較 平均時間複雜度由高到低為： 氣泡排序O(n2) 選擇排序O(n2) 插入排序O(n2) 合併排序O(n log n)

【C++】使用STL內建的sort()、reverse()函式做到排序功能 #include <algorithm> 這個標頭檔 sort() – 由小至大排序 reverse() – 由大至小排序 sort(array_begin,array_end); reverse(array_begin,array_end); array_begin的部份就是開始排序的地方，array_end就是排序的結尾，