1. package sort;
    3. import java.util.Arrays;
    4. import java.util.stream.Collectors;
    6. public class QuickSort {
    8.     public void solution(int[] arr){
    9.         int n = arr.length;
    11.         if(n<=1){
    12.             return;
    13.         }
    15.         quicksort(arr, 0, n-1);
    16.     }
    18.     public void quicksort(int[] arr, int low, int high){
    19.         if(low >= high){
    20.             return;
    21.         }
    22.         // 把数组分成2份，
    23.         // 左边的值比 arr[pivotIndex] 小
    24.         // 右边的值比 arr[pivotIndex] 大
    25.         int pivotIndex = partition(arr, low, high);
    27.         quicksort(arr, low, pivotIndex-1);
    28.         quicksort(arr, pivotIndex+1, high);
    30.     }
    32.     /**
    33.      * 算法思想：
    34.      * 在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边
    35.      * 下次，再对分组后对每一组，按同样对方式进行
    36.      */
    37.     public int partition(int[] arr, int low, int high){
    39.         int pivot = arr[low];
    41.         while (low < high){
    42.             // 从右往左，找出比 pivot 小的元素的下标
    43.             while (low < high && arr[high] >= pivot){
    44.                 high--;
    45.             }
    46.             // 将比pivot小的，交换到low的位置
    47.             arr[low] = arr[high];
    49.             // 从左往右，找出比 pivot 大的元素的下标
    50.             while (low < high && arr[low] <= pivot){
    51.                 low++;
    52.             }
    53.             arr[high] = arr[low];
    54.         }
    56.         arr[low] = pivot;
    58.         return low;
    60.     }
    62.     public static void main(String[] args) {
    63.         int []arr = {8,5,9,12,4,1,3};
    65.         QuickSort quickSort = new QuickSort();
    66.         quickSort.solution(arr);
    68.         System.out.println(Arrays.stream(arr).boxed().collect(Collectors.toList()));
    69.     }
    70. }