快速排序及歸并排序的實現與排序的穩定性

快速排序

一. 快速排序遞歸的實現方法

1. 左右指針法

步驟思路

為什么要讓end先走？

2. 挖坑法

步驟思路

3. 前后指針法

步驟思路

二. 快速排序的時間和空間復雜度

1. 時間復雜度

2. 空間復雜度

三. 快速排序的優化方法

1. 三數取中優化

2. 小區間優化

四. 使用棧來實現非遞歸快排

步驟思路

歸并排序

?編輯

一. 歸并排序的遞歸實現

步驟思路

二. 時間復雜度與空間復雜度

1. 時間復雜度

2. 空間復雜度

三. 非遞歸實現歸并排序

步驟思路

排序算法的穩定性

快速排序

一. 快速排序遞歸的實現方法

1. 左右指針法

步驟思路

(假設排升序)將數組a最左邊的下標用begin記錄下來，最右邊用end記錄下來，定義一個key為begin或end

(假設key定義為begin)end先向左查找找到<a[key]的數停下，begin再向右查找找到>a[key]的值停下，此時將begin指向的值與end指向的值交換，以此類推直到end的值<=begin，將此時的a[key]與begin與end相遇坐標的值交換，我們發現此時的a[key]，左邊的值都比其小，右邊的值都比其大，那就說明key所指向的值在數組中已經排好位置了

