QuickSort & MergeSort

QuickSort

1. 确定分界点 q[l]、q[r]、q[(l + r) / 2]或随机
2. 🌟调整区间，使得分界点左边均<=分界点，右边均>=分界点
3. 递归处理左右两段

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] q = new int[n];
        for(int i = 0; i < n; ++i) {
            q[i] = sc.nextInt();
        }
        quickSort(q, 0, n - 1);
        for(int i = 0; i < n; ++i) {
            System.out.printf("%d ",q[i]);
        }
    }
    
    public static void quickSort(int[] q, int l, int r) {
        if(l >= r) return;
        int x = q[l + r >> 1], i = l - 1, j = r + 1;
        while(i < j) {
            do i++; while(q[i] < x);
            do j--; while(q[j] > x);
            if(i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }
}

MergeSort

分治思想

1. 确定分界点mid (l + r) / 2
2. 将数组分为两块：left部分和right部分，递归排序left和right
3. 🌟归并，合二为一

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; ++i) {
            nums[i] = sc.nextInt();
        }
        mergeSort(nums, 0, n - 1);
        for(int i = 0; i < n; ++i) {
            System.out.print(nums[i] + " ");
        }
    }
    
    public static void mergeSort(int[] nums, int l, int r) {
        if(l >= r) return;
        int mid = l + r >> 1;
        int[] tmp = new int[r - l + 1];
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r) {
            if(nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= r) tmp[k++] = nums[j++];
        for(i = l, j = 0; i <= r; ++i, ++j) {
            nums[i] = tmp[j];
        }
    }
}