一篇很好的講8大排序的博客

選擇排序 (不穩(wěn)定)

• 選擇排序是給每個位置選擇當(dāng)前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因?yàn)橹皇Ｏ滤粋€最大的元素了。那么，在一趟選擇中，如果當(dāng)前元素比一個元素大，而該小的元素又出現(xiàn)在一個和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩(wěn)定的排序算法。

堆排序 (不穩(wěn)定)

• 堆的結(jié)構(gòu)是節(jié)點(diǎn)i的孩子為 2i 和 2i+1 節(jié)點(diǎn)，大頂堆要求父節(jié)點(diǎn)大于等于其2個子節(jié)點(diǎn)，小頂堆要求父節(jié)點(diǎn)小于等于其2個子節(jié)點(diǎn)。在一個長為n的序列，堆排序的過程,首先要根據(jù)floyd算法建堆，因此要從第n/2開始和其子節(jié)點(diǎn)共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當(dāng)然不會破壞穩(wěn)定性。但當(dāng)為n/2-1, n/2-2,...1這些個父節(jié)點(diǎn)選擇元素時，就會破壞穩(wěn)定性。有可能第n/2個父節(jié)點(diǎn)交換把后面一個元素交換過去了，而第n/2-1個父節(jié)點(diǎn)把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法。
• eg：{5A,6,5B,7,8} --> {8,7,5B,5A,6} ,兩個5的順序顛倒了。

插入排序 (穩(wěn)定)

• 插入排序是在一個已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個元素。當(dāng)然，剛開始這個有序的小序列只有1個元素，就是第一個元素。插入調(diào)用有序序列的search操作，該操作返回的是第一個大于該元素的位置，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。

希爾排序 (不穩(wěn)定)

• 希爾排序是按照不同步長對元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ?#xff0c;希爾排序的時間復(fù)雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。

冒泡排序 (穩(wěn)定)

• 冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。

快速排序 (不穩(wěn)定)

• 快速排序有兩個方向，當(dāng)a[i] <= a[center_index]，左邊的i下標(biāo)一直往右走，其中center_index是中樞元素的數(shù)組下標(biāo)，一般取為數(shù)組第0個元素。
• 當(dāng)a[j] > a[center_index]，右邊的j下標(biāo)一直往左走。如果i和j都走不動了，i <= j,交換a[i] 和 a[j],重復(fù)上面的過程，直到i>j。交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩(wěn)定性打亂.
• 比如序列為?5 3 3 4 3 8 9 10 11，現(xiàn)在中樞元素5和3(第5個元素，下標(biāo)從1開始計(jì))交換就會把元素3的穩(wěn)定性打亂，所以快速排序是一個不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時刻。

歸并排序 (穩(wěn)定)

• 歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認(rèn)為直接有序)或者2個序列(1次比較和交換),然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序。可以發(fā)現(xiàn)，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也沒有人故意交換，這不會破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞？沒有，合并過程中我們可以保證如果兩個當(dāng)前元素相等時，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。所以，歸并排序也是穩(wěn)定的排序算法。

基數(shù)排序 (穩(wěn)定)

• 基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序，最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前。基數(shù)排序基于分別排序，分別收集，所以其是穩(wěn)定的排序算法。

1.快速排序

#include<iostream> #include<vector> using namespace std;void swap(int &p, int &q){int temp;temp = p;p = q;q = temp; }int partition(vector<int>&array, int lo, int hi){swap(array[lo], array[lo + rand() % (hi - lo + 1)]);//產(chǎn)生[lo,hi]之間的一個隨機(jī)數(shù)int pivot = array[lo];while (lo < hi){//swapwhile ((lo < hi) && pivot <= array[hi]){hi--;}//array[lo] = array[hi]; swap(array[lo], array[hi]);while ((lo < hi) && pivot >= array[lo]){lo++;}//array[hi] = array[lo]; swap(array[lo], array[hi]);}//array[lo] = pivot;return lo; } void quicksort(vector<int>&array, int lo, int hi){if (hi - lo < 1)return;int mi = partition(array, lo, hi);quicksort(array, lo, mi-1);quicksort(array, mi + 1, hi);} int partition(vector<int>&array, int lo, int hi){int pivot = array[lo];while (lo < hi){while (lo < hi&&pivot <= array[hi])hi--;swap(array[lo], array[hi]);while (lo < hi&&pivot >= array[lo])lo++;swap(array[lo], array[hi]);}return lo; }/**使用棧的非遞歸快速排序**/ void quicksort2(vector<int> &vec, int low, int high){stack<int> st;if (low<high){int mid = partition(vec, low, high);if (low<mid - 1){st.push(low);st.push(mid - 1);}if (mid + 1<high){st.push(mid + 1);st.push(high);}//其實(shí)就是用棧保存每一個待排序子串的首尾元素下標(biāo)，下一次while循環(huán)時取出這個范圍，對這段子序列進(jìn)行partition操作while (!st.empty()){int q = st.top();st.pop();int p = st.top();st.pop();mid = partition(vec, p, q);if (p<mid - 1){st.push(p);st.push(mid - 1);}if (mid + 1<q){st.push(mid + 1);st.push(q);}}} }

