寫在前面:

1.本文中默認排序為升序，降序的原理類似。

2.如果程序直接復制到vs出現無法識別標記的問題，解決方法在這：vs無法識別標記的解決方法

3.本文的算法都是自己用stl實現的，疏漏之處還請指正。

4.在文末對個算法的穩定性進行了詳細的講解！

目錄

算法概述

1.算法分類

2.算法復雜度

3.相關概念

一、 冒泡排序

1.原理概述

2.算法實現

二、選擇排序

1.原理概述

2.算法實現

三、快速排序

1.選取基準數

2.將該序列中小于基準數的數排在其左邊，大于基準數的數排在其右邊

3.算法實現

四、插入排序

1.原理概述

2.示例

3.算法實現

五、希爾排序

1.原理概述

2.排序步驟

3.算法實現

六、歸并排序

1.原理概述

2.示例

3.算法實現

七、堆排序

1.原理概述

2.堆：

3.實現原理

3.1 初始化數組，創建大頂堆。

3.2 交換根節點和倒數第一個數據，現在倒數第一個數據就是最大的。

3.3 重新建立大頂堆。

3.4 重復3.2、3.3的步驟，直到只剩根節點 array[0]，即 i=1。

4.排序實例

5.算法實現

八、計數排序

1.原理概述

2.排序步驟

3.算法實現

九、基數排序(也可以叫低位到高位的基數排序)

1.原理概述

2.算法實現

十、桶排序

1.原理概述

2.排序實例

3.算法實現

十一、經典算法穩定性分析

一、不穩定排序算法有哪些

二、常見排序算法穩定性分析

1、堆排序穩定性分析

2、希爾排序

3、快速排序

4、選擇排序

5、冒泡排序

6、插入排序

7、歸并排序

8、基數排序

---

?

算法概述

1.算法分類

十種常見排序算法分為2大類：

非線性時間比較類：通過比較來決定元素間的相對順序，由于其時間復雜度不能突破O(nlogn)，因此稱為非線性時間比較類排序。

線性時間非比較類：不通過比較來決定元素間的相對順序，它可以突破基于比較排序的時間下界，以線性時間運行，因此稱為線性時間非比較類排序。

2.算法復雜度

3.相關概念

穩定：如果a原本在b前面，而a=b，排序后a仍在b前面

不穩定：如果a原本在b前面，而a=b，排序后a可能會出現在b后面。

時間復雜度：對排序數據的總的操作次數。反映當n變化時，操作次數呈現什么規律。

空間復雜度：是指算法在計算機內執行時所需存儲空間的度量，它也是數據規模n的函數。

一、 冒泡排序

1.原理概述

冒泡排序是遍歷整個序列，并相鄰兩元素兩兩比較，如果反序就交換位置，最終就將最大的數放到序列末尾。遍歷第二次就將倒數第二大的數放到了倒數第二的位置，重復該操作，直到遍歷n-1次后，整個序列完成排序。

2.算法實現

#include<vector> #include<string> #include?<iostream> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{ public:void?BubbleSort(vector<int>&?nums)?{int?n?=?nums.size();if?(nums.empty()?||?n?<=?1)?return;for?(int?i?=?n;?i?>?0;?i--)?{for?(int?j?=?1;?j?<?i;?j++)?{if?(nums[j]?<?nums[j?-?1])?swap(nums[j],?nums[j?-?1]);}}return;} }; int?main() {vector<int>?aa{4,3,5,1,5,8};Solution?sa;sa.BubbleSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

二、選擇排序

1.原理概述

遍歷整個序列，找到最小元素的位置，然后將其放到序列最開始作為已排序序列。然后再從剩余的序列中找到最小的元素放在已排序序列后面。依次類推直到所有元素排列完畢。

選擇排序與冒泡排序的區別是：選擇排序遍歷完整個序列才交換一次；而冒泡排序是兩兩比較視情況交換，所以每遍歷一個元素都可能交換。

2.算法實現

