百度：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
我的理解：
首先将一组无序的数组按照长度进行等分拆分，直到分成只有一个数字，然后再进行相邻之间的比较，从而再合并起来。是一种先分后和的做法，高逼格说法为分治法（分治法通常要运用递归方法）。
脑补例子：
原数组 [5,1,6,7,1,6,8,2,10]
使用递归进行拆分后结果 5 1 6 7 1 6 8 2 10
第一次归并后 {1,5}（+1）{6,7} {1,6}（+1）{2,8}（+1）{10} 共比较3次
第二次归并后 {1,5,6,7} (+2) {1,2,6,8} (+3) {10} 共比较5次
第三次归并 {1,1,2,5,6,6,7,8} (+6) {10} 共比较6次
第四次归并 {1,1,2,5,6,6,7,8,10} {+8} 共比较8次
自己写的数组，死都要排完......
实现代码（java）：
package com.company;
import java.util.Arrays;public class Main {
public static void main(String[] args) {
int[] arr = new int[]{1, 4, 6, 83, 5, 7, 2, 10};
// Main.merge(arr,0,(arr.length-1)/2,arr.length-1);
Main.mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
//归并排序
private static void mergeSort(int[] arr, int low, int hight) {
int middle = (hight + low) / 2;
//结束条件
if (low < hight) {
//处理左边
mergeSort(arr, low, middle);
//处理右边
mergeSort(arr, middle + 1, hight);
//归并
merge(arr, low, middle, hight);
}
}
public static void merge(int[] arr, int low, int midden, int hight) {
//用来存储归并后的临时数组
int[] temp = new int[hight - low + 1];
//记录第一个数组中需要遍历的下标
int i = low;
//记录第二个数组中需要遍历的下标
int j = midden + 1;
//用于记录临时数组中存放的下标
int index = 0;
//遍历两组数组取出最小数字，放入临时数组
while (i <= midden && j <= hight) {
//第一组数组的数字比第二组数组小
if (arr[i] <= arr[j]) {
temp[index] = arr[i];
i++;
}
//反之
else {
temp[index] = arr[j];
j++;
}
index++;
}
//当第一组数组有剩下数时，再把剩下的全部添加进临时数组
while (i <= midden) {
temp[index] = arr[i];
i++;
index++;
}
//当第二组数组有剩下数时，再把剩下的全部添加进临时数组
while (j <= hight) {
temp[index] = arr[j];
j++;
index++;
}
//把临时数组重新放到原数组中
for (int k = 0; k < temp.length; k++) {
arr[k + low] = temp[k];
}
}
}
网友评论