?

?

2.歸并排序

void merge(vector<int>&input, int left, int right, int mid, vector<int>&temp){int i = left;int j = mid+1;int t = 0;while (i<=mid&&j<=right){if (input[i] <= input[j]){temp[t++] = input[i++];}else{temp[t++] = input[j++];}}while (i <= mid){temp[t++] = input[i++];}while (j <= right){temp[t++] = input[j++];}t = 0;while (left <= right){input[left++] = temp[t++];} }void mergesort(vector<int>&input, int left, int right, vector<int>&temp){if (left < right){int mid = (left + right) / 2;mergesort(input, left, mid, temp);mergesort(input, mid + 1, right, temp);merge(input, left, right, mid, temp);} }

?3.堆排序

/* * (最大)堆的向下調(diào)整算法** 注：數(shù)組實(shí)現(xiàn)的堆中，第N個節(jié)點(diǎn)的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。數(shù)組是按層編號的。* 其中，N為數(shù)組下標(biāo)索引值，如數(shù)組中第1個數(shù)對應(yīng)的N為0。** 參數(shù)說明：* a -- 待排序的數(shù)組* start -- 被下調(diào)節(jié)點(diǎn)的起始位置(一般為0，表示從第1個開始)* end -- 截至范圍(一般為數(shù)組中最后一個元素的索引)*/ void maxheap_down(int a[], int start, int end) {int c = start; // 當(dāng)前(current)節(jié)點(diǎn)的位置int l = 2*c + 1; // 左(left)孩子的位置int tmp = a[c]; // 當(dāng)前(current)節(jié)點(diǎn)的大小for (; l <= end; c=l,l=2*l+1){// "l"是左孩子，"l+1"是右孩子if ( l < end && a[l] < a[l+1])l++; // 左右兩孩子中選擇較大者，即m_heap[l+1]if (tmp >= a[l])break; // 調(diào)整結(jié)束else // 交換值 {a[c] = a[l];a[l]= tmp;}} }/** 堆排序(從小到大)** 參數(shù)說明：* a -- 待排序的數(shù)組* n -- 數(shù)組的長度*/ void heap_sort_asc(int a[], int n) {int i;// 從(n/2-1) --> 0逐次遍歷。遍歷之后，得到的數(shù)組實(shí)際上是一個(最大)二叉堆。從下到上，從左到右遍歷父節(jié)點(diǎn)調(diào)整for (i = n / 2 - 1; i >= 0; i--)maxheap_down(a, i, n-1);// 從最后一個元素開始對序列進(jìn)行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個元素for (i = n - 1; i > 0; i--){// 交換a[0]和a[i]。交換后，a[i]是a[0...i]中最大的。swap(a[0], a[i]);// 調(diào)整a[0...i-1]，使得a[0...i-1]仍然是一個最大堆。// 即，保證a[i-1]是a[0...i-1]中的最大值。//下面一條語句start=0是因?yàn)榈谝粋€父節(jié)點(diǎn)改變了值，要重新調(diào)整為最大堆maxheap_down(a, 0, i-1);} }

?

/ brief /void makeheap_down(vector<int>&array, int start, int end){int c = start;//c是當(dāng)前要下濾的節(jié)點(diǎn)for (int i = 2 * start + 1; i <= end; c = i, i = 2 * i + 1){if (i<end&&array[i] < array[i + 1])i++;//i<end不能漏，不然i=end;i+1超出范圍if (array[c] >= array[i])break; else{ swap(array[c], array[i]); }} } /*堆排序*/ void maxheap_sort(vector<int>&a, int n){ //第一個for循環(huán)構(gòu)建最大堆，n為向量長度 for (int i = n / 2 - 1; i >= 0; i--) makeheap_down(a, i, n-1); //第二個for循環(huán)用來排序 for (int i = n-1; i>0; i--){ swap(a[0], a[i]); makeheap_down(a, 0, i-1);//再次調(diào)整為最大堆 ，i不能=0 } }

?

4.選擇排序

void select_sort(vector<int>&a){for (int i = 0; i < a.size()-1; i++){int min_index = i;for (int j = i+1; j < a.size(); j++){if (a[j] < a[min_index]){min_index = j;}}if (min_index!=i)swap(a[i], a[min_index]);} }

?5.冒泡排序

void bubble_sort(vector<int>&a){for (int i = 0; i < a.size()-1; i++){for (int j = 0; j < a.size()-1-i; j++){if (a[j] > a[j + 1]){//swap(a[j], a[j + 1]);int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}} }

6.插入排序

void insert_sort(vector<int>&a){for (int i = 1; i < a.size(); i++){int j = i;while (j>0 && a[j] < a[j - 1]){swap(a[j], a[j - 1]);j--;}} }

?7.桶排序和基數(shù)排序

void bucketSort(vector<int>&input,int max){vector<int>bucket(max, 0);//max是要排序數(shù)組中的最大值+1for (int i = 0; i < input.size(); i++){bucket[input[i]]++;}for (int i = 0,j=0; i < max; i++){while ((bucket[i]--)> 0){//可以排序重復(fù)數(shù)字input[j++] = i;}} }

基數(shù)排序補(bǔ)充：基數(shù)排序(Radix Sort)是桶排序的擴(kuò)展，它的基本思想是：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。
具體做法是：將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。

/** 獲取數(shù)組a中最大值** 參數(shù)說明：* a -- 數(shù)組* n -- 數(shù)組長度*/ int get_max(int a[], int n) {int i, max;max = a[0];for (i = 1; i < n; i++)if (a[i] > max)max = a[i];return max; }/** 對數(shù)組按照"某個位數(shù)"進(jìn)行排序(桶排序)** 參數(shù)說明：* a -- 數(shù)組* n -- 數(shù)組長度* exp -- 指數(shù)。對數(shù)組a按照該指數(shù)進(jìn)行排序。** 例如，對于數(shù)組a={50, 3, 542, 745, 2014, 154, 63, 616}；* (01) 當(dāng)exp=1表示按照"個位"對數(shù)組a進(jìn)行排序* (02) 當(dāng)exp=10表示按照"十位"對數(shù)組a進(jìn)行排序* (03) 當(dāng)exp=100表示按照"百位"對數(shù)組a進(jìn)行排序* ...*/ void count_sort(int a[], int n, int exp) {int output[n]; // 存儲"被排序數(shù)據(jù)"的臨時數(shù)組int i, buckets[10] = {0};// 將數(shù)據(jù)出現(xiàn)的次數(shù)存儲在buckets[]中for (i = 0; i < n; i++)buckets[ (a[i]/exp)%10 ]++;// 更改buckets[i]。目的是讓更改后的buckets[i]的值，是該數(shù)據(jù)在output[]中的位置。for (i = 1; i < 10; i++)buckets[i] += buckets[i - 1];// 將數(shù)據(jù)存儲到臨時數(shù)組output[]中for (i = n - 1; i >= 0; i--){output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];buckets[ (a[i]/exp)%10 ]--;}// 將排序好的數(shù)據(jù)賦值給a[]for (i = 0; i < n; i++)a[i] = output[i]; }/** 基數(shù)排序** 參數(shù)說明：* a -- 數(shù)組* n -- 數(shù)組長度*/ void radix_sort(int a[], int n) {int exp; // 指數(shù)。當(dāng)對數(shù)組按各位進(jìn)行排序時，exp=1；按十位進(jìn)行排序時，exp=10；...int max = get_max(a, n); // 數(shù)組a中的最大值// 從個位開始，對數(shù)組a按"指數(shù)"進(jìn)行排序for (exp = 1; max/exp > 0; exp *= 10)count_sort(a, n, exp); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/inception6-lxc/p/9021389.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的各种排序实现以及稳定性分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。