文章目錄
- 前言
- 歸并排序
- 快速排序
- 最后
前言
先來看看這兩個排序在常見的排序中的速度比較（50個亂數）：
再來看看資料放大四倍后（200個亂數）的速度：
可見這兩位大哥在所有的排序中脫穎而出，在此app里資料量較少的時候，快速排序比歸并排序要快，資料量變大后，快排略遜一籌，是不是真的呢？讓我們來一起學習康康，
（區別于文章末尾的測驗）
（截圖源自手機APP：C語言學習寶典）
歸并排序
（截圖源自百度百科）
歸并：顧名思義是把資料合并，在這之前需要把他們分開，這是“分”的程序，合并的程序就是“治”的程序，
<畫個草圖>
分：奇數序列我習慣給右邊的序列多分一個數（看網上很多是左邊多分一個數，但我除錯的時候由于邊界問題出bug了就給改了）
治：處理兩個有序列的演算法可參考 ： 力扣第21題“合并兩個有序鏈表”
用到了類似啞元加迭代的思想，迭代放在兩個有序列起點位置的下標，每次比較下標位置元素大小，按比較條件放入新建立的陣列，
下面是代碼部分：
class myMergesort {
public:
vector<int> Mergesort(vector<int>& before) {
if (before.size() == 1)return before; /*遞回出口*/
vector<int>left, right, ans;
/*分*/
for (int i = 0; i < before.size() / 2; ++i) /*左切塊*/
left.push_back(before[i]);
for (int i = before.size() / 2; i < before.size(); ++i)/*右切塊*/
right.push_back(before[i]);
left=Mergesort(left);/*繼續切左邊（遞回）*/
right=Mergesort(right);/*繼續切右邊（遞回）*/
/*治*/
int i=0, j=0;
while(i<left.size()&&j<right.size()) {/*排序插入到ans*/
if (left[i] <= right[j])ans.push_back(left[i++]);
else ans.push_back(right[j++]);
}
if (i == left.size()) /*接上right的后續有序列*/
for (int k = j; k < right.size(); ++k)ans.push_back(right[k]);
if (j == right.size())/*接上left的后續有序列*/
for (int k = i; k < left.size(); ++k)ans.push_back(left[k]);
return ans;
}
};
除錯程序
50個（0~9）亂數：
20000個（0~9）亂數：
快速排序
快排：C/C++可直接使用快速排序的庫函式qsort() / sort()
快排也用到了分治的思想，但它的“分”的程序是依據基準數歸位后所在的位置進行劃分，而基準數是什么？怎么“治”？才是快排的關鍵，
基準數：通俗講就是每次需要歸位的數，每次歸位后，它的左邊都是比它小的數，它的右邊都是比它大的數，（一般取最左邊的數為基準數）
治：（這里參考到的是《啊哈!演算法》中的小插圖）
首先左右哨兵站在序列的左右兩端（下標定位，基準數為6）：
<右邊的哨兵先往左走，找到第一個比6小的數停下>
<左邊的哨兵再往右走，找到第一個比6大的數停下>
<然后把他們交換>
哨兵繼續走，重復上述程序（交換9和4）：
當他們相遇，將相遇處的數字3和基準數6交換：
這就完成了一次“治”的程序，然后將此時左邊和右邊的序列進行遞回，最后回傳完成排序，
主代碼部分：
void myQuicksort::_myQuicksort(int left,int right) {
if (left >= right)return;
int i = left,j=right,base=ans[left],temp;
while (i<j) {
while (ans[j] >= base && j > i)--j; /*1.右哨兵定位*/
while (ans[i] <= base && i < j)++i; /*1.左哨兵定位*/
if (i < j) { /*若左右哨兵相遇，取消定位處的交換*/
/*2.交換左右哨兵定位到的元素*/
temp = ans[j];
ans[j] = ans[i];
ans[i] = temp;
}
}
/*3.交換基準數和哨兵相遇處的元素*/
ans[left] = ans[i];
ans[i] = base;
_myQuicksort(left,i-1);/*左邊的無序序列繼續呼叫快排*/
_myQuicksort(i+1,right);/*右邊的無序序列繼續呼叫快排*/
}
除錯程序：
50個（0~9）亂數：
20000個（0~9）亂數：
對比一下，什么？！快排比歸并排序要快！直接打臉了，為什么在app里的結果不一樣呢…
最后
文章總結了快排和歸并的原理以及用法，等我以后哪天忘了就來看看，
大家不要復制粘貼，要認真學習總結，不懂的給我留言，哈哈哈還押韻上了，小生不才不當的地方請多多指教，
參考：《啊哈!演算法》中的排序一章 還有 百度百科，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/238097.html
標籤：其他