java模拟归并排序merge sort
/**
* 模拟归并排序merge sort
* 思路是将一个数组分成两半 每一半再继续分半 递归的拆分直至每个范围内只有一个元素 从最小的单元开始排序、返回上一层变为更大的单元排序再返回上一层变成更大的单元 最后完成整个数组的排序
*/
public class TestMergeSort {
public static void sort(int[] arr){
//先重载一个给整个数组排序的方法 不用手动输入low=0 high=length-1 方便使用更易懂
sort(arr, 0, arr.length-1);
//最高位是length-1
}
public static void sort(int[] arr,int low,int high){
if (low<high){
//当low=high即范围内只有一个数的时候不执行直接结束迭代 两个数及以上才需要排序
int mid = (high+low)/2;
sort(arr,low,mid);
sort(arr,mid+1,high);
//将当前范围分割成左右两部分 分别进行排序 这里会一层一层迭代 直到子范围内只有一个数的时候结束迭代 然后返回上一层依次进行后续运算
//最下层两个子范围都是一个数 结束迭代 回到上一层往下执行运算 将两个子范围排序 执行完就得到了范围=2的有序集合
// 执行完结束 返回上一层 用范围=2的有序集合和另外一个有序集合排序 执行完再返回上一层 层层执行、返回 直到最高层
//最高层是数组的整个左半边和整个右半边 两个半边内部都是排好序的 再将这两部分执行下面的运算
int[] b = new int[high-low+1];
//new一个数组 长度和现在要排序的范围的长度一致
int i = 0;
int left = low;
//左半边范围的首位 用于左边的索引
int right = mid+1;
//右半边范围的首位 用于右边的索引
while (left<mid+1&&right<high+1){
b[i++] = (arr[left]<arr[right])?arr[left++]:arr[right++];
//因为左半边范围和右半边范围都是从小到大排序好的 所以每次都比较两个范围内最左侧的那个元素 哪个小就放入b[i]中并将这边的索引+1
//等号左侧也可以++ 条件运算符内也可以++
//当左边或者右边取完了即left<mid+1&&right<high+1 为false时结束循环 因为每次循环只会取左边或者右边一位数 所以不可能两侧同时取完 还没取出的部分要继续取
}
while (left<mid+1){
//如果右边取完了 左边没取完 这时b[]中所有存在的元素都比没取完的小 没取完的又是有序的 所以遍历剩余的依次存到b中
b[i++] = arr[left++];
}
while (right<high+1){
//如果左边取完了 右边没取完
b[i++] = arr[right++];
}
//到这时左右两边都取完了 b也填满了
for (i = 0;i<b.length;i++){
arr[low++] = b[i];
//将b遍历 存回arr的范围中 即完成对当前范围的排序
}
}
}
public static void main(String[] args) {
int[] a = {7,82,4,6,35,1,19,32,2};
sort(a);
System.out.println(Arrays.toString(a));
//结果[1, 2, 4, 6, 7, 19, 32, 35, 82]
/*
第一步 7，82，4，6，35 1，19，32，2
第二步 7，82，4 6，35 1，19，32，2
第三步 7，82 4 6，35 1，19，32，2
第四步 7 82 4 6，35 1，19，32，2
第五步 7，82 4 6，35 1，19，32，2
第六步 4，7，82 6，35 1，19，32，2
第七步 4，7，82 6 35 1，19，32，2
第八步 4，7，82 6，35 1，19，32，2
第九步 4，6，7，35，82 1，19，32，2
第十步 4，6，7，35，82 1，19 32，2
十一步 4，6，7，35，82 1 19 32，2
十二步 4，6，7，35，82 1，19 32，2
十三步 4，6，7，35，82 1，19 32 2
十四步 4，6，7，35，82 1，19 2，32
十五步 4，6，7，35，82 1，2，19，32
十六步 1，2，4，6，7，19，32，35，82
*/
}
}
