1. public static void main(String[] args) {
    3.     int[] arr = {1, 3, 2, 6, 9, 8, 4};
    4.     quickSort(arr, 0, arr.length - 1);
    5.     for (int i : arr) {
    6.         System.out.print(i + " ");
    7.     }
    8. }
    10. public static void quickSort(int[] arr, int begin, int end) {
    11.     // 中断条件，如果不合法或只有一个元素直接返回
    12.     if (begin >= end) return;
    13.     // mid位置之前的元素都小于它，之后的元素都大于它
    14.     int mid = partition(arr, begin, end);
    15.     // 继续递归前半部分
    16.     quickSort(arr, begin, mid - 1);
    17.     // 继续递归后半部分
    18.     quickSort(arr, mid + 1, end);
    19. }
    21. public static int partition(int[] arr, int begin, int end) {
    22.     // 用来记录需要交换的位置
    23.     int cur = begin;
    25.     // 把所有小于end的元素都和cur位置元素交换
    26.     for (int i = begin; i < end; i++) {
    27.         if (arr[i] < arr[end]) {
    28.             int tmp = arr[i];
    29.             arr[i] = arr[cur];
    30.             arr[cur] = arr[i];
    31.             cur++;
    32.         }
    33.     }
    35.     // 最后把end元素和cur交换，这样end之前的元素都小于它，之后都大于它
    36.     int tmp = arr[cur];
    37.     arr[cur] = arr[end];
    38.     arr[end] = tmp;
    39.     return cur;
    40. }