#include<vector> #include?<iostream> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{ public:void?SelectionSort(vector<int>&?nums)?{int?n?=?nums.size();if?(nums.empty()?||?n?<=?1)?return;for?(int?i?=?0;?i?<?n;?i++)?{int?minpos?=?i;for?(int?j?=?i?+?1;?j?<?n;?j++)?{if?(nums[j]?<?nums[minpos])?minpos?=?j;}swap(nums[minpos],?nums[i]);}return;} }; int?main() {vector<int>?aa{4,3,5,1,5,8,7?,?25,?6};Solution?sa;sa.BubbleSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

三、快速排序

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-onquerMethod)。它的平均時間復雜度為O(nlogn)，最壞時間復雜度為O(n^2)。

快速排序完成的事情就是：選取參照數后，需要將參照數挪到序列中的第k位，并以位置k為分界。實現左邊的數小于參照數，右邊的數大于參照數。然后遞歸對左右兩個區間做同樣的事，就能完成排序。

假設現在要對“6 ?1 ?2 7 ?9 ?3 ?4 ?5 10 ?8”這個10個數進行排序。

1.選取基準數

隨機選取序列中的一個數作為參照數，一般選第一個，如果選的不是第一個，就將其與第一個交換。比如這里選6作為基準數。

2.將該序列中小于基準數的數排在其左邊，大于基準數的數排在其右邊

3? 1? 2 5? 4? 6? 9 7? 10? 8

具體步驟：

首先要選取哨兵(基準數base)，如果是隨機選取的，就將其換到第一個位置。定義left指針指向序列首位置，定義right指針指向末尾位置。

1）從數組的right位置向前找，一直找到比（base）小的數，如果找到，將此數賦給left位置，此時right指針指向找到的那個數。

2）從數組的left位置向后找，一直找到比（base）大的數，如果找到，將此數賦給right的位置，此時left指針指向找到的那個數的位置。

3）重復步驟1、2直到left==right。

4）將基準數放在相等的位置上。至此完成一次快排！

5）以剛剛找到的基準數的位置為分界點，對其前后兩個新序列重復步驟1-4。直到排序完成。

因為來回覆蓋，不會丟掉數。(首先將基數放在第一個位置上。從右方開始，小的往前面覆蓋，也就是放在基數位置上。從左方開始大的往后面覆蓋，也就是放在剛剛最小的那個數上面)

3.算法實現

#include<vector> #include<string> #include?<iostream> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{ public:void?QuickSort(vector<int>&?points)?{if?(points.empty())?return?;int?len?=?points.size();int?left?=?0,?right?=?len?-?1;//序列的左右邊界Sort(points,?left,?right);}void?Sort(vector<int>&?points,?int?left,?int?right)?{if?(points.empty())?return;if?(left?>=?right)?return;//防止有序隊列導致快速排序效率降低?int?len?=?right?-?left;int?flag?=?points[left],?i?=?left,?j?=?right;while(i?<?j)?{while(points[j]?>=?flag?&&?i?<?j)?--j;//一直向前遍歷?直到位置j上的數小于哨兵if?(i?<?j)?points[i]?=?points[j];//將找到的小的那個數覆蓋到前面while?(points[i]?<=?flag?&&?i?<?j)?++i;//一直向后遍歷?直到位置i上的數大于哨兵if?(i?<?j)?points[j]?=?points[i];//將找到的大的那個數?覆蓋到后面}points[i]?=?flag;//因為此時位置i左邊的數都小于flag?右邊的數都大于flag?位置i上的數是個重復的數Sort(points,?left,?i?-?1);//遞歸左邊序列Sort(points,?i?+?1,?right);//遞歸右邊序列} }; int?main() {vector<int>?aa{4,3,5,1,5,8,7?,?25,?6};Solution?sa;sa.QuickSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

四、插入排序

1.原理概述

直接插入排序，也簡稱為插入排序?；舅枷胧?#xff1a;

假設左邊i個元素已經排好序，從i開始，從左向右開始遍歷，將遍歷到的元素放在已排序列中第一個小于該元素的元素后面。

