题目
归并排序也是一种基于分治法的排序算法。为了排序长度为n的数组,需要先排序两个长度为n/2的子数组,然后合并这两个排序的子数组,于是整个数组也就排序完毕。
分析
归并排序可以用迭代代码实现。例如,输入一个长度为8的数组[4,1,5,6,2,7,8,3],
- 可以先合并相邻的长度为1的子数组得到4个排序的长度为2的子数组。
- 然后合并相邻的长度为2的子数组得到2个排序的长度为4的子数组
- 最后合并相邻的长度为4的子数组,此时整个数组排序完毕
解:迭代
public class Test {
public static void main(String[] args) {
int[] nums = {
4, 1, 5, 6, 2, 7, 8, 3};
int[] result = sortArray(nums);
for (int item : result) {
System.out.println(item);
}
}
public static int[] sortArray(int[] nums) {
int length = nums.length;
int[] src = nums;
int[] dst = new int[length];
for (int seg = 1; seg < length; seg += seg) {
// 合并分段的长度
for (int start = 0; start < length; start += seg * 2) {
int mid = Math.min(start + seg, length);
// i,j两个游标在遍历的时候,j可能先到达end,因为end可能取的是length的值
int end = Math.min(start + seg * 2, length);
int i = start, j = mid, k = start;
while (i < mid || j < end) {
if (j == end || (i < mid && src[i] < src[j])) {
dst[k++] = src[i++];
}
else {
dst[k++] = src[j++];
}
}
}
int[] temp = src;
src = dst;
dst = temp;
}
return src;
}
}
解:递归
public class Test {
public static void main(String[] args) {
int[] nums = {
4, 1, 5, 6, 2, 7, 8, 3};
int[] result = sortArray(nums);
for (int item : result) {
System.out.println(item);
}
}
public static int[] sortArray(int[] nums) {
int[] dst = new int[nums.length];
dst = Arrays.copyOf(nums, nums.length);
mergeSort(nums, dst, 0, nums.length);
return dst;
}
private static void mergeSort(int[] src, int[] dst, int start, int end) {
if (start + 1 >= end) {
return;
}
int mid = (start + end) / 2;
mergeSort(dst, src, start, mid);// 注意src和dst反过来了,两个数组来回颠倒
mergeSort(dst, src, mid, end);
int i = start, j = mid, k = start;
while (i < mid || j < end) {
if (j == end || (i < mid && src[i] < src[j])) {
dst[k++] = src[i++];
}
else {
dst[k++] = src[j++];
}
}
}
}