思路
- 第一步:找出mid
-------mid
--------↓
1,5,7,3,9,10,5,2,4,8
l~~~~~~~~~~~~~~~~~~r
i~~~~~~~~~j(mid+1)
如上,i=l,j=mid+1
- 第二步:递归排序左边和右边
- 第三步:合并
left合right分别排序好后如下
l
i-------mid
↓-------↓
1,3,5,7,9
2,4,5,8,10
↑-------↑
j-------r
↑
mid+1
模板
public class MergeSort787 {
public static int[] tmp = new int[100010];
public static void main(String[] args) {
int[] q = new int[]{3, 5, 3, 9, 8};
mergeSort(q, 0, q.length - 1);
for (int value : q) {
System.out.print(value + " ");
}
}
private static void mergeSort(int[] q, int l, int r) {
if (l >= r) {
return;
}
// 找出中点
int mid = l + r >> 1;
// 排序左和右
mergeSort(q, l, mid);
mergeSort(q, mid + 1, r);
// 合并
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
// ↑:用<=是因为i从0开始遍历走到中点,j同理,从mid+1开始走到末尾为r
if (q[i] <= q[j]) {
// ↑: 用<=是因为稳定性
tmp[k++] = q[i++];
} else {
tmp[k++] = q[j++];
}
}
// 剩余的
while (i <= mid) {
// ↑:用<=是因为i从0开始遍历走到中点
tmp[k++] = q[i++];
}
while (j <= r) {
// ↑:j同理,从mid+1开始走到末尾为r
tmp[k++] = q[j++];
}
// copy tmp到q
for (i = l, j = 0; i <= r; i++, j++) {
// ↑:i代表从原始数组的l开始到r,故i=l && i<=r
// ↑:j代表将临时数组从0开始复制,故j=0
// 每次加一个,两个指针自增
q[i] = tmp[j];
}
}
}
本文由 ONE 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
如有版权疑问交流,请给我留言:oneisall8955@gmail.com
本文永久链接:http://liuzhicong.cn/index.php/study/alg-merge-sort_template_acwing787.html
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
如有版权疑问交流,请给我留言:oneisall8955@gmail.com
本文永久链接:http://liuzhicong.cn/index.php/study/alg-merge-sort_template_acwing787.html