直接插入排序對于最壞的情況(嚴格遞減的序列)，需要比較和移位的次數為n(n-1)/2;對于最好的情況(嚴格遞增的序列)，需要比較的次數為n-1，需要移位的次數為0。

直接插入排序法對于基本有序的序列會有更好的性能，這一特性給了它進一步優化的可能性(希爾排序)。

2.示例

使用直接插入排序法對序列89 45 54 29 90 34 68進行升序排序。

89?45 54 29 90 34 68

45 89?54 29 90 34 68

45 54 89?29 90 34 68

29 45 54 89?90 34 68

29 45 54 89 90?34 68

29 34 45 54 89 90?68

29 34 45 54 68 89 90

3.算法實現

#include<vector> #include<string> #include?<iostream> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{ public:void?InsertSort(vector<int>&?nums)?{int?n?=?nums.size();if?(n?<=?1)?return;for?(int?i?=?1;?i?<?n;?i++)?{for?(int?j?=?i;?j?>?0;?j--)?{if?(nums[j]?<?nums[j?-?1])?swap(nums[j],?nums[j?-?1]);else?break;}}return;} }; int?main() {vector<int>?aa{4,3,5,1,5,8,7?,?25,?6};Solution?sa;sa.InsertSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

五、希爾排序

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，是在簡單插入排序基礎上改進的一個高效版本，也稱為縮小增量排序。該算法是第一批沖破O(n2)的算法之一。利用了插入排序的最佳時間代價特性，它試圖將待排序序列變成基本有序的，然后再用插入排序來完成排序工作。

(這里再提一下插入排序，直接插入排序是從前往后一次遍歷每一個并將其放在前面第一個小于它的元素后面)

1.原理概述

由于直接插入排序需要一步一步的對元素進行比較、移動、插入。希爾排序在此基礎上采用跳躍分組的策略，通過增量(跳躍的量化)將序列劃分為若干組，然后分組進行插入排序，接著縮小增量，繼續按組進行插入排序操作，直至增量為1。采用這個策略的希爾排序使整個序列在初始階段從宏觀上看就基本有序，小的基本在前面，大的基本在后面。然后縮小增量至增量為1時，多數情況下只需要微調就可以了，不涉及到大量的數據移動。

2.排序步驟

首先選擇增量gap=lengh/2，縮小增量至gap=gap/2。增量的可以用增量序列來表示，如{n/2,(n/2)/2……1}。

這個增量序列也稱為希爾增量，其實這個增量序列不是最優的。

算法實現關鍵是在序列中每隔gap取一個構成一組，然后對每一組進行插入排序操作。

3.算法實現

#include<vector> #include<string> #include?<iostream> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{ public:const?int?INCRGAP?=?3;//增量初始化void?ShellSort(vector<int>?&nums){int?len?=?nums.size();unsigned?gap?=?len?/?INCRGAP?+?1;?//?步長初始化,注意如果當len<INCRGAP時，gap為0，所以為了保證進入循環，gap至少為1！！！while?(gap)?//?while?gap>=1{for?(unsigned?i?=?gap;?i?<?len;?++i)?//?分組，在每個子序列中進行插入排序{unsigned?j?=?i;while?(j?>=?gap?&&?nums[j]?<?nums[j?-?gap])//直接插入排序{swap(nums[j],?nums[j?-?gap]);j?-=?gap;}}gap?=?gap?/?INCRGAP;}} }; int?main() {vector<int>?aa{?2,?1,?4,?3,?11,?6,?5,?7,?8,?10,?15?};int?K?=?8766;Solution?sa;sa.ShellSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

六、歸并排序

1.原理概述

歸并排序是利用歸并的思想實現的排序方法。該方法采用分治策略(分治法將問題分解為一些小問題，然后遞歸求解；而治階段將分段得到的答案合并在一起)。

2.示例

這種結構類似于完全二叉樹，歸并排序需要使用遞歸或者迭代的方法實現。

分階段就是遞歸拆分子序列，遞歸深度為log2n。

治階段需要將兩個已經有序的子序列相互比較再合并。

3.算法實現

