- 排序穩(wěn)定性
首先磺芭，排序算法的穩(wěn)定性大家應(yīng)該都知道，通俗地講就是能保證排序前2個(gè)相等的數(shù)其在序列的前后位置順序和排序后它們兩個(gè)的前后位置順序相同肘迎。在簡單形式化一下颓帝，如果Ai = Aj，Ai原來在位置前谷丸，排序后Ai還是要在Aj位置前堡掏。
其次，說一下穩(wěn)定性的好處刨疼。排序算法如果是穩(wěn)定的布疼，那么從一個(gè)鍵上排序摊趾，然后再從另一個(gè)鍵上排序，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用游两±悖基數(shù)排序就是這樣，先按低位排序贱案，逐次按高位排序肛炮，低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的。另外宝踪，如果排序算法穩(wěn)定侨糟，對基于比較的排序算法而言，元素交換的次數(shù)可能會(huì)少一些（個(gè)人感覺瘩燥，沒有證實(shí)）秕重。
回到主題，現(xiàn)在分析一下常見的排序算法的穩(wěn)定性厉膀，每個(gè)都給出簡單的理由溶耘。
(1)冒泡排序
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較服鹅，交換也發(fā)生在這兩個(gè)元素之間凳兵。所以，如果兩個(gè)元素相等企软，我想你是不會(huì)再無聊地把他們倆交換一下的庐扫；如果兩個(gè)相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個(gè)相鄰起來仗哨，這時(shí)候也不會(huì)交換形庭，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法厌漂。
(2)選擇排序
選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的碘勉，比如給第一個(gè)位置選擇最小的，在剩余元素里面給第二個(gè)元素選擇第二小的桩卵，依次類推，直到第n - 1個(gè)元素倍宾，第n個(gè)元素不用選擇了雏节，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了。那么高职，在一趟選擇钩乍，如果當(dāng)前元素比一個(gè)元素小，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面怔锌，那么交換后穩(wěn)定性就被破壞了寥粹。比較拗口变过，舉個(gè)例子，序列5 8 5 2 9涝涤，我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換媚狰，那么原序列中2個(gè)5的相對前后順序就被破壞了，所以選擇排序不是一個(gè)穩(wěn)定的排序算法阔拳。
(3)插入排序
插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上崭孤，一次插入一個(gè)元素。當(dāng)然糊肠，剛開始這個(gè)有序的小序列只有1個(gè)元素辨宠，就是第一個(gè)元素。比較是從有序序列的末尾開始货裹，也就是想要插入的元素和已經(jīng)有序的最大者開始比起嗤形，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置弧圆。如果碰見一個(gè)和插入元素相等的赋兵，那么插入元素把想插入的元素放在相等元素的后面。所以墓阀，相等元素的前后順序沒有改變毡惜，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的斯撮。
(4)快速排序
快速排序有兩個(gè)方向经伙，左邊的i下標(biāo)一直往右走，當(dāng)a[i] <= a[center_index]勿锅，其中center_index是中樞元素的數(shù)組下標(biāo)帕膜，一般取為數(shù)組第0個(gè)元素。而右邊的j下標(biāo)一直往左走溢十，當(dāng)a[j] > a[center_index]垮刹。如果i和j都走不動(dòng)了，i <= j张弛，交換a[i]和a[j],重復(fù)上面的過程荒典，直到i > j。 交換a[j]和a[center_index]吞鸭，完成一趟快速排序寺董。在中樞元素和a[j]交換的時(shí)候，很有可能把前面的元素的穩(wěn)定性打亂刻剥，比如序列為5 3 3 4 3 8 9 10 11遮咖，現(xiàn)在中樞元素5和3（第5個(gè)元素，下標(biāo)從1開始計(jì)）交換就會(huì)把元素3的穩(wěn)定性打亂造虏，所以快速排序是一個(gè)不穩(wěn)定的排序算法御吞，不穩(wěn)定發(fā)生在中樞元素和a[j] 交換的時(shí)刻麦箍。
(5)歸并排序
歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個(gè)元素（認(rèn)為直接有序）或者2個(gè)序列（1次比較和交換）陶珠，然后把各個(gè)有序的段序列合并成一個(gè)有序的長序列挟裂，不斷合并直到原序列全部排好序”陈剩可以發(fā)現(xiàn)话瞧，在1個(gè)或2個(gè)元素時(shí)，1個(gè)元素不會(huì)交換寝姿，2個(gè)元素如果大小相等也沒有人故意交換交排，這不會(huì)破壞穩(wěn)定性。那么饵筑，在短的有序序列合并的過程中埃篓，穩(wěn)定是是否受到破壞？沒有根资，合并過程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí)架专，我們把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性玄帕。所以部脚，歸并排序也是穩(wěn)定的排序算法。
(6)基數(shù)排序
基數(shù)排序是按照低位先排序裤纹，然后收集委刘；再按照高位排序，然后再收集鹰椒；依次類推锡移，直到最高位。有時(shí)候有些屬性是有優(yōu)先級順序的漆际，先按低優(yōu)先級排序淆珊，再按高優(yōu)先級排序，最后的次序就是高優(yōu)先級高的在前奸汇，高優(yōu)先級相同的低優(yōu)先級高的在前施符。基數(shù)排序基于分別排序擂找，分別收集戳吝，所以其是穩(wěn)定的排序算法。
(7)希爾排序(shell)
希爾排序是按照不同步長對元素進(jìn)行插入排序婴洼，當(dāng)剛開始元素很無序的時(shí)候，步長最大撼嗓，所以插入排序的元素個(gè)數(shù)很少柬采，速度很快欢唾；當(dāng)元素基本有序了，步長很小粉捻， 插入排序?qū)τ谟行虻男蛄行屎芨呓盖病Ｋ裕柵判虻臅r(shí)間復(fù)雜度會(huì)比O(n^2)好一些肩刃。由于多次插入排序祟霍，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對順序盈包，但在不同的插入排序過程中沸呐，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂呢燥，所以shell排序是不穩(wěn)定的崭添。
(8)堆排序
我們知道堆的結(jié)構(gòu)是節(jié)點(diǎn)i的孩子為2 * i和2 * i + 1節(jié)點(diǎn)，大頂堆要求父節(jié)點(diǎn)大于等于其2個(gè)子節(jié)點(diǎn)叛氨，小頂堆要求父節(jié)點(diǎn)小于等于其2個(gè)子節(jié)點(diǎn)呼渣。在一個(gè)長為n 的序列，堆排序的過程是從第n / 2開始和其子節(jié)點(diǎn)共3個(gè)值選擇最大（大頂堆）或者最心骸（小頂堆）屁置，這3個(gè)元素之間的選擇當(dāng)然不會(huì)破壞穩(wěn)定性。但當(dāng)為n / 2 - 1仁连， n / 2 - 2蓝角， ... 1這些個(gè)父節(jié)點(diǎn)選擇元素時(shí)，就會(huì)破壞穩(wěn)定性怖糊。有可能第n / 2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過去了帅容，而第n / 2 - 1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒 有交換，那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了伍伤。所以并徘，堆排序不是穩(wěn)定的排序算法。
冒泡排序
/**
* 冒泡排序
*/
class Solution{
public:
void sort(vector<int> &nums){
int mark=1;
int size=nums.size();
while(mark !=0 ){
mark=0;
for(int i=0;i<size-1;i++){
if(nums[i]>nums[i+1]){
swap(nums[i],nums[i+1])
mark++;
}
}
}
}
};
選擇排序
/**
* 選擇排序
*/
class Solution{
public:
void sort(vector<int> &nums){
int size=nums.size();
for(int i=0;i<size-1;i++){
int temp=i;
for(int j=i+1;j<size;j++){
if(nums[temp] > nums[j])
temp=j;
}
swap(nums[temp],nums[i])
}
}
};
普通插入排序
- 算法原理
將數(shù)據(jù)分為兩部分扰魂，有序部分與無序部分麦乞，一開始有序部分包含第1個(gè)元素，依次將無序的元素插入到有序部分劝评，直到所有元素有序姐直。插入排序又分為直接插入排序、二分插入排序蒋畜、鏈表插入等声畏，這里只討論直接插入排序。它是穩(wěn)定的排序算法，時(shí)間復(fù)雜度為O(n^2) - 時(shí)間復(fù)雜度
在最好的情況下（元素已經(jīng)排好順序）：那么只需要循環(huán) n-1 次就可以了插龄，時(shí)間復(fù)雜度 O（n）
在最差的情況下 （元素是逆序的）：要循環(huán)調(diào)整次數(shù)： [ n * (n-1) ] / 2 愿棋，時(shí)間復(fù)雜度為 O（n ^ 2）
平均時(shí)間復(fù)雜度為：O（n ^ 2）
/**
* 普通插入排序
*/
class Solution{
public:
void sort(vector<int> &nums){
cout << " 普通法插入 " <<endl;
int size=nums.size();
for(int i=1;i<size;i++){
for(int j=i;j>0;j--){
if(nums[j-1]>nums[j]){
swap(nums[j-1],nums[j]);
}
else break;
}
}
}
private:
};
二分法插入排序
- 算法原理
折半插入排序的基本思想與直接插入排序一樣，在插入第i(i≥1)i(i≥1)個(gè)元素時(shí)均牢，前面i?1i?1個(gè)元素已經(jīng)排好序糠雨。區(qū)別在于尋找插入位置的方法不同，折半插入排序是采用折半查找法來尋找插入位置的徘跪。
折半查找法的基本思路是：用待插元素的值與當(dāng)前查找序列的中間元素的值進(jìn)行比較甘邀，以當(dāng)前查找序列的中間元素為分界，確定待插元素是在當(dāng)前查找序列的左邊還是右邊垮庐，如果是在其左邊松邪，則以該左邊序列為當(dāng)前查找序列，右邊也類似突硝。按照上述方法测摔，遞歸地處理新序列，直到當(dāng)前查找序列的長度小于1時(shí)查找過程結(jié)束解恰。 - 時(shí)間復(fù)雜度
折半插入排序適合記錄數(shù)較多的場景锋八，與直接插入排序相比，折半插入排序在尋找插入位置上面所花的時(shí)間大大減少护盈，但是折半插入排序在記錄移動(dòng)次數(shù)方面和直接插入排序是一樣的挟纱，所以其時(shí)間復(fù)雜度為O(n2)。
其次腐宋，折半插入排序的記錄比較次數(shù)與初始序列無關(guān)紊服。因?yàn)槊刻伺判蛘郯雽ふ也迦胛恢脮r(shí)，折半次數(shù)是一定的胸竞，折半一次就要比較一次欺嗤，所以比較次數(shù)也是一定的。
穩(wěn)定排序
/**
* 二分法插入排序
*
* 考慮邊界
*/
class Solution{
public:
void sort(vector<int> &nums){
cout << " 二分法插入 " <<endl;
int size=nums.size();
vector<int> ret;
ret.push_back(nums[0]);
for(int i=1;i<size;i++){
sortinsert(ret,nums[i]);
}
nums.swap(ret);
}
private:
void sortinsert(vector<int> &nums,int a){
int size=nums.size();
if((a>=nums[size-1])){
nums.push_back(a);
return;
}
else if((a<=nums[0])){
nums.insert(nums.begin(),a);
return;
}
int l=0;
int r=size-1;
int mid=0;
while(l<r){
mid=l+(r-l)/2;
if( nums[mid] < a){
if(a< nums[mid+1]){
mid=mid+1;
break;
}
else{
l=mid+1;
}
}
else if(a < nums[mid]){
if(nums[mid-1] < a){
// mid = mid-1;
break;
}
else{
r=mid-1;
}
}
else{
break;
}
}
auto beg=nums.begin();
beg+=mid;
nums.insert(beg,a);
return;
}
};
最后必須取low位置為插入點(diǎn)卫枝，因?yàn)閘ow之前的數(shù)字全部小于或等于插入值煎饼。
二分插入排序
public void BinaryInsertSort(int[] a, int left, int right) {
int low, middle, high;
int temp;
for (int i = left + 1; i <= right; i++) {
temp = a[i];
low = left;
high = i - 1;
while (low <= high) {
middle = (low + high) / 2;
if (a[i] < a[middle])
high = middle - 1;
else
low = middle + 1;
}
for (int j = i - 1; j >= low; j--)
a[j + 1] = a[j];
a[low] = temp;
}
希爾排序
- 算法原理
將無序數(shù)組分割為若干個(gè)子序列，子序列不是逐段分割的校赤，而是相隔特定的增量的子序列吆玖，對各個(gè)子序列進(jìn)行插入排序；然后再選擇一個(gè)更小的增量马篮，再將數(shù)組分割為多個(gè)子序列進(jìn)行排序......最后選擇增量為1沾乘，即使用直接插入排序，使最終數(shù)組成為有序浑测。 - 增量的選擇：
在每趟的排序過程都有一個(gè)增量翅阵，至少滿足一個(gè)規(guī)則 增量關(guān)系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序)；根據(jù)增量序列的選取其時(shí)間復(fù)雜度也會(huì)有變化，這個(gè)不少論文進(jìn)行了研究掷匠，在此處就不再深究读慎；本文采用首選增量為n/2,以此遞推，每次增量為原先的1/2槐雾，直到增量為1；
/**
* 希爾排序
*/
class Solution
{
public:
void sort(vector<int> &nums)
{
cout << " 希爾排序 " << endl;
int size = nums.size();
int interval = size;
int mult = 2;
while (1)
{ //loop times
interval = size / mult;
for (int i = 0; i < interval; i++)
{
for (int j = i + interval; j < size; j += interval)
{
for (int k = j; k >= interval; k -= interval)
{
if (nums[k - interval] > nums[k])
{
int temp = nums[k];
nums[k] = nums[k - interval];
nums[k - interval] = temp;
}
else
{
break;
}
}
}
}
mult *= 2;
if (interval == 1)
return;
}
}
};
/**
* 希爾排序
*/
class Solution
{
public:
void sort(vector<int> &nums)
{
for (int gap = nums.size() >> 1; gap > 0; gap >>= 1)
{ // times
for (int i = gap; i < nums.size(); i++)
{
for (int j=i; j >gap-1; j -= gap)
{
if(nums[j-gap]>nums[j])
swap(nums[j-gap],nums[j])
else break;
}
}
}
}
};
快速排序
算法原理
快速排序是目前在實(shí)踐中非常高效的一種排序算法幅狮，它不是穩(wěn)定的排序算法募强，平均時(shí)間復(fù)雜度為O(nlogn)，最差情況下復(fù)雜度為O(n^2)崇摄。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分擎值，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序逐抑，整個(gè)排序過程可以遞歸進(jìn)行鸠儿，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。平均時(shí)間復(fù)雜度 nlogN
n個(gè)數(shù)字厕氨，每次分成兩份进每，一共要分logn次，每一次排序要操作n次命斧。所以平均時(shí)間復(fù)雜度為 nlogn田晚。最差事件復(fù)雜度 n^2
最差的情況就是每一次取到的元素就是數(shù)組中最小/最大的，這種情況其實(shí)就是冒泡排序了(每一次都排好一個(gè)元素的順序)
這種情況時(shí)間復(fù)雜度就好計(jì)算了国葬，就是冒泡排序的時(shí)間復(fù)雜度：T[n] = n * (n-1) = n^2 + n;
綜上所述：快速排序最差的情況下時(shí)間復(fù)雜度為：O( n^2 )
/**
* 快速排序
* 基準(zhǔn)數(shù)字的位置與先從右邊開始找還從左邊開始找是有聯(lián)系的贤徒。
* 若基準(zhǔn)數(shù)字在左邊，則應(yīng)該先從右邊開始找汇四，這樣找到的最后位置肯定是
* 數(shù)值比基準(zhǔn)數(shù)字小接奈。
* 若從左邊開始找，則找到的最后位置肯定是數(shù)值比基準(zhǔn)數(shù)字大通孽。
*/
另一組實(shí)現(xiàn)序宦，從頭開始遍歷，標(biāo)準(zhǔn)值為A利虫，維護(hù)兩個(gè)pos,pos1表示當(dāng)前比較的數(shù)據(jù)位置挨厚，pos2表示當(dāng)前最靠前的一個(gè)大于A的數(shù)字的位置。如果pos1的數(shù)值小于A糠惫，則交換pos1和pos2的數(shù)值疫剃。然后pos1++,pos++。否則只有pos1++硼讽。
也就是說pos2之前的數(shù)字都是小于A的巢价，pos2到pos1之間的數(shù)字都是大于等于A。
class Solution
{
public:
void sort(vector<int> &nums)
{
cout << " 快速排序 " << endl;
quick_sort(nums,0,nums.size()-1);
}
private:
void quick_sort(vector<int> &nums, int cl, int cr)
{
int l = cl;
int r = cr;
int mark = l;
if (l < r)
{
while (l < r)
{
while (nums[r] >= nums[mark] && l < r)
r--;
while (nums[l] <= nums[mark] && l < r)
l++;
swap(nums[l], nums[r]);
}
swap(nums[r], nums[mark]);
quick_sort(nums, cl, l);
quick_sort(nums, l + 1, cr);
}
}
};
堆排序
- 堆排序原理
a.將無需序列構(gòu)建成一個(gè)堆，根據(jù)升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換壤躲，將最大元素"沉"到數(shù)組末端;
c.重新調(diào)整結(jié)構(gòu)城菊，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素碉克，反復(fù)執(zhí)行調(diào)整+交換步驟凌唬，直到整個(gè)序列有序。
/**
* 堆排序
*/
class Solution
{
public:
void sort(vector<int> &nums)
{
cout << " 堆排序 " << endl;
int n=nums.size();
for(int i = n/2-1; i>=0 ;i--)// n是數(shù)組中數(shù)字的個(gè)數(shù)
{
max_heapify(nums, i, n-1);
}
for(int i=n-1; i>0;i--){
swap(nums[0],nums[i]);
max_heapify(nums,0,i-1);
}
}
private:
void max_heapify(vector<int> &nums, int beg, int end)//beg和end是以數(shù)組下標(biāo)計(jì)算
{
int parent=beg;
int child=parent*2+1;
while(child<=end){
if(child+1<=end && nums[child+1] > nums[child])
child++;
if(nums[child] > nums[parent]){
swap(nums[child],nums[parent]);
parent=child;
child=parent*2+1;
}
else break;
}
}
};
歸并排序
- 算法原理
歸并排序具體工作原理如下（假設(shè)序列共有n個(gè)元素）：
將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作（merge)漏麦，形成floor(n/2)個(gè)序列客税，排序后每個(gè)序列包含兩個(gè)元素
將上述序列再次歸并，形成floor(n/4)個(gè)序列撕贞，每個(gè)序列包含四個(gè)元素
重復(fù)步驟2更耻，直到所有元素排序完畢
歸并排序是穩(wěn)定的排序算法，其時(shí)間復(fù)雜度為O(nlogn)捏膨，如果是使用鏈表的實(shí)現(xiàn)的話秧均，空間復(fù)雜度可以達(dá)到O(1)，但如果是使用數(shù)組來存儲(chǔ)數(shù)據(jù)的話号涯，在歸并的過程中目胡，需要臨時(shí)空間來存儲(chǔ)歸并好的數(shù)據(jù)，所以空間復(fù)雜度為O(n)
/**
* 歸并排序
*/
class Solution{
public:
void sort(vector<int> &nums)
{
cout << " 歸并排序 " << endl;
int size=nums.size();
int i=1;
while(i<size){
int beg=0;
int mid=beg+i-1<size-1?beg+i-1:size-1;
int end=beg+2*i-1<size-1?beg+2*i-1:size-1;
while(mid<end){
merge_sort(nums,beg,mid,end);
beg=end+1;
mid=mid=beg+i-1<size-1?beg+i-1:size-1;
end=beg+2*i-1<size-1?beg+2*i-1:size-1;
}
i*=2;
}
}
private:
void merge_sort(vector<int> &nums,int beg,int mid,int end){
vector<int> temp;
int pos1=beg;
int pos2=mid+1;
while(pos1<=mid || pos2<=end){
if(pos1<=mid && pos2<=end){
if(nums[pos1]<=nums[pos2]){
temp.push_back(nums[pos1]);
pos1++;
}
else{
temp.push_back(nums[pos2]);
pos2++;
}
}
else if(pos1<=mid){
temp.push_back(nums[pos1]);
pos1++;
}
else{
temp.push_back(nums[pos2]);
pos2++;
}
}
for(int i=0;i<=end-beg;i++){
nums[beg+i]=temp[i];
}
}
};
int main()
{
Solution sol;
// vector<int> a {25, 34, -4, 0, 4, 9, 6, -1, 7, 2, 7, 25, 19, 20,-23,-11,43,29,1,0,0};
vector<int> a {45, 34, 0, -4, 8,5,8};
sol.sort(a);
for (auto &w : a)
{
cout << w << " ";
}
cout << endl;
}
