思路图image.png 思路解析

    • 采用分治法
    1. 分
    • 将数组 每次划分成两组
    • 直到 只剩下一个
    1. 治
    • 取得两个组进行合并
    • 获取两个组的第一个进行比较
    • 将小的先放到新的组里面 ```java /**
      • 归并排序：时间复杂度为olnN */

    public class mergeSort { public static void merge_sort(int[] arr, int l, int r){ //如果 l >= r 数据不合法，或者就一个数据，本身就有序 if (l >= r) return; //开始进行排序，排序arr中的所欲元素，可以用分治法，先排序数组中，左边的数据，使之有序，右边的数据，使之有序 int mid = (l + r)/2; merge_sort(arr, l, mid); //先使之左边的有序 merge_sort(arr, mid+1, r); //再使之右边的有序 merge(arr, l, r, mid); //左边和右边的都有序了，把左边和右边有序的数据变成整体有序的数据 }

    1. private static void merge(int[] arr, int l, int r, int mid) {
    2.     //开辟一个辅助空间，用来存取整体有序的数据
    3.     int[] newArr = new int[r-l+1];
    4.     int n = 0;
    5.     int p1 = l;
    6.     int p2 = mid + 1;
    7.     while(p1 <= mid && p2 <= r){        //l指向左边的数据开始位置，j指向右边的数据的开始位置,并且不越界的情况下
    8.         if (arr[p1] <= arr[p2]) {
    9.             //左边的比较小
    10.             newArr[n++] = arr[p1++]; //把l位置上的数据放到新的数组中
    11.         }else{
    12.             newArr[n++] = arr[p2++];
    13.         }
    14.     }
    15.     //当条件不满足的时候
    16.     while(p1 <= mid){
    17.         newArr[n++] = arr[p1++];
    18.     }
    19.     while(p2 <= r){
    20.         newArr[n++] = arr[p2++];
    21.     }
    22.     for (int i = 0; i < newArr.length; i++){
    23.         arr[l+i] = newArr[i];
    24.     }
    25. }
    27. public static void main(String[] args) {
    28.     int[] arr = {24,1,5,4,7,2,9,10};
    29.     //例如，想要使arr数组中1~8中有序,那么调用函数
    30.     merge_sort(arr, 0, 7);
    31.     for(int i = 0; i < arr.length; i++){
    32.         System.out.println(arr[i]);
    33.     }
    34. }

    }

    ```