华为|java模拟归并排序merge sort 华为

【华为|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[
arrint lowint high){
if (low<high){
//当low=high即范围内只有一个数的时候不执行直接结束迭代两个数及以上才需要排序
int mid = (high+low)/2;
sort(arrlowmid);
sort(arrmid+1high);
//将当前范围分割成左右两部分分别进行排序这里会一层一层迭代直到子范围内只有一个数的时候结束迭代然后返回上一层依次进行后续运算
//最下层两个子范围都是一个数结束迭代回到上一层往下执行运算将两个子范围排序执行完就得到了范围=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 = {7824635119322;
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