學歸並排序和逆序對，這篇文章就够了，直面秋招

程序員ioms 2021-09-18 03:44:35 阅读数:338

排序逆序篇文章文章够了

(3).代碼


//歸並排序模板
const int maxn = 1e5 + 10;
int a[maxn],b[maxn];
void msort(int l, int r)
{
if (l == r) return; //如果只有一個數字則返回，無需排序
int mid = (l + r) / 2;
msort(l, mid); //分解左序列
msort(mid + 1, r); //分解右序列
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r)
{
if (a[i] <=a[j])
{
b[k] = a[i]; k++; i++;
}
else
{
b[k] = a[j]; k++; j++;
}
}
while (i <= mid) //複制左邊子序列剩餘
{
b[k] = a[i]; k++; i++;
}
while (j <= r) //複制右邊子序列剩餘
{
b[k] = a[j]; k++; j++;
}
for (int i = l; i <= r; i++)
{
a[i] = b[i];
}
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.

簡化版


const int maxn = 1e5 + 10;
int q[maxn], tmp[maxn];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return; //如果只有一個數字或沒有數字，則無需排序
int mid = (l + r ) /2;
merge_sort(q, l, mid); //分解左序列
merge_sort(q, mid + 1, r); //分解右序列
int k = l, i = l, j = mid + 1;
while (i <= mid && j <= r) //合並
{
if (q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while (i <= mid) tmp[k++] = q[i++]; //複制左邊子序列剩餘
while (j <= r) tmp[k++] = q[j++]; //複制右邊子序列剩餘
for (int i = l; i <= r; i++) q[i] = tmp[i];
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.

[](

)2.逆序對

(1).介紹

上述提到歸並排序是穩定的排序，相等的元索的順序不會改變，進而用其可以解决逆序對的問題。首先我們了解一下什麼是逆序對。

逆序對:設 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個。

所謂逆序對的問題，即對給定的數組序列,求其逆序對的數量。

從逆序對定義上分析，逆序對就是數列中任意兩個數滿足大的在前,小的在後的組合。如果將這些逆序對都調整成順序(小的在前，大的在後),那麼整個數列就變得有序，即排序。因面，容易想到冒泡排序的機制正好是利用消除逆序來實現排序的，也就是說，交換相鄰兩個逆序數，最終實現整個序列有序，那麼交換的次數即為逆序對的數量。

冒泡排序可以解决逆序對問題，但是由於冒泡排序本身效率不高，時間複雜度為O(n^2),對於n比較大的情况就沒用武之地了。我們可以這樣認為，冒泡排序求逆序對效率之所以低，是因為其在統計逆序對數量的時候是一對一對統計的，而對於範圍為n的序列，逆序對數量最大可以是(n+1)*n/2,因此其效率太低.那怎樣可以一下子統計多個，而不是一個一個累加呢?這個時候，歸並排序就可以幫我們來解决這個問題。

在合並操作中，我們假設左右兩個區間元素為：

左邊：{3 4 7 9} 右邊：{1 5 8 10}

那麼合並操作的第一步就是比較3和1,然後將1取出來放到輔助數組中,這個時候我們發現，右邊的區間如果是當前比較的較小值，那麼其會與左邊剩餘的數字產生逆序關系，也就是說1和3、4、7、9都產生了逆序關系，我們可以一下子統計出有4對逆序對。接下來3,4取下來放到輔助數組後，5與左邊剩下的7、9產生了逆序關系，我們可以統計出2對。依此類推,8與9產生1對,那麼總共有4+2+1對。這樣統計的效率就會大大提高，便可較好地解决逆序對問題。

而在算法的實現中，我們只需略微修改原有歸並排序,當右邊序列的元素為較小值時，就統計其產生的逆序對數量，即可完成逆序對的統計。.

(2).代碼


const int maxn = 1e5 + 10;
int q[maxn], tmp[maxn];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return; //如果只有一個數字或沒有數字，則無需排序
int mid = (l + r )/2;
merge_sort(q, l, mid); //分解左序列
merge_sort(q, mid + 1, r); //分解右序列
int k = l, i = l, j = mid + 1;
while (i <= mid && j <= r) //合並
{
if (q[i] <= q[j]) tmp[k++] = q[i++];
else
# 最後
2020年在匆匆忙忙慌慌亂亂中就這麼度過了，我們迎來了新一年，互聯網的發展如此之快，技術日新月异，更新迭代成為了這個時代的代名詞，堅持下來的技術體系會越來越健壯，JVM作為如今是跳槽大廠必備的技能，如果你還沒掌握，更別提之後更新的新技術了。
![學歸並排序和逆序對，這篇文章就够了，直面秋招_Java](https://s5.51cto.com/images/20210918/1631907270933184.jpg)
**更多JVM面試整理：**
![學歸並排序和逆序對，這篇文章就够了，直面秋招_程序員_02](https://s7.51cto.com/images/20210918/1631907270229607.jpg)
**[CodeChina開源項目：【一線大廠Java面試題解析+核心總結學習筆記+最新講解視頻】](https://ali1024.coding.net/public/P7/Java/git)**


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.

版权声明：本文为[程序員ioms]所创，转载请带上原文链接，感谢。 https://gsmany.com/2021/09/20210918034434915N.html

《 100天的默契