歸並排序解題套路

nighty_k 2022-01-07 20:00:17 阅读数:918

排序 套路

歸並排序模板

void merge_sort(int q[], int l, int r)
{

if (l >= r) return;
int mid = l + r >> 1;//取整個區間的中點
merge_sort(q, l, mid);//遞歸排序左邊
merge_sort(q, mid + 1, r);//遞歸排序右邊
//排完之後,左右兩邊就都有序了
int k = 0, 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 ++ ];//左右兩端,有一邊沒有循環完的話,就把剩下的數直接接到tmp裏
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//存回
}

思路

1.歸並主要的思想也是分治,同樣是分治,但是這裏的分治與快速排序的分治不一樣

1.1快排是拿隨機一個數來分,分完之後,保證讓左邊小於等於分界點,右邊大於等於分界點
1.2歸並則是以整個數組最中心的比特置,分成兩段,兩端排序完,使用雙指針算法

2.雙指針算法
3.過程

3.1首先確定數組的中間比特置的分界點(下標),也就是mid=(left+right)>>1,分成left,right兩段
3.2然後遞歸排序left,right兩端
3.2最後就是將兩個有序的數組歸並,合二為一,這一部分是歸並排序最難的

4.歸並排序穩定

穩定指的並不是時間效率上,而是說兩個相同的數值,可以保證排完序後比特置不變。而快速排序做不
到這點,當然修改後的快排,每個數改成pair,保證沒有相同的數值,也能穩定

版权声明:本文为[nighty_k]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072000172756.html