快速排序

平均时间复杂度：O(nlogn)
最坏时间复杂度：O(n^2) （极少情况下会出现）
最优时间复杂度：O(nlogn)

步骤（from wiki）：

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

优点：

不消耗额外的空间

缺点：

不够稳定

为何不稳定？

• 情况1:如果挑选当基数最终填入后如果其位置靠近左右两端而不是序列中间，那么树就会失去平衡

image.png

• 情况2:如果序列近乎有序，当直接使用第一个元素或最后一个元素（下图中使用第一个元素），就有可能导致整颗树不平衡，从而无法保证树高为logN。（针对这种现象有一些优化方式：三数取中法、随机交换法）

image.png

代码思路：

1、partition（核心）

从序列 a 中挑选出一个基数pivot（随机抽取），枚举序列中其他元素 i 与pivot指向元素进行比较，如果 a[i] < a[pivot] ，则将a[i]往前挪（与示例中counter指针元素进行交换），直至枚举完所有元素后，将pivot与count指向的元素进行交换，此时counter指针即为当前序列中界定左小右大的索引。

图解：

排序前（假设pivot抽取到最后一个元素）：
(i和counter)    pivot
↓                 ↓
3  2  5  8  1  9  4

以基数为准，进行**左小右大**的站队（小的往前站，大的不动）
2 3 5 8 1 9 4 // 枚举到i=0,由于2<4,发生第一次swap后, i=1, counter=1
2 3 5 8 1 9 4 // 枚举到i=1,由于3<4,发生第二次swap后, i=2, counter=2（此处相当于没有交换，体现了快排的不稳定，可优化）
2 3 1 8 5 9 4 // 枚举到i=4,由于1<4，发生第三次swap后, i=5, counter=3，此时完成了站队。

将pivot与counter位置上的元素进行swap后，最终得到下面序列，此时counter即为界定序列**左小右大**的索引：
2 3 1 4 5 9 8 

2、分割&递归调用quickSort

将partition函数返回的pivot作为边界，对其左右子序列进行分割，再分别进行递归调用，完成排序。

代码示例

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {1,9,4,2,3,6,5};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private void quickSort(int[] nums, int begin, int end) {
        if (begin >= end) return;
        int pivot = randomPartition(nums, begin, end);
        quickSort(nums, begin, pivot - 1);
        quickSort(nums, pivot + 1, end);
    }

    private int randomPartition(int[] nums, int begin, int end) {
        // 从中随机选一个索引，作为pivot（增加随机性可提高效率）
        int randomIdx = new Random().nextInt(end - begin + 1) + begin;
        swap(nums, end, randomIdx);
        return partition(nums, begin, end);
    }

    private int partition(int[] nums, int begin, int end) {
        int pivot = nums[end];
        int counter = begin;
        for (int i = begin; i < end; i++) {
            if (nums[i] <= pivot) {
                swap(nums, counter++, i);
            }
        }
        swap(nums, counter, end);
        return counter;
    }

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