【数据结构】排序算法及优化整理
排序算法
- 排序算法
- 選擇排序 Selection Sort
- 插入排序 Insertion Sort
- 歸并算法 Merge Sort
- 快速排序 Quick Sort
- 堆排序 Heap Sort
- 二叉堆的基礎操作
- 堆的初始化
- Shift Up 往最大堆中添加一個元素
- ShiftDown 從堆中取出一個元素
- 基礎堆排序和Heapify
排序算法
選擇排序 Selection Sort
-
思路：每次遍歷找到剩余數(shù)組中最小的元素，并依次swap到數(shù)組開頭
-
時間復雜度：O(n^2)
template <typename T> void selectionSort(int arr[], int n) {for( int i = 0; i < n; i ++ ) {// 尋找[i ... n-1]的最小值int minIndex = i;for( int j = i; j < n; j ++ ) if(arr[j] < arr[minIndex])minIndex = j;swap(arr[i], arr[minIndex]);} }
插入排序 Insertion Sort
- 思路：將選定元素排到前序合適的位置上（類似撲克理牌的思路
遍歷到6時，6應該放在8的前面，于是將6和8調換位置；
下一個是2，首先2比8小，所以2和8調換位置；2也比6小，于是2和6調換位置。
以此類推。
-
時間復雜度：O(n^2)
template <typename T> void insertionSort(T arr[], int n) {for( int i = 1; i < n; i ++ ) { // i = 1開始，因為i = 0時只有一個元素不需要排序// 尋找元素arr[i]合適的插入位置for( int j = i; j > 0; j -- ) { // j > 0 非 j >= 0，因為每次都將arr[j]和arr[j-1]比較// 避免j-1越界，所以j最小只能到1if( arr[j-1] <= arr[j] )break;else // arr[j-1] > arr[j]swap(arr[j], arr[j-1]);}// for( int j = 1; j > 0 && arr[j-1] > arr[j]; j -- )// swap(arr[j], arr[j-1]);} } -
優(yōu)化
當前的算法在每次循環(huán)中要swap很多次，減少賦值操作的次數(shù)。
當考察元素2時，先將2復制出一份；
考察2前一個元素8，因為8比2大所以2不應該放在當前位置，將8賦值2的位置；
再向前考察8的位置，2比當前位置前一個元素6要小，所以2也不應該在這個位置，將6賦值2的當前位置；
再向前考察6的位置，當前位置沒有前一個元素，所以2只能放在當前位置。
swap操作是三次賦值，這樣優(yōu)化成一次賦值
template <typename T> void insertionSort(T arr[], int n) {for( int i = 1; i < n; i ++ ) { // i = 1開始，因為i = 0時只有一個元素不需要排序// 尋找元素arr[i]合適的插入位置T e = arr[i];int j; // 保存元素e應該插入的位置for( j = i; j > 0; j -- ) { // j > 0 非 j >= 0，因為每次都將arr[j]和arr[j-1]比較// 避免j-1越界，所以j最小只能到1if( arr[j-1] > e )arr[j] = arr[j-1];else // arr[j-1] <= ebreak;}// for( int j = 1; j > 0 && arr[j-1] > e; j -- )// arr[j] = arr[j-1];arr[j] = e;} }在近乎有序的數(shù)組中，插入排序的性能要遠遠優(yōu)于選擇排序。
歸并算法 Merge Sort
-
排序思路：
先將整個數(shù)組不斷分割，然后向上歸并排序。
時間復雜度：O(nlogn)
-
具體實現(xiàn)
#include <iostream> #include <algorithm>using namespace std;// 將arr[l ... mid]和arr[mid+1 ... r]兩部分進行歸并 template <typename T> void __merge( T arr[], int l, int mid, int r ) {T aux[r-l+1];for( int i = l; i <= r; i ++ )aux[i-l] = arr[i];int i = l, j = mid + 1;for( int k = l; k <= r; k ++ ) if( i > mid ) {arr[k] = aux[j-l];j ++;}else if( j > mid ) {arr[k] = aux[i-l];i ++;}else if( aux[i-l] < aux[j-l] ) {arr[k] = aux[i-l];i ++;}else {arr[k] = aux[j-l];j ++;} }// 遞歸使用歸并排序，對arr[l ... r]的范圍進行排序（重點：左閉右閉 template <typename T> void __mergeSort( T arr[], int l, int r ) {if( l >= r ) return;int mid = l + (r - l) / 2; // 防止溢出 __mergeSort(arr, l, mid);__mergeSort(arr, mid + 1, r);__merge(arr, l, mid, r); }template <typename T> void mergeSort( T arr[], int n ) {__mergeSort(arr, 0, n - 1); } -
優(yōu)化：
-
在輸入數(shù)組近乎有序的情況下，歸并排序會退化為O(n^2)
因為在這部分中
template <typename T> void __mergeSort( T arr[], int l, int r ) {if( l >= r ) return;int mid = l + (r - l) / 2; // 防止溢出 __mergeSort(arr, l, mid);__mergeSort(arr, mid + 1, r);、// 不管兩部分排序情況如何，都會進行一遍merge__merge(arr, l, mid, r); }如果左半邊的最后一個元素比右半邊的第一個元素還要小，說明數(shù)組已經(jīng)是有序的了，不需要再進行merge操作，代碼可優(yōu)化如下：
template <typename T> void __mergeSort( T arr[], int l, int r ) {if( l >= r ) return;int mid = l + (r - l) / 2; // 防止溢出 __mergeSort(arr, l, mid);__mergeSort(arr, mid + 1, r);、if(arr[mid] > arr[mid+1])__merge(arr, l, mid, r); }這樣已經(jīng)對近乎有序的數(shù)組有一定程度的優(yōu)化，但歸并排序無法優(yōu)化到O(n)級別，但插入排序可以。
所以在數(shù)組近乎有序的時候最好使用插入排序。
-
在歸并到最后數(shù)據(jù)量比較小的時候可以采用插入排序
因為此時數(shù)據(jù)近乎有序的可能性比較大。
template <typename T> void __mergeSort( T arr[], int l, int r ) { // if( l >= r ) // return;if( r - l <= 15 ) { // 取值并非最優(yōu)，只是舉例insertionSort(arr, l, r);return;}int mid = l + (r - l) / 2; // 防止溢出 __mergeSort(arr, l, mid);__mergeSort(arr, mid + 1, r);、if(arr[mid] > arr[mid+1])__merge(arr, l, mid, r); } -
自底向上的歸并排序
不需要遞歸只需要迭代
template <typename T> void mergeSortBU( T arr[], int n ) {for( int sz = 1; sz <= n; sz += sz ) for( int i = 0; i + sz < n; i += sz + sz ) // 對 arr[i ... i+sz-1] 和 arr[i+sz ... i+sz+sz-1] 進行歸并__merge( arr, i, i + sz - 1, min(i + sz + sz - 1, n-1) ); // 注意數(shù)組越界問題 }雖然說性能差不多，但是自頂向下要快一點。
但沒有使用到數(shù)組的特性：用索引直接獲取元素。所以這個算法可以在O(nlogn)下對鏈表之類的數(shù)據(jù)結構進行排序。
-
快速排序 Quick Sort
-
關鍵步驟 Partition
把每個數(shù)字都放在合適的位置
一般選取數(shù)組的第一個元素
時間復雜度：O(nlogn)
-
代碼實現(xiàn)
// 對arr[l ... r]部分進行partition操作 // 返回p，使得arr[l ... p-1] < arr[p]; arr[p+1 ... r] > arr[p] template <typename T> int __partition(T arr[], int l, int r) {T v = arr[l];// arr[l+1 ... j] < v; arr[j+1 ... i-1] > vint j = l; // 是l不是l+1，因為要保證開始的arr[l+1 ... j]和arr[j+1 ... i-1]都是空for( int i = l + 1; i <= r; i ++ ) {if(arr[i] < v) {swap(arr[j+1], arr[i]);j++;// swap(arr[++j], arr[i]);}// 如果arr[i] >= v// 只需要進行i++即可}swap(arr[l], arr[j]);return j; }// 對arr[l ... r]部分進行快速排序 template <typename T> void __quickSort(T arr[], int l, int r) {if(l >= r)return;int p = __partition(arr, l, r);__quickSort(arr, l, p-1);__quickSort(arr, p+1, r); }template <typename T> void quickSort(T arr[], int n) {__quickSort(arr, 0, n-1); } -
優(yōu)化：
-
在最后數(shù)據(jù)量較少時也可以直接使用插入排序
// 對arr[l ... r]部分進行快速排序 template <typename T> void __quickSort(T arr[], int l, int r) {if(r - l <= 15) {insertionSort(arr, l, r);return;} int p = __partition(arr, l, r);__quickSort(arr, l, p-1);__quickSort(arr, p+1, r); }優(yōu)化力度不大，并不是主要優(yōu)化方法
-
在近乎有序的數(shù)組中：
每次選擇的標定元素所partition出的左右兩邊數(shù)組元素個數(shù)是極不平衡的，因為數(shù)組近乎有序，第一個元素往往是最小的。
循環(huán)往復，Quick Sort的時間復雜度會退化到O(n^2)。
解決方法：隨機選取標定元素
// 對arr[l ... r]部分進行partition操作 // 返回p，使得arr[l ... p-1] < arr[p]; arr[p+1 ... r] > arr[p] template <typename T> int __partition(T arr[], int l, int r) {swap(arr[l], arr[rand()%(r - l + 1) + l]); // 隨機選擇標定元素！T v = arr[l];// arr[l+1 ... j] < v; arr[j+1 ... i-1] > vint j = l; // 是l不是l+1，因為要保證開始的arr[l+1 ... j]和arr[j+1 ... i-1]都是空for( int i = l + 1; i <= r; i ++ ) {if(arr[i] < v) {swap(arr[j+1], arr[i]);j++;// swap(arr[++j], arr[i]);}// 如果arr[i] >= v// 只需要進行i++即可}swap(arr[l], arr[j]);return j; }template <typename T> void quickSort(T arr[], int n) {srand(time(NULL)); // 隨機種子__quickSort(arr, 0, n-1); }經(jīng)過優(yōu)化后會好很多，但還是沒有歸并排序快。
-
兩路快排
擁有大量重復鍵值元素的數(shù)組中，快排的性能很差
因為在之前的partition操作中，如果元素 = v，則會被分到 > v 的一組。當數(shù)組中有大量重復鍵值元素的時候，兩端會極不平衡。
時間復雜度會退化到O(n^2)。
-
換一個思路：將 > v 的元素放在最右邊
- 將 i 向后移直到遇到 >= v 的元素，然后將 j 向前移直到遇到 <= v 的元素。
-
然后交換 i 和 j 的位置
i 繼續(xù)向后，j 繼續(xù)向前，直到i和j重合。 -
此時其實橙色部分表示的是 <= v 的元素，而紫色部分表示的是 >= v 的元素。
這個方法其實是將 == v 的元素分散到左右兩邊了，避免兩端不平衡。
// 對arr[l ... r]部分進行partition操作 // 返回p，使得arr[l ... p-1] < arr[p]; arr[p+1 ... r] > arr[p] template <typename T> int __partition(T arr[], int l, int r) {swap(arr[l], arr[rand()%(r - l + 1) + l]); // 隨機選擇標定元素！T v = arr[l];// arr[l+1 ... i-1] <= v; arr[j+1 ... r] >= vint i = l+1, j = r;while(true) {while(i <= r && arr[i] < v) i ++；while(j >= l + 1 && arr[j] > v)j --;if(i > j) break;swap(arr[i], arr[j]);i ++;j --;}swap(arr[l], arr[j]);return j; } -
三路快排
將數(shù)組分割成小于v，等于v和大于v。
-
當 arr[i] == v 時，只需要 i ++ 即可；
-
當 arr[i] < v 時，swap( arr[lt + 1], arr[i] ) ，然后 lt ++, i ++；
-
當 arr[i] > v 時，swap( arr[gt - 1], arr[i] ) ，然后 gt --；
這里 i 不加了，因為arr[gt - 1] 沒被處理過，需要再次判斷
-
最后 gt 和 i 重合表示處理結束。
-
swap(arr[l], arr[lt])
-
然后將小于v的部分和大于v的部分進行再次排序
堆排序 Heap Sort
-
優(yōu)先隊列 Priority Queue
普通隊列：先進先出，后進后出
優(yōu)先隊列：出隊順序和入隊順序無關，和優(yōu)先級相關
入隊出隊 普通數(shù)組 O(1) O(n) 順序數(shù)組 O(n) O(1) 堆 O(logn） O(logn)
二叉堆的基礎操作
任何節(jié)點的值都不大于它的父節(jié)點（最大堆：樹頂?shù)脑厥亲畲蟮闹?#xff09;
是一棵完全二叉樹，用數(shù)組來存儲整個堆
根節(jié)點從1開始標記
parent(i) = i/2
left_child(i) = 2*i
right_child(i) = 2*i + 1
堆的初始化
template<typename Item> class MaxHeap { private:Item* data;int count; public:MaxHeap(int capacity) {data = new Item[capacity + 1]; // 因為索引是從1開始的count = 0;}~MaxHeap() {delete[] data;}int size() {return count;}bool isEmpty() {return count == 0;} };Shift Up 往最大堆中添加一個元素
添加元素到數(shù)組的尾部
但不滿足堆的定義，需要將新加入的元素調整到一個合適的位置以滿足堆的定義
和父節(jié)點進行比較，如果比父節(jié)點大則交換
在public中添加一個新的函數(shù) insert
void insert(Item item) {assert(count + 1 <= capacity);data[count + 1] = item; // 隱藏數(shù)組越界的問題count++;ShiftUp(count);}在private里添加ShiftUp函數(shù)，通過遞歸將新插入的元素調整到合適位置
- 步驟：判斷當前元素與其parent的值的大小，如果當前元素比parent大，說明位置不合適，需要將其與parent互換，然后仍指向交換后的元素（已在parent的位置）。
ShiftDown 從堆中取出一個元素
即只能取出根節(jié)點元素（最大值），然后將數(shù)組中的最后一個元素放到根節(jié)點中，相應的count --，來保證是一個完全二叉樹。
但此時并不符合堆的定義，接下來就是調整元素位置來恢復成一個合理的最大堆（即將根節(jié)點一步一步向下挪到合適的位置 ——> ShiftDown）
- 步驟：如果子節(jié)點比當前節(jié)點大，則跟子節(jié)點中最大的那個交換位置，直到子節(jié)點的值都比當前節(jié)點小或當前節(jié)點是葉子節(jié)點。
在public里添加函數(shù)ExtractMax（根節(jié)點元素是最大值）
Item ExtractMax() {assert(count > 0); // 首先保證堆里有元素Item ret = data[1];swap(data[1], data[count]);count--; // 已經(jīng)取出了一個元素，所以count --ShiftDown(1); // 將當前根節(jié)點向下移直到移到合適位置return ret;}在private里添加函數(shù)ShiftDown
void ShiftDown(int k) {while (2 * k < count) { // 判斷是否有孩子，只要有左孩子就是有孩子了int j = 2 * k; // j指向k的左孩子，j最終要指向需要和k交換的那個孩子if (j + 1 <= count && data[j + 1] > data[j]) // 如果有右孩子并且比左孩子大j += 1; // 那么j指向更大的那個孩子if (data[k] > data[j]) // 如果k比j所指的值還大，則說明k已經(jīng)在合適的位置了break;swap(data[j], data[k]); // 否則k就應該和最大的孩子交換位置k = j; // 并更新k的值進行下一輪ShiftDown}}基礎堆排序和Heapify
- 實現(xiàn)一個基礎的堆排序
這個實現(xiàn)中，先要遍歷整個數(shù)組來建立堆（O(nlogn)），再要將所有的元素取出（O(nlogn)），可以進一步優(yōu)化只需要遍歷一遍(O(n))就建立成堆。
-
優(yōu)化：Heapify
給定一個數(shù)組，將數(shù)組的排列變成堆的形狀
所有的葉子節(jié)點可以看做成五個最大堆，而下標為 arr.size() / 2 的元素是第一個非葉子節(jié)點的節(jié)點，是第一個需要考察的節(jié)點。
第一個考慮 arr[5] = 22，子節(jié)點的值比它大，不符合最大堆性質，直接進行ShiftDown操作就可以，這棵子樹就符合了最大堆性質。
下一個需要考慮的節(jié)點下標為4，選擇子節(jié)點中值最大的那個來ShiftDown，那么這棵子樹也滿足了最大堆的性質。
下一個需要考慮的節(jié)點下標為3，選擇子節(jié)點中最大的那個ShiftDown，那么這棵子樹也滿足了最大堆的性質。
下一個需要考慮的節(jié)點下標為2，選擇子節(jié)點中最大的那個ShiftDown，arr[5] = 17 子節(jié)點為22，不符合最大堆性質，則繼續(xù)ShiftDown直到滿足性質。
最后一個需要考慮的是根節(jié)點 15 ，將與子節(jié)點ShiftDown到底，恢復整個最大堆的性質。
-
代碼實現(xiàn)：
template<typename Item> class MaxHeap { private:Item* data;int count; public:MaxHeap(int capacity) {data = new Item[capacity + 1]; // 因為索引是從1開始的count = 0;}MaxHeap(Item arr[], int n) { // heapifydata = new Item[n+1];capacity = n;for(int i = 0; i < n; i ++) data[i+1] = arr[i];count = n;for( int i = count / 2; i >= 1; i -- ) // 從第一個非葉子節(jié)點開始shiftDown(i);}~MaxHeap() {delete[] data;}int size() {return count;}bool isEmpty() {return count == 0;} };時間復雜度：O(n)
-
手撕排序
#include <iostream> #include <vector>using namespace std; void ShiftDown(vector<int>& arr, int k, int n) {// 從0開始索引的，所以判斷時需要加1while (2 * k + 1 < n) {int j = 2 * k + 1;if (j + 1 < n && arr[j + 1] > arr[j])j += 1;if (arr[j] < arr[k])break;swap(arr[j], arr[k]);k = j;} } void heapify(vector<int>& arr, int n) {// 注意，此時我們的堆是從0開始索引的// 從(最后一個元素的索引-1)/2開始// 最后一個元素的索引 = n-1for (int i = (n - 2) / 2; i >= 0; i--)ShiftDown(arr, i, n);// 到此為止只能說是遵守了最大堆規(guī)則// 并沒有排序// 接下來的for循環(huán)實現(xiàn)從小到大排序for (int i = n - 1; i >= 0; i--) {swap(arr[0], arr[i]);ShiftDown(arr, 0, i);} }int main() {vector<int> arr{ 3,5,7,3,6,1,4 };int n = arr.size();heapify(arr, n);for (int i = 0; i < n; i++)cout << arr[i] << " ";return 0; }
總結
以上是生活随笔為你收集整理的【数据结构】排序算法及优化整理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 《Linux高性能服务器编程》学习笔记
- 下一篇： 【C++】多继承