#include<vector> #include<string> #include?<iostream> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{public:void?MergeSort(vector<int>&?nums)?{int?n?=?nums.size();if?(n?<=?1)?return;int?left?=?0,?right?=?n?-?1;Sort(nums,?left,?right);//開始歸并排序}void?Sort(vector<int>?&nums,?int?left,?int?right)?{if?(left?>=?right)?return;int?mid?=?(left?+?right)?/?2;//將序列分為2部分Sort(nums,?left,?mid);//處理左半部分序列Sort(nums,?mid?+?1,?right);//處理右半部分序列/***下面是對序列進行排序合并處理，可以單獨用一個函數完成***/vector<int>?temp;//排序的臨時容器?int?i?=?left,?j?=?mid?+?1;while?(i?<=?mid?&&?j?<=?right)?{//對兩個序列進行排序并合并if?(nums[i]?<=?nums[j])?temp.push_back(move(nums[i++]));elsetemp.push_back(move(nums[j++]));?}while?(i?<=?mid)?temp.push_back(move(nums[i++]));while?(j?<=?right)?temp.push_back(move(nums[j++]));for?(int?k?=?0;?k?<?right?-?left?+?1;?k++){nums[left?+?k]?=?temp[k];}} }; int?main() {vector<int>?aa{4,10,5,1,5,8,7?,?9,?6};Solution?sa;sa.MergeSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

七、堆排序

1.原理概述

堆排序是利用堆的性質來進行排序的。

2.堆：

堆實際上是一顆完全二叉樹，滿足兩個性質：

1.堆的父節點都大(小)于其子節點；2.堆的每個子樹也是一個堆。

堆分為兩類：

最大堆：堆的每個父節點都大于其孩子節點；

最小堆：堆的每個父節點都小于其孩子節點。

堆的存儲：第i個節點的父節點下標為(i-1)/2。對應的其左右孩子節點下標為2*i+1和2*i+2.

3.實現原理

要實現從小到大的排序，就要建立大頂堆，即父節點比子節點都要大。

3.1 初始化數組，創建大頂堆。

大頂堆的創建從下往上比較，不能直接用無序數組從根節點比較，否則有的不符合大頂堆的定義。

3.2 交換根節點和倒數第一個數據，現在倒數第一個數據就是最大的。

3.3 重新建立大頂堆。

?因為只有 array[0] 改變，其它都符合大頂堆的定義，所以可以根節點 array[0] 重新建立。

3.4 重復3.2、3.3的步驟，直到只剩根節點 array[0]，即 i=1。

4.排序實例

原始數據：array[]={49,38,65,97,76,13,27,49,10}

要升序排序，就構建最大堆。

原始堆排序

創建大頂堆

從倒數第二行往上比較父節點和子節點，把大的往上移動，小的向下移，直到符合大頂堆定義。

交換根節點和最后一個節點

重新創建大頂堆

接下來就一直循環即可得到堆排序結果

5.算法實現

#include?<iostream> #include<vector> #include<string> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{ public://堆排序/*大頂堆sort之后，數組為從小到大排序*///====排序=====void?HeapSort(vector<int>?&nums){int?len?=?nums.size();MakeHeap(nums);for?(int?i?=?len?-?1;?i?>=?0;?--i){swap(nums[i],?nums[0]);AdjustHeap(nums,?0,?i);}}//====調整=====void?AdjustHeap(vector<int>?&nums,?int?node,?int?len)??//----node為需要調整的結點編號，從0開始編號;len為堆長度{int?index?=?node;int?child?=?2?*?index?+?1;?//左孩子，第一個節點編號為0while?(child?<?len){//右子樹if?(child?+?1?<?len?&&?nums[child]?<?nums[child?+?1]){child++;}if?(nums[index]?>=?nums[child])?break;swap(nums[index],?nums[child]);index?=?child;child?=?2?*?index?+?1;}}//====建堆=====void?MakeHeap(vector<int>?&nums){int?len?=?nums.size();for?(int?i?=?len?/?2;?i?>=?0;?--i){AdjustHeap(nums,?i,?len);}} }; int?main() {vector<int>?aa{?8,5,0,3,7,1,2?};//int?K;vector<int>?sa;Solution?ss;ss.HeapSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

