文
章
目
录
章
目
录
本文重点讲解Java实现归并排序经典代码和算法思路。
归并排序算法思想
归并排序(Merge-Sort):和快速排序一样,都是基于分而治之的算法思想,把待排序的序列分成更小的序列,再把已经有序的序列合并成一个有序序列。
归并排序先将待排序的数组不断拆分,直到拆分到区间里只剩下一个元素的时候。不能再拆分的时候。这个时候我们再想办法合并两个有序的数组,得到长度更长的有序数组。当前合并好的有序数组为下一轮得到更长的有序数组做好了准备。一层一层的合并回去,直到整个数组有序。
归并排序图解
策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。先分再合:
Java实现归并排序
/**
* 归并排序
* 分而治之(divide - conquer);每个递归过程涉及三个步骤
* 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
* 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
* 第三, 合并: 合并两个排好序的子序列,生成排序结果.
*/
public static int[] mergeSort(int[] a, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
//左右归并
merge(a, low, mid, high);
}
return a;
}
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for (int x = 0; x < temp.length; x++) {
a[x + low] = temp[x];
}
}
总结
以上就是Java实现归并排序经典代码和算法思路的全部内容,希望对你有帮助!