|
归并排序的原则为分而治之，主要思想为一下几个步骤
1.首先什么是“分”？就是讲每个数据集分成一个独立的小单元。
2.再次，将分割后的独立的小单元进行排序。
3.最后，将分割排序后的小单元进行两两合并，组成新的有序数据集。
如下图所示
核心代码如下：
main方法的入口，主要做两个操作，创建排序好的存放数组，和限定排序的范围
public static void mergeSort(int arr[]) {
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
Arrays.stream(temp).forEach(System.out::println);
}
进行递归操作，目的是将数据集分成独立的小单元，类似树的遍历（左边分割，右边分割，分割不了退回根节点，然后进行俩俩数据集合并）
public static void mergeSort(int arr[], int start, int end, int temp[]) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(arr, start, mid, temp);
mergeSort(arr, mid + 1, end, temp);
merge(arr, start, mid, end, temp);
}
}
核心操作主要为3个步骤，第一步进行分割时候，左右数据集比较。比较完成之后，根据大小依次放入新数聚集中（一般为数组），查看左右数据集是否都进行放入存放（因为左右数据集比较时，可能存在某侧的数据集已经排序完毕，但是另一侧却存在数据未进行操作）接着需要查看两侧数据集是否都进行数据操作。最后更新之前数据的数据顺序。
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int leftIndex = left;
int rightIndex = mid + 1;
int tempIndex = 0;
// 左右比较第一步骤
while (leftIndex <= mid && rightIndex <= right) {
if (arr[leftIndex] >= arr[rightIndex]) {
temp[tempIndex++] = arr[rightIndex++];
} else {
temp[tempIndex++] = arr[leftIndex++];
}
}
//补充数据，第二步骤
while(leftIndex<= mid ){
temp[tempIndex++] = arr[leftIndex++];
}
while (rightIndex<=right){
temp[tempIndex++] = arr[rightIndex++];
}
tempIndex = 0;
//将temp中的元素全部拷贝到原数组中，第三步骤
while (left <= right) {
arr[left++] = temp[tempIndex++];
}
}
| 
转播
