归并排序【简单易懂】

偏执的太偏执、 2024-03-23 14:14 62阅读 0赞

import java.util.Arrays;
    
    public class MergeSort {
        
    
        public static void merge(int[] arr, int[] tempArr, int left, int mid, int right) {
        
            int leftPos = left; // 标记左半区第一个未排序的元素
            int rightPos = mid + 1; // 标记右半区第一个未排序的元素
            int tempPos = left; // 临时数组元素的下标
    
            // 合并
            while (leftPos <= mid && rightPos <= right) {
        
                if (arr[leftPos] < arr[rightPos]) {
         // 左半区第一个剩余元素更小
                    tempArr[tempPos++] = arr[leftPos++];
                } else {
         // 右半区第一个剩余元素更小
                    tempArr[tempPos++] = arr[rightPos++];
                }
            }
    
            // 合并左半区剩余的元素
            while (leftPos <= mid) {
        
                tempArr[tempPos++] = arr[leftPos++];
            }
    
            // 合并右半区剩余的元素
            while (rightPos <= right) {
        
                tempArr[tempPos++] = arr[rightPos++];
            }
    
            // 把临时数组中合并后的元素复制回原来的数组
            for (int i = left; i <= right; i++) {
        
                arr[i] = tempArr[i];
            }
        }
    
        public static void divide(int[] arr, int[] tempArr, int left, int right) {
        
            if (left < right) {
        
                int mid = (left + right) / 2; // 找中间点
                divide(arr, tempArr, left, mid); // 递归划分左半区
                divide(arr, tempArr, mid + 1, right); // 递归划分右半区
                merge(arr, tempArr, left, mid, right); // 合并已经排序的部分
            }
        }
    
        public static void mergeSort(int[] arr) {
        
            int[] tempArr = new int[arr.length]; // 分配一个辅助数组
            divide(arr, tempArr, 0, arr.length - 1); // 调用实际的归并排序
        }
    
        public static void main(String[] args) {
        
            int[] array = {
        5, 3, 8, 6, 2};
            System.out.println("Before sorting: " + Arrays.toString(array));
            mergeSort(array);
            System.out.println("After sorting: " + Arrays.toString(array));
        }
    }