八、計數排序

1.原理概述

計數排序不是基于比較的排序算法，其核心是將輸入的數據值轉化為鍵存儲在額外的空間。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

2.排序步驟

找出待排序的序列中的最大值和最小值；

統計序列中每個值為i的元素出現的次數，存入序列C的第i項；

對所有的計數累加(對C按項求和)；

反向填充目標序列，將每個元素i放在新序列的第C(i)項，每放一個元素將C(i)減一。

計數排序是一種不需要比較的排序，比任何比較的排序都要快。

適用于數組中的值不是特別大的情況，因為需要用空間換時間，所以當數組中的值特別大的時候，空間開銷會超級大。從代碼中可以明顯看出來。

此外，計數排序只能用于正數排序（個人認為負數排序也是可以的）。

3.算法實現

#include?<iostream> #include<vector> #include<string> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{ public:void?CounterSort(vector<int>?&nums)?{if?(nums.empty())?return;int?len?=?nums.size();int?max_num?=?*(max_element(nums.begin(),?nums.end()));vector<int>?tmp(max_num+1,?0);//根據最大數構建一個數組for?(int?i?=?0;?i?<?len;?i++)?{tmp[nums[i]]++;}vector<int>().swap(nums);for?(int?i?=?0;?i?<?tmp.size();?i++)?{while?(tmp[i]?!=?0)?{nums.push_back(i);tmp[i]--;}}} }; int?main() {vector<int>?aa{45,?1,?9,?18,5,0,23,47,15,2?};//int?K;vector<int>?sa;Solution?ss;ss.CounterSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

九、基數排序(也可以叫低位到高位的基數排序)

1.原理概述

基數排序與前面大部分排序方法都不相同，它不需要比較關鍵字的大小。

它根據關鍵字中各位的值，通過對排序的N個元素進行若干次“分配”與“收集”來實現排序。

其原理就是從個位開始排序，在低位數滿足排序的情況下，低位對整體排序的作用已經完成，只需要高位也滿足排序規則即可。所以從個位開始逐位放入桶中再按桶號取出即可。

LSD(低位到高位的排序)

下面通過一個具體的實例來展示基數排序。設置初始序列：

