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

程序員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