一、歸并排序演算法
1.1 撰寫歸并排序，記住下面的內容，代碼也就游刃有余了！
(1) 首先確定陣列的中間位置的分界點（下標），也就是mid=(left+right)>>1，分成left,right兩段，
(2) 然后遞回排序left,right兩端，
(3) 最后就是將兩個有序的陣列歸并，合二為一，這一部分是歸并排序最難的，
二、歸并排序演算法的核心
2.1 主要的思想也是分治
同樣是分治，但是這里的分治與快速排序的分治不一樣，
@快排是拿隨機一個數來分，分完之后，保證讓左邊小于等于分界點，右邊大于等于分界點，
@歸并則是以整個陣列最中心的位置，分成兩段，兩端排序完，使用雙指標演算法，
2.2 雙指標演算法
2.3 歸并排序穩定
穩定指的并不是時間效率上，而是說兩個相同的數值，可以保證排完序后位置不變，而快速排序做不到這點，當然修改后的快排，每個數改成pair,保證沒有相同的數值，也能穩定，
三、歸并排序演算法的代碼模板
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];//存回
}
查看更多
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91961.html
標籤：其他