?{50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

每個位置的數字其各位上的基數都是0~9來表示，所以可以將0~9視為10個桶。

先根據序列的個位數的數字來進行分類，將其分到指定的桶中。例如：

分類后，我們再從各個桶中，將這些數按照從編號0到編號9的順序依次將所有數取出來。

這時，得到的序列就是個位數上呈遞增趨勢的序列。

原始序列：?{50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

按照個位數排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

再對十位進行相同的操作，然后依次將數取出，

得到按照十位數排序：{0， 2，100，11，123，30，543，49，50，187}。

再對百位進行相同的操作，然后將數取出。

得到按照百位排序：{0， 2，11，30，49，50，100，123，187，543}

最終排序完成。

2.算法實現

LSD(低位到高位的排序)

#include?<iostream> #include<vector> #include<string> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Solution?{ public:void?RadixSort_LSD(vector<int>?&nums)?{if?(nums.empty())?return;int?len?=?nums.size();//得到最高位到哪int?max_num?=?*(max_element(nums.begin(),?nums.end()));int?min_num?=?*(min_element(nums.begin(),?nums.end()));//防止有負數int?high1?=?0,?high2?=?0,?high?=?0;while?(max_num?!=?0)?{high1++;max_num?/=?10;}while?(min_num?!=?0)?{high2++;min_num?/=?10;}high?=?max(high1,?high2);vector<vector<int>>?Bucket(10,?vector<int>());vector<int>tmp;tmp?=?nums;for?(int?i?=?1;?i?<=?high;?i++)?{for?(int?j?=?0;?j?<?tmp.size();?j++)?{Bucket[abs(tmp[j]?%?10)].push_back(nums[j]);}//重新組成臨時排序數組vector<int>().swap(nums);vector<int>().swap(tmp);for?(int?m?=?0;?m?<?10;?m++)?{for?(int?n?=?0;?n?<?Bucket[m].size();?n++)?{nums.push_back(Bucket[m][n]);//每處理一次?去掉最低位tmp.push_back(Bucket[m][n]/10);}vector<int>().swap(Bucket[m]);}}//再處理數組中的負數deque<int>?rev;for?(int?i?=?0;?i?<?len;?i++)?{if?(nums[i]?<?0)?rev.push_front(nums[i]);else?rev.push_back(nums[i]);}vector<int>().swap(nums);for?(auto?x?:?rev)?{nums.push_back(x);}} }; int?main() {vector<int>?aa{45,?-1,?-995,?18,5,0,-23,47,15,2?};//int?K;vector<int>?sa;Solution?ss;ss.RadixSort_LSD(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

十、桶排序

1.原理概述

桶排序是基數排序和計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排）。

2.排序實例

待排序序列

170, 45, 75, 90, 2, 24, 802, 66

我們看到，這里面的最大的數是3位數。所以說我們開始從百位對這些數進行分組

0: 045, 075, 090,002, 024, 066

1: 170

2-7: 空

8: 802

9: 空

從這里開始就和LSD基數排序有差別了。在LSD基數排序中，每次分好組以后開始對桶中的數據進行收集。然后根據下一位，對收集后的序列進行分組。在這里不會對桶中的數據進行收集。我們要做的是檢測每個桶中的數據。當桶中的元素個數多于1個的時候，要對這個桶遞歸進行下一位的分組。

在這個例子中，我們要對0桶中的所有元素根據十位上的數字進行分組

0: 002

1: 空

2: 024

3: 空

4: 045

5: 空

6: 066

7: 075

8: 空

9: 090

按照上面所說，我們應該再遞歸的對每個桶中的元素根據個位上的數進行分組。但是我們發現，現在在每個桶中的元素的個數都是小于等于1的。因此，到這一步我們就開始回退了。也就是說我們開始收集桶中的數據。收集完成以后，回退到上一層。此時按照百位進行分組的桶變成了如下的形式

0: 002, 024, 045,066, 075, 090

1: 170

2-7: 空

8: 802

9: 空

然后我們在對這個桶中的數據進行收集。收集起來以后序列如下

2, 24, 45, 66, 75, 90, 170, 802

整個桶排序就是按照上面的過程進行的。

其實怎么分桶也是由映射函數決定的，下面程序就用了分段的方法。

3.算法實現

#include?<iostream> #include<vector> #include<string> #include?<unordered_map> #include?<unordered_set> #include?<queue> #include?<algorithm>//算法頭文件 using?namespace?std; class?Insert?{ public:void?InsertSort(vector<int>&?nums)?{int?n?=?nums.size();if?(n?<=?1)?return;for?(int?i?=?1;?i?<?n;?i++)?{for?(int?j?=?i;?j?>?0;?j--)?{if?(nums[j]?<?nums[j?-?1])?swap(nums[j],?nums[j?-?1]);else?break;}}return;} }; class?Solution?{ public:void?bucketSort(vector<int>?&nums)?{if?(nums.size()?==0)?{return?;}int?minValue?=?*(min_element(nums.begin(),?nums.end()));int?maxValue?=?*(max_element(nums.begin(),?nums.end()));//?桶的初始化int?DEFAULT_BUCKET_SIZE?=?5;????????????//?設置桶的默認數量為5int?bucketCount?=?((maxValue?-?minValue)?/?DEFAULT_BUCKET_SIZE)?+?1;vector<vector<int>>?buckets(bucketCount,vector<int>());//?利用映射函數將數據分配到各個桶中for?(int?i?=?0;?i?<?nums.size();?i++)?{buckets[((nums[i]?-?minValue)?/?DEFAULT_BUCKET_SIZE)].push_back(nums[i]);//其實這里已經分段存入桶中了}Insert?ins;vector<int>().swap(nums);for?(int?i?=?0;?i?<?buckets.size();?i++)?{ins.InsertSort(buckets[i]);??????????????????????//?對每個桶進行排序，這里使用了插入排序for?(int?j?=?0;?j?<?buckets[i].size();?j++)?{nums.push_back(buckets[i][j]);}}} };int?main() {vector<int>?aa{45,?1,?9,?18,5,0,23,47,15,2?};//int?K;vector<int>?sa;Solution?ss;ss.bucketSort(aa);for?(int?i?=?0;?i?<?aa.size();?i++)cout?<<?aa[i]?<<?endl;system("pause");return?0; }

十一、經典算法穩定性分析

參考鏈接：https://www.cnblogs.com/Leophen/p/11397731.html

一、不穩定排序算法有哪些

1、堆排序
2、希爾排序
3、快速排序
4、選擇排序
口訣：一堆（堆）希爾（希爾）快（快速）選（選擇）

二、常見排序算法穩定性分析

1、堆排序穩定性分析

我們知道堆的結構是節點i的孩子為 2*i 和 2*i+1 節點，大頂堆要求父節點大于等于其 2個子節點，小頂堆要求父節點小于等于其 2 個子節點。
在一個長為 n 的序列，堆排序的過程是從第 n/2 開始和其子節點共 3 個值選擇最大（大頂堆）或者最小（小頂堆），這 3 個元素之間的選擇當然不會破壞穩定性。
但當為 n/2-1, n/2-2, ...1 這些個父節點選擇元素時，就會破壞穩定性。
有可能第 n/2 個父節點交換把后面一個元素交換過去了，而第 n/2-1 個父節點把后面一個相同的元素沒有交換，那么這 2 個相同的元素之間的穩定性就被破壞了。
所以，堆排序不是穩定的排序算法。

2、希爾排序

希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；
當元素基本有序時，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比 O(N^2) 好一些。
由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性
就會被打亂。
所以 shell 排序是不穩定的排序算法。

3、快速排序

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

4、選擇排序

選擇排序即是給每個位置選擇待排序元素中當前最小的元素。比如給第一個位置選擇最小的，在剩余元素里面給第二個位置選擇次小的，依次類推，直到第 n-1 個元素，第 n 個元素不用選擇了，因為只剩下它一個最大的元素了。
那么，在一趟選擇時，如果當前鎖定元素比后面一個元素大，而后面較小的那個元素又出現在一個與當前鎖定元素相等的元素后面，那么交換后位置順序顯然改變了。
舉個例子：序列5 8 5 2 9， 我們知道第一趟選擇第 1 個元素 5 會與 2 進行交換，那么原序列中兩個5的相對先后順序也就被破壞了。
所以選擇排序不是一個穩定的排序算法。

5、冒泡排序

冒泡排序就是把小的元素往前調（或者把大的元素往后調）。注意是相鄰的兩個元素進行比較，而且是否需要交換也發生在這兩個元素之間。
所以，如果兩個元素相等，我想你是不會再無聊地把它們倆再交換一下。
如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個元素相鄰起來，最終也不會交換它倆的位置，所以相同元素經過排序后順序并沒有改變。
所以冒泡排序是一種穩定排序算法。

6、插入排序

插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有 1 個元素，也就是第一個元素（默認它有序）。
比較是從有序序列的末尾開始，也就是把待插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其后面。
否則一直往前找直到找到它該插入的位置。如果遇見一個與插入元素相等的，那么把待插入的元素放在相等元素的后面。
所以，相等元素的前后順序沒有改變，從原無序序列出去的順序仍是排好序后的順序。
所以插入排序是穩定的。

7、歸并排序

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

8、基數排序

基數排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。
有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序，最后的次序結果就是高優先級高的在前，高優先級相同的情況下低優先級高的在前。
基數排序基于分別排序，分別收集。
所以其是穩定的排序算法。

總結

以上是生活随笔為你收集整理的C++ 十大经典排序算法原理及模板之STL方法实现以及稳定性分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。