如以下代碼，即完成了單趟

		int key = left;int begin = left, end = right;while (begin < end){while (a[end] >= a[key] && begin < end){end--;}while (a[begin] <= a[key] && begin < end){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);

我們在end和begin尋找比a[key]大或小的值的時候不要忘記也要判斷循環成立的條件

既然key已經在數組排好位置，我們接下來遞歸就不需要加上key了，只需要遞歸key的左右區間即可，直到遞歸的區間左邊與右邊相等即只有一個數

完整代碼如下

void QuickSort1(int* a, int left,int right)
{if (left >= right)return;int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int key = left;int begin = left, end = right;while (begin < end){while (a[end] >= a[key] && begin < end){end--;}while (a[begin] <= a[key] && begin < end){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, begin + 1, right);
}

為什么要讓end先走？

左邊做key右邊先走，可以保證相遇位置比key小
相遇場景分析

begin遇end：end先走，停下來，end停下條件是遇到比key小的值,end停下來的位置一定比key小,begin沒有找到大的遇到end停下了
end遇begin:end先走，找小，沒有找到比key更小的，直接跟begin相遇了。begin停留的位置是上一輪交換的位置(即，上一輪交換，把比key小的值，換到begin的位置了）
同樣道理讓右邊做key，左邊先走，可以保證相遇位置比key要大??

2. 挖坑法

步驟思路

(假設排升序，給數組a)將最左邊的值定義key存儲起來，最左邊的下標用bigen記錄，最右邊的下標用end記錄，定義pivot記錄為最左邊的下標，即將最左邊視為坑位

然后end向左尋找比key小的值放到pivot所指向的位置即坑位中，并將這個地方(end所找到的)視作新的坑(更新pivot的值)。

begin向右尋找比key大的值，放到坑位中，并將這個地方視作新的坑(更新pivot的值)

重復以上步驟直到end<=begin

然后將key填進pivot中，再通過遞歸，即可完成排序

由于與左右指針法類似就不寫單趟，直接上完整代碼

void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int key = a[left];int begin = left, end = right;int pivot = left;while (begin < end){while (a[end] >= key && begin < end){end--;}a[pivot]=a[end];pivot = end;while (a[begin] <= key && begin < end){begin++;}a[pivot] = a[begin];pivot = begin;}a[pivot] = key;QuickSort2(a, left, pivot - 1);QuickSort2(a, pivot + 1, right);
}

3. 前后指針法

步驟思路

(假設排升序)定義key為數組最左邊的下標，并定義，prev=key與after=key+1

after在找到比key指向的值小的值時，prev++，并將after指向的值與現在的prev(即prev++后的值)交換

以此往復，直到after>數組的值

然后將prev所指向的值與key所指向的值交換

代碼如下

我們要注意，當prev++后的值==after就會發生與自身交換

完成一次后，效果依然是a[key]左區間的值比其小，右區間的值比其大

	int key = left;int prev = left, after = left + 1;while (after<=right){while (a[after] < a[key]&&++prev!=after){Swap(&a[prev], &a[after]);}after++;}Swap(&a[prev], &a[key]);

遞歸是和上面兩種方法同樣的道理

完整代碼如下

void QuickSort3(int* a,int left,int right)
{if (left >= right)return;int key = left;int prev = left, after = left + 1;while (after<=right){while (a[after] < a[key]&&++prev!=after){Swap(&a[prev], &a[after]);}after++;}Swap(&a[prev], &a[key]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev + 1, right);
}

二. 快速排序的時間和空間復雜度

1. 時間復雜度

①最好情況

每次的劃分都使得劃分后的子序列長度大致相等，一般在數據已經部分有序或者隨機分布的情況下發生。此時時間復雜度為O(Nlog?N)

②最壞情況

在待排序序列有序的情況下，每一次劃分的兩個區間都有一個為0，此時快速排序的時間復雜度退化為O(N2)

③平均情況

實際應用中快速排序的平均情況大概會接近于最好情況，因為待排序序列通常不是有序的，我們還可以通過三數取中來優化，減少最壞情況的可能性，所以快速排序的時間復雜度為O(Nlog?N)

2. 空間復雜度

由于需要遞歸調用，相當于求遞歸樹的深度，

①最壞情況

當數組接近有序時，遞歸深度很深，空間復雜度為O(N)

②最好情況

當數組無序時，遞歸樹基本相當與完全二叉樹，空間復雜度為O(log?N)

③平均情況

實際應用中，平均情況大概會接近最好情況，同樣可以用三數取中優化

所以快速排序空間復雜的為O(log?N)

三. 快速排序的優化方法

1. 三數取中優化

為了讓每次左右區間長度接近，我們可以使用三數取中，即最左邊最右邊與中間的值取不大也不小的一個值并返回

int GetMid(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right])return mid;else if (a[left] < a[right])//上面if條件不成立可得a[right]<a[mid]return right;else//又可得 a[left] > a[right]return left;}else//a[left]>=a[mid]{if (a[mid] > a[right])return mid;else if (a[left]<  a[right])//上面if條件不成立可得a[right]>a[mid]return left;else//又可得 a[left] < a[right]return right;}}

將返回值接收并將其指向位置與最左邊的值交換，代碼如下

		if (left >= right)return;int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int key = left;

2. 小區間優化

當快速排序要排的數據很長時，越遞歸到后面區間越小遞歸的層數越多，我們可以考慮，當要遞歸區間小于10的時候用別的排序來代替，這樣就可以省去80%到90%的遞歸

代碼如下

void QuickSort1(int* a, int left,int right)
{if ( (right-left+1)<10)//小區間優化{InsertSort(a+left, right - left + 1);//a+left 有可能是后半段區間//減少遞歸層數}else{if (left >= right)return;int mid = GetMid(a, left, right);Swap(&a[mid], &a[left]);int key = left;int begin = left, end = right;while (begin < end){while (a[end] >= a[key] && begin < end){end--;}while (a[begin] <= a[key] && begin < end){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, begin + 1, right);}
}

四. 使用棧來實現非遞歸快排

棧的實現可以看一下我以前的博客

棧的實現詳解-CSDN博客

步驟思路

初始化棧后，將數組的最右邊與最左邊分別放入棧(即將一個區間放入棧中)

進入循環(當棧為空時循環結束)，用begin和begin1接收棧頂端的值，再刪除棧的值，再用end和end1接收棧頂端的值，再刪除棧的值，使用左右指針法(挖坑法，前后指針法皆可)(用begin與end來尋找值，begin1與end1不變)進行一趟排序，

如果right1>=begin+1 就往棧里存 right1(當前排序區間的最右邊) 和 begin+1 反之不存

如果left1<=begin-1 就往棧里存? begin-1 和 left1(當前排序區間的最左邊)? 反之不存

最后不要忘記銷毀棧

代碼如下

void StackQuickSort(int* a, int left, int right)
{ST s;StackInit(&s);StackPush(&s, right);StackPush(&s, left);while (!StackEmpty(&s)){int begin = StackTop(&s);int left1 = begin;StackPop(&s);int end = StackTop(&s);int right1= end;StackPop(&s);int key = begin;//int mid = GetMid(a, begin, end);//Swap(&a[mid], &a[begin]);while (begin < end){while (a[end] >= a[key] && begin < end){end--;}while (a[begin] <= a[key] && begin < end){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);if(right1>=begin+1){StackPush(&s,right1);StackPush(&s, begin + 1);}if(left1<=begin-1){StackPush(&s, begin - 1);StackPush(&s, left1);}}StackDestroy(&s);
}

歸并排序

一. 歸并排序的遞歸實現

步驟思路

malloc一個臨時數組進入子函數(創建子函數遞歸會更方便)，進行遞歸，子函數利用分治思想一直遞歸直到left>=right 開始執行下面操作

k賦初值為當前區間最左邊，begin1 ， end1來記錄左數組最左邊和最右邊，定義begin2 ，end2 來記錄右數組的最左邊和最右邊，將兩個數組從頭比較，較小的賦值給臨時數組，直到有一方賦完值，再將沒賦完值的數組給臨時數組賦值。最后給要排序數組left到right賦值為臨時數組left到right

代碼如下

//遞歸
void _MergeSort(int* a,int* tmp, int left, int right)
{if(left>=right){return;}int mid = (left + right) / 2;//如果[left,mid][mid+1,right]有序就可以歸并了_MergeSort(a,tmp, left, mid);_MergeSort(a,tmp, mid + 1, right);int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int k=left;while (begin1 <= end1&&begin2<=end2){if(a[begin1]<a[begin2]){tmp[k++] = a[begin1++];}else{tmp[k++] = a[begin2++];}}while (begin1 <= end1){tmp[k++] = a[begin1++];}while (begin2 <= end2){ tmp[k++] = a[begin2++];}for (int i = left; i <= right; i++){a[i] = tmp[i];}}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//_MergeSort(a, tmp, 0, n - 1);_MergeSort2(a,tmp,  n);free(tmp); tmp = NULL;
}

二. 時間復雜度與空間復雜度

1. 時間復雜度

歸并排序的時間復雜度是穩定的，不受輸入數組的初始順序影響

?將數組分成兩個子數組的時間復雜度為O(1)，遞歸對子數組進行排序，假設每個子數組長度為n

則兩個子數組排序的總時間復雜度為O(NlogN)，將兩個有序數組合并為一個有序數組時間復雜度為O(N)，所以歸并排序時間復雜度為O(NlogN)

2. 空間復雜度

調用棧所需要的額外空間為O(logN)，因為我們需要一個額外數組來存儲數據所以又額外消耗O(N)的空間，我們將較小的O(logN)忽略可以得到歸并排序的空間復雜度為O(N)

三. 非遞歸實現歸并排序

步驟思路

開辟動態空間后定義一個數gap=1來控制區間(gap相當于每組數據個數)，(每一次gap*2，使每次區間擴大)gap<數組長度

設計一個for循環i+=gap*=2

每次分兩組[i][i+gap-1]和[i+gap][i+2*gap-1]? (i每次+=正好跳過這些數據)

將兩個區間的值比較放入新開辟的數組，再拷貝到原數組

代碼如下

//非遞歸
void _MergeSort2(int* a,int* tmp,int n)
{int gap = 1;while(gap<n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i;int end1 = i + gap - 1;;int begin2 = i + gap;int end2 = i + 2 * gap - 1;int k = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[k++] = a[begin1++];}else{tmp[k++] = a[begin2++];}}while (begin1 <= end1){tmp[k++] = a[begin1++];}while (begin2 <= end2){tmp[k++] = a[begin2++];}//memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));for (int j = i; j < k; j++){a[j] = tmp[j];}}gap *= 2;}
}

但是我們發現，這樣如果會發生越界的現象

一共三種可能

1. [begin1,end1][begin2,end2] ?end2越界
2. [begin1,end1][begin2,end2] ?begin2，end2越界
3. [begin1,end1][begin2,end2] ?end1，begin2，end2越界

?第2,3種我們可以直接不遞歸了，因為后面區間的不存在前面區間的在上一次已經遞歸好了，

第一種呢我們需要把區間(即end)給修正一下

修正代碼如下

//非遞歸
void _MergeSort2(int* a,int* tmp,int n)
{int gap = 1;while(gap<n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i;int end1 = i + gap - 1;;int begin2 = i + gap;int end2 = i + 2 * gap - 1;int k = i;if (begin2 >= n)//第二種情況,第二組不存在，不需要歸并break;if (end2 >= n)//第一種情況，需要修正一下end2 = n - 1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[k++] = a[begin1++];}else{tmp[k++] = a[begin2++];}}while (begin1 <= end1){tmp[k++] = a[begin1++];}while (begin2 <= end2){tmp[k++] = a[begin2++];}//memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));for (int j = i; j < k; j++){a[j] = tmp[j];}}gap *= 2;}
}

排序算法的穩定性

假定在待排序的記錄序列中，存在多個具有相同關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變

即原序列中 r[i]=r[j],且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]前，則稱這種排序算法是穩定的，否則是不穩定的

冒泡選擇	穩定
選擇排序	不穩定***	只會考慮自身，假如找到最小值1下標為3，將其與下標為0(假設此處為6)處交換若下標為1處也是6，就改變了
直接插入排序	穩定
希爾排序	不穩定(分組)	預排序時相同的值可能分到不同的組
堆排序	不穩定	建堆時可能就亂了
歸并排序	穩定	當兩個數相等，讓第一個下來就是穩定的（可以控制）
快速排序	不穩定	end先找到 j 和begin交換了，在找到 i 和bigin交換，顯然改變了