快速排序

定义

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法

算法步骤

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

排序过程

复杂度

平均时间复杂度
最坏时间复杂度
最优时间复杂度
空间复杂度	根据实现的方式不同而不同
最佳解	有时是
排序方式	in-place
稳定性	不稳定

Java代码

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {65461, 34, 868, 4, 5, 2, 3, 99, 5345,3, 34, 2,6564, 434};
        System.out.println(Arrays.toString(arr));
        new QuickSort().quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public void quickSort(int[] arr,int left,int right) {
        // 递归边界
        if (left < right) {
            // 挑选基准值索引，已就位元素
            int pivotIndex = partition(arr, left, right);
            // 分割 递归排序子序列
            quickSort(arr,left,pivotIndex-1);
            quickSort(arr,pivotIndex+1,right);
        }
    }
    private int partition(int[] arr, int left, int right) {
        // 基准点
        int pivotValue = arr[left];
        while (left < right) {
            // 大于等于基准值的都位于其右边   等于的位于那边都可以
            while (left < right && pivotValue <= arr[right]) {
                right--;
            }
            if (left < right) {
                arr[left] = arr[right];
            }
            // 小于等于基准值的都位于其右边
            while (left < right && arr[left] <= pivotValue) {
                left++;
            }
            if (left < right) {
                arr[right] = arr[left];
            }
        }
        // 基准值就位
        arr[left] = pivotValue;
        // 返回基准值索引
        return left;
    }
}