题解 | 【模板】排序

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int index = 0;
        int[] nums = new int[n];
        while(in.hasNextInt()){
            nums[index] = in.nextInt();
            index++;
        }
        // mergeSort(nums);
        quickSort(nums, 0, n - 1);
        
        printRes(nums);
    }
    // 结果输出
    public static void printRes(int[] arr){
        for(int x : arr){
            System.out.print(x + " ");
        }
    }

    // 快速排序
    public static void quickSort(int[] arr, int low, int high){
        // 递归终止条件：当子数组长度小于等于1时
        if(low < high){
            int pi = partition(arr, low, high);
            // 递归排序基准元素左边的子数组
            quickSort(arr, low, pi - 1);
            // 递归排序基准元素右边的子数组
            quickSort(arr, pi + 1, high);
        }
    }
    public static int partition(int[] arr, int low, int high){
        // 选择一个元素作为基准
        int pivot = arr[high];
        int i = (low - 1);

        // 遍历数组，将小于基准的元素放到左边区域
        for(int j = low; j < high; j++){
            // 如果当前元素小于或等于基准
            if(arr[j] < pivot){
                i++;
                // 交换arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准元素放到正确的位置（左边都小于它，右边都大于它）
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // 返回基准元素的索引
        return i + 1;
    }
    // ———————— 快速排序 ————————

    // 归并排序
    public static void mergeSort(int[] arr){
        if(arr.length <= 1){
            return;
        }
        // 将数组分成两半
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr,0,mid);
        int[] right = Arrays.copyOfRange(arr,mid,arr.length);
        mergeSort(left);
        mergeSort(right);

        // 合并已排序的两半
        merge(arr, left, right);
    }

    // 合并两个已排序的数组到结果数组中
    public static void merge(int[] result, int[] left, int[] right){
        int i = 0; // 左数组的索引
        int j = 0; // 右数组的索引
        int k = 0; // 结果数组的索引
        while(i < left.length && j < right.length){
            if(left[i] <= right[j]){
                result[k++] = left[i++];
            }else{
                result[k++] = right[j++];
            }
        }
        while(i < left.length){
            result[k++] = left[i++];
        }
        while(j < right.length){
            result[k++] = right[j++];
        }
    }
    //———————— 归并排序 ——————————
}