快速排序 Quicksort 是对冒泡排序的一种改进
冒泡排序基础上的递归分治法
通过多次比较和交换来实现排序
非稳定 ，相同值的相对位置在排序结束后会改变

快速排序 最坏  O(n²) ，平均 O(nlogn)
且 O(nlogn) 记号中隐含的常数因子很小，比归并排序小很多
对绝大多数顺序性较弱的随机数列而言，快速排序优于归并排序

分治 Divide and conquer 和  递归 

算法步骤
从数列中挑出一个元素，称为 基准 pivot 
重新排序数列，小于基准的放左边，大于基准的放右边（相同可以放任一边） ，这个称为分区（partition）操作
递归地（recursive）排序 左右子数列


int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 };
left=0,right=8,partitionIndex=2
1 2 3 9 4 8 7 5 6 
left=0,right=1,partitionIndex=0
1 2 3 9 4 8 7 5 6 
left=3,right=8,partitionIndex=8
1 2 3 6 4 8 7 5 9 
left=3,right=7,partitionIndex=5
1 2 3 5 4 6 7 8 9 
left=3,right=4,partitionIndex=4
1 2 3 4 5 6 7 8 9 
left=6,right=7,partitionIndex=6
1 2 3 4 5 6 7 8 9 



public class QuickSort {
    public static void main(String[] args) throws Exception {
        int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 };
        quickSort(arr);
        System.out.println();
        printArr(arr);
        System.out.println();

        int[] arr2 = { 3 };
        quickSort(arr2);
        System.out.println();

        int[] arr3 = { 3, 2 };
        quickSort(arr3);
        System.out.println();
    }

    private static void quickSort(int[] arr) {
        final int N = arr.length - 1;
        quickSort(arr, 0, N);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            // for debug
            System.out.println("left=" + left + ",right=" + right + ",partitionIndex=" + partitionIndex);
            printArr(arr);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        // 设定基准值 pivot
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private static void printArr(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}



https://gitee.com/dyyx/hellocode/blob/master/src/algo/sort/QuickSort.java


 归并排序与快速排序