原理：将原序列划分为有序的n个序列，然后利用归并算法进行合并，合并之后即为有序序列。
要点：分治，归并
private static void sortMerge(int[] array, int childLength) {
System.out.println("分割数组，并对各个子数组排序：");
//将原数组array分割线成长度为childLength的多个子数组
int childArrayLength = array.length / childLength + (array.length % childLength == 0 ? 0 : 1);
//记录各个子数组的起始位置和归并标记位 [start, end, mergeIndex]
int[][] indexStartEnd = new int[childArrayLength][3];
int index = 0;
int start = 0;
while (start < array.length) {
int end = start + childLength - 1;
if (end > array.length - 1) {
end = array.length - 1;
}
//对子数组进行排序
sortBubble(array, start, end);
printArray(String.format(Locale.getDefault(), "start = %2d , end = %2d : ", start, end), array);
indexStartEnd[index] = new int[]{start, end, start};
start = end + 1;
index++;
}
System.out.println("归并各个子数组：");
int[] result = new int[array.length];
for (int i = 0; i < result.length; i++) {
boolean isMinSetValue = false;
int minIndex = 0;
int min = 0;
int minPosition = 0;
for (index = 0; index < indexStartEnd.length; index++) {
if (indexStartEnd[index][2] <= indexStartEnd[index][1]) {
if (!isMinSetValue || array[indexStartEnd[index][2]] < min) {
minPosition = indexStartEnd[index][2];
min = array[minPosition];
minIndex = index;
isMinSetValue = true;
}
}
}
indexStartEnd[minIndex][2] = indexStartEnd[minIndex][2] + 1;
result[i] = array[minPosition];
printArray(String.format(Locale.getDefault(), "min = %2d , minPosition = %2d : ", min, minPosition), result);
}
}
将数组array分割成长度为6的多个子数组，运行结果：
原数组： 34 42 13 56 45 22 8 50 73 5 43 84 34 81 73 27 44 59 26 91
归并排序：
分割数组，并对各个子数组排序：
第 0 趟 : 34 13 42 45 56 22 8 50 73 5 43 84 34 81 73 27 44 59 26 91
第 1 趟 : 13 34 42 45 56 22 8 50 73 5 43 84 34 81 73 27 44 59 26 91
第 2 趟 : 13 34 42 45 56 22 8 50 73 5 43 84 34 81 73 27 44 59 26 91
start = 0 , end = 5 : 13 34 42 45 56 22 8 50 73 5 43 84 34 81 73 27 44 59 26 91
第 6 趟 : 13 34 42 45 56 22 8 50 5 43 73 84 34 81 73 27 44 59 26 91
第 7 趟 : 13 34 42 45 56 22 8 5 43 50 73 84 34 81 73 27 44 59 26 91
第 8 趟 : 13 34 42 45 56 22 5 8 43 50 73 84 34 81 73 27 44 59 26 91
第 9 趟 : 13 34 42 45 56 22 5 8 43 50 73 84 34 81 73 27 44 59 26 91
start = 6 , end = 11 : 13 34 42 45 56 22 5 8 43 50 73 84 34 81 73 27 44 59 26 91
第 12 趟 : 13 34 42 45 56 22 5 8 43 50 73 84 34 73 27 44 81 59 26 91
第 13 趟 : 13 34 42 45 56 22 5 8 43 50 73 84 34 27 44 73 81 59 26 91
第 14 趟 : 13 34 42 45 56 22 5 8 43 50 73 84 27 34 44 73 81 59 26 91
第 15 趟 : 13 34 42 45 56 22 5 8 43 50 73 84 27 34 44 73 81 59 26 91
start = 12 , end = 17 : 13 34 42 45 56 22 5 8 43 50 73 84 27 34 44 73 81 59 26 91
第 18 趟 : 13 34 42 45 56 22 5 8 43 50 73 84 27 34 44 73 81 59 26 91
start = 18 , end = 19 : 13 34 42 45 56 22 5 8 43 50 73 84 27 34 44 73 81 59 26 91
归并各个子数组：
min = 5 , minPosition = 6 : 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
min = 8 , minPosition = 7 : 5 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
min = 13 , minPosition = 0 : 5 8 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
min = 26 , minPosition = 18 : 5 8 13 26 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
min = 27 , minPosition = 12 : 5 8 13 26 27 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
min = 34 , minPosition = 1 : 5 8 13 26 27 34 0 0 0 0 0 0 0 0 0 0 0 0 0 0
min = 34 , minPosition = 13 : 5 8 13 26 27 34 34 0 0 0 0 0 0 0 0 0 0 0 0 0
min = 42 , minPosition = 2 : 5 8 13 26 27 34 34 42 0 0 0 0 0 0 0 0 0 0 0 0
min = 43 , minPosition = 8 : 5 8 13 26 27 34 34 42 43 0 0 0 0 0 0 0 0 0 0 0
min = 44 , minPosition = 14 : 5 8 13 26 27 34 34 42 43 44 0 0 0 0 0 0 0 0 0 0
min = 45 , minPosition = 3 : 5 8 13 26 27 34 34 42 43 44 45 0 0 0 0 0 0 0 0 0
min = 50 , minPosition = 9 : 5 8 13 26 27 34 34 42 43 44 45 50 0 0 0 0 0 0 0 0
min = 56 , minPosition = 4 : 5 8 13 26 27 34 34 42 43 44 45 50 56 0 0 0 0 0 0 0
min = 22 , minPosition = 5 : 5 8 13 26 27 34 34 42 43 44 45 50 56 22 0 0 0 0 0 0
min = 73 , minPosition = 10 : 5 8 13 26 27 34 34 42 43 44 45 50 56 22 73 0 0 0 0 0
min = 73 , minPosition = 15 : 5 8 13 26 27 34 34 42 43 44 45 50 56 22 73 73 0 0 0 0
min = 81 , minPosition = 16 : 5 8 13 26 27 34 34 42 43 44 45 50 56 22 73 73 81 0 0 0
min = 59 , minPosition = 17 : 5 8 13 26 27 34 34 42 43 44 45 50 56 22 73 73 81 59 0 0
min = 84 , minPosition = 11 : 5 8 13 26 27 34 34 42 43 44 45 50 56 22 73 73 81 59 84 0
min = 91 , minPosition = 19 : 5 8 13 26 27 34 34 42 43 44 45 50 56 22 73 73 81 59 84 91
网友评论