/**
* 归并排序：使用递归，二分拆分，所有拆分的排好序，最后数组也就排好序了NlogN
* 具体操作：将数组递归拆分成两份，将两边排好序的数组进行比较，由小到大放入临时数组
*/
public class MergeTest {
public static void main(String[] args) {
int[] arr = {3,1,6,3,8,3,5,9,4,67,2,5,7,2,6,3,5};
mergeSort(arr);
for (int i : arr) {
System.out.print(i+",");
}
}
private static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
private static void process(int[] arr, int l, int r) {
if (l == r) {
return;
}
int m = l + ((r - l) >> 1);
// 1、左边部分排序
process(arr, l, m);
// 2、右边部分排序
process(arr, m + 1, r);
// 3、合并左右两边排好序的数组
merge(arr, l, m, r);
}
private static void merge(int[] arr, int l, int m, int r) {
// 创建一个临时数组，用来存储当前范围的数组，并进行排序，然后写入原数组
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
// 1、2个数组均排好序了
// 2、两边从最开始进行比较，小的入临时数组
// 3、当其中一个数组遍历完，另一个数组剩下的数均是排好序且更大的数字，直接按顺序放入数组即可
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
System.arraycopy(help, 0, arr, l, help.length);
}
}
归并排序
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 归并排序是建立在归并操作上的一种有效、稳定的排序算法，该算法采用非常经典的分治法（分治法可以通俗的解释为:把一片领...
- 数据结构和算法学习汇总[https://www.jianshu.com/p/72b20d1e06e6] 本文主要讲...
- 1.快速排序 快速排序每趟选择一个基准元素，用基准元素将序列划分成两部分，所有比基准值小的元素摆放在基准前面，所有...
