归并排序(Java)

思想:

基本思想是使用递归将数组不断分成两半，直到分成的小组都只剩下一个元素为止，随后分别开始排序，将排序好的数组合并在一起。

归并排序使用了分治（Divide and Conquer）的思想。包括以下三个步骤：

1. 划分（Divide）：将原问题分解成几个规模较小的相同问题。
2. 解决（Conquer）：递归求解这些子问题。
3. 合并（Combine）：将子问题的解合并为原问题的解。

合并过程:

时间复杂度

归并排序的时间复杂度是 O(n log n)，因为分解过程将数组分成 log n 层，合并过程每层需要 O(n) 的时间复杂度。

空间复杂度

归并排序的空间复杂度是 O(n)，因为需要额外的空间来存储合并的临时数组。

归并排序是一种稳定的排序算法，因为合并操作不会改变相同元素的相对顺序。然而，它需要额外的内存空间，这在内存资源有限的情况下可能是一个缺点。

代码实现:

public class MergeSort {
    public static void main(String[] args) {
        //创建要排序的数组
        int nums[] = {9,7,18,8,2,5,16,10,12,6};
        divideSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    //递归数组
    public static void divideSort(int[] arr, int left, int right){
        if(left < right){
            int mid = (left + right) >>> 1;
            divideSort(arr,left,mid);
            divideSort(arr,mid+1,right);
            MergeSort(arr,left,mid,right);
        }
    }

    //排序
    public static void MergeSort(int[] arr, int left, int mid, int right){
        //合并数组
        int i = left;
        int j = mid + 1;
        int k = 0;
        int[] temp = new int[right - left + 1];
        while(i <= mid && j <= right){
            if(arr[i] < arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
        }

        //合并剩余元素
        while(i <= mid){
            temp[k++] = arr[i++];
        }
        while(j <= right){
            temp[k++] = arr[j++];
        }
        // 将合并后的数组复制回原数组
        for (i = left, k = 0; i <= right; i++, k++) {
            arr[i] = temp[k];
        }
    }
}

运行结果：