排序：歸并排序與逆序對

一、概念

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

時間復雜度：O(nlogn)

二、算法描述

1.將數組拆分成單個元素，兩兩歸并。 2.對于兩組同向有序數組，首先判斷兩組數的首位的大小，并將較小的數保留到一個新數組中。 3.再比較較小組數的第二位和另一組數的第一位，仍然保留較小的數，這樣就保證新數組的有序，需要注意的是當任意一組數為空時，就自然將另一組數的剩下數接到新數組后（因為剩下的樹肯定比剛放進去的大）。

三、逆序對

逆序對問題設 A 為一個有 n 個數字的有序集 (n>1)，其中所有數字各不相同。如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則 A[i], A[j]這個有序對稱為 A 的一個逆序對，也稱作逆序數。?

例如，數組（3，1，4，5，2）的逆序對有(3,1),(3,2),(4,2),(5,2)，共4個。

四、歸并排序與逆序對

因為在排序的合并過程中是將兩組有序數進行比較，所以根據逆序對的定義，在數組下標 i 小于 j 時，如果有 a[i] 大于 a[j] 就可以知道下標 i 后面所有數都與 a[j] 構成逆序數，只需添加一句求和語句即可求出逆序數了；

例題?POJ1804 Brainman

解題思路

最簡單的關于逆序對的題目，題目大意是給出一個序列，求最少移動多少步能使它順序，規定只能相鄰移動。
相鄰移動的話，假設a，b 相鄰，若a<b 交換會增加逆序數，所以最好不要做此交換；若a==b 交換無意義，也不要進行此交換；a>b時，交換會減少逆序，使序列更順序，所以做交換。
由上可知，所謂的移動只有一種情況，即a>b，且一次移動的結果是逆序減1。假設初始逆序是n，每次移動減1，那么就需要n次移動時序列變為順序。所以題目轉化為直接求序列的逆序便可以了。

AC代碼

#include<cstdio> int a[1005];//存儲數串的數組 int t[1005];//排好序的數組 int ans;//逆序對數void merge(int l, int m, int r)//因為起點和終點不變，所以用i，j來表示可變的下標 {int k = l, i = l, j = m + 1;while (i <= m && j <= r)//分解數組的首元素進行比較，兩個數組分別為[l,m][m+1,r] {if (a[i] > a[j])//構成逆序對 {t[k++] = a[j++];//將較小的元素加入排序后的數組,并移動到下一元素ans = ans + m - i + 1;//從i到middle的值都大于a[j]，所以逆序對增加m-i+1 }else{t[k++] = a[i++];}}while (i <= m) t[k++] = a[i++];//若左邊還有剩下的while (j <= r) t[k++] = a[j++];for (i = l; i <= r; i++)a[i] = t[i];//更新原數組為合并后的數組 }void mergeSort(int l,int r)//歸排 {if (l < r)//遞歸終止條件 {int m = (l + r) / 2;mergeSort(l, m);mergeSort(m + 1, r);//此時已經通過遞歸全部拆分merge(l, m, r);//從單元素開始合并 } }int main() {int T, n, cnt = 1;scanf("%d", &T);while (T--){ans = 0;scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%d", &a[i]);mergeSort(0, n - 1);printf("Scenario #%d:\n", cnt++);printf("%d\n\n", ans);}return 0; }

例題?POJ2299?Ultra-QuickSort

解題思路

簡單直接的歸并排序求逆序數，和上一題一模一樣。難點是n < 500000，所以答案用int32會WA，要用int64，用long long int也可以，取值范圍一樣的，printf函數對應I64d和lld。

AC代碼

#include<cstdio> const int N = 500500; int a[N]; int t[N]; __int64 ans;void merge(int l, int m, int r) {int k = l, i = l, j = m + 1;while (i <= m && j <= r){if (a[i] > a[j]){t[k++] = a[j++];ans += m - i + 1;}else{t[k++] = a[i++];}}while (i <= m)t[k++] = a[i++];while (j <= r)t[k++] = a[j++];for (int i = l; i <= r; i++)a[i] = t[i]; }void mergeSort(int l, int r) {int m = (l + r) / 2;if (l < r){mergeSort(l, m);mergeSort(m + 1, r);merge(l, m, r);} }int main() {int n;scanf("%d", &n);while (n != 0){ans = 0;for (int i = 0; i < n; i++)scanf("%d", &a[i]);mergeSort(0, n-1);printf("%I64d\n", ans);scanf("%d", &n);}return 0; } AC代碼

?

轉載于:https://www.cnblogs.com/yun-an/p/11097712.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的POJ-排序-归并排序与逆序对的全部內容，希望文章能夠幫你解決所遇到的問題。

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