【常见面试算法】快速排序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        
        quickSort(nums, 0, n - 1);
        
        for (int i = 0; i < n; i++) {
            System.out.print(nums[i] + " ");
        }
    }
    
    static void quickSort(int[] nums,int l, int r) {
        if (l >= r) return;
        
        int less = l - 1;
        int cur = l;
        int more = r;
        int pivot = nums[r];
        
        while (cur != more) {
            if (nums[cur] < pivot) {
                swap(nums,++less,cur++);
            } else if(nums[cur] > pivot) {
                swap(nums,--more,cur);
            } else {
                cur++;
            }
        } 
        swap(nums, r, more);
        quickSort(nums,l,less);
        quickSort(nums,more + 1,r);
    }
    
    static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}