最簡練寫法實作歸并排序【C++代碼】

目錄

歸并排序

C++代碼實作

穩定性分析

求逆序對

歸并排序

歸并排序的思想是分治。其過程也就是“分”和“治”的兩個步驟。

對于一個序列，我們先将其一分為二，分别排好序，然後再合并這兩個有序數列。

對于被平分成的兩部分怎麼排序呢？再一分為二，遞歸下去，直至分成單個元素時，即自然有序了。

C++代碼實作

網上很多代碼會把歸并排序的分和治兩個環節分開寫，這樣可能好了解，但是函數太多了，備援。

我更習慣将其合并起來寫，看起來更簡潔。

int t[50005]; //用于暫時存放合并的元素的空數組
void merge_sort(int* a,int l,int r){
//分
	if (l==r) return;  //遞歸出口
	int mid=(l+r)/2;
	merge_sort(a,l,mid);
	merge_sort(a,mid+1,r);
//治
	int i=l;
	int j=mid+1;
	for (int k=l; k<=r; k++){ //合并
		if ( (j>r) || (i<=mid && a[i]<=a[j]) ) {
			t[k]=a[i];
			i++;
		} else {
			t[k]=a[j];
			j++; 
		}
	}
	for (int k=l; k<=r; k++) a[k]=t[k]; //複制
}
           

函數調用 void merge_sort(int* a,int l,int r)，傳入參數分别為 待排序數組，以及左右邊界l，r。 

要注意當數組用vector時，需要傳入的是引用，也就是說，必須修改原數組。

代碼分成兩大部分

第一部分是“分”：

    先計算出區間[l,r]的中點mid，然後一直遞歸下去。

    遞歸出口是 (l==r)，也就是一個數的時候，自然是有序的，也就可以執行第二部分的“治”的步驟。

第二部分是“治”：

    對于排好序的兩個數組，進行合并。

    合并的元素需要暫時放到一個空的數組，最後再複制回來。t就是那個暫時的空數組。

    具體合并的方法是用兩個指針 i ，j 分别指向待合并的兩部分。其中判斷a[i]<=a[j]的條件需要特别注意，要考慮周全。

    if ( (j>r) || (i<=mid && a[i]<=a[j]) ) 的意思是： 如果右區間越界（也就是合并完了），或者左區間沒越界并且滿足小于條件，才選擇左區間的數。

穩定性分析

歸并排序是穩定的嗎？答：上述版本是穩定的。

我們分析一下，在合并兩個有序部分時，當 a[i]==a[j] ，我們總是先取 a[i] ，而指針 i 是永遠小于 j 的，是以是穩定的。

而如果判斷條件    if ( (j>r) || (i<=mid && a[i]<a[j]) )  也就是缺少這個等号的話，就不是穩定的。

求逆序對

利用歸并排序求逆序對隻需要加一個統計變量即可。

在合并兩個有序部分的過程中，當選擇了左區間的指針 i 時，我們檢視下這時的 j 的大小，計算出已經選擇了幾個數， 也就是 j-(mid+1)。

 因為 i 是小于 j 的，但是這幾個數已經被選擇就說明 a[i]>a[j] ，是以有幾個數，就是有幾個逆序對。

int ans=0;  //用于統計逆序對
int t[50005]; //用于暫時存放合并的元素的空數組
void merge_sort(vector<int>& a,int l,int r){
//分
	if (l==r) return;  //遞歸出口
	int mid=(l+r)/2;
	merge_sort(a,l,mid);
	merge_sort(a,mid+1,r);
//治
	int i=l;
	int j=mid+1;
	for (int k=l; k<=r; k++){ //合并
		if ( (j>r) || (i<=mid && a[i]<=a[j]) ) {
			t[k]=a[i];
			i++;
            ans+=j-(mid+1); //統計逆序對
		} else {
			t[k]=a[j];
			j++; 
		}
	}
	for (int k=l; k<=r; k++) a[k]=t[k]; //複制
}