【算法】标准排序之快排（ Quicksort ）

1.简介

快速排序是很经典的分治算法，大概的算法思路就是将大数组划分partition为两个子数组，左数组整块小于右数组（max(left)<min(right)），然后递归处理左子数组和右子数组，如下图所示：

2.算法实现

2.1 quickSort递归

Divide 阶段（partition）： 挑一个数当作pivot基准， 把数组分割partition成左右两堆， 使左半小于pivot，右半大于pivot，基准数字置于中间。 Conquer 阶段：左右两堆资料各自从事Quicksort 。 Combine 阶段：不做任何事。

3.2 划分partition

1.两个指针分别迭代，i for [left,right-1]， [left,i]部分永远是划分好的两部分 [left,small]块小于pivot，[small,i]不小于pivot 2.当[left,right-1]划分好，将pivot插入到正确的位置（small+1）， small++，交换small位置和right，划分完成   不变式  [left,small]任意元素小于pivot （除了最终small是pivot本身）

public class QuickSort {public void sort(int[] nums) {int left = 0, right = nums.length-1;if (left<right) {quickSort(nums, left, right);}}//[left, right] 闭区间public void quickSort(int[] a, int left, int right) {int index = partition(a, left, right);     // 划分if (left < index -1) { quickSort(a, left, index-1); // 左半部分}if (index < right) {quickSort(a, index+1, right); // 右半部分}}int partition(int[] a, int left, int right) {int pindex = rand.nextInt(right - left + 1) + left; // 随机找pivotswap(a, pindex, right); //交换到最后int small = left - 1;//small-left+1是小于pivot值的个数，指向当前遍历到的最后一个最小值for (int i=left;i<right;i++) {if (a[i] < a[right]) {small++;if (i!=small) {swap(a, i, small);}}}small ++;swap(a, small, right);return small;}void swap(int[] nums, int i,int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public static void main(String[] args) {
//        int[] nums = {1,3,2,4,2,5,2};
//        int[] nums = {};int[] nums = {1};new QuickSort().sort(nums);System.out.println(Arrays.toString(nums));}}

第二种划分方法，从left、right两端向中间靠拢

    int partition(int[] a, int left, int right) {int pivot = a[(left+right)/2]; //基准点 中位数while (left <= right) {while (a[left]<pivot) left++; //一直找到左边大于等于基准的值while (a[right]>pivot) right--; //从右向左 找到右边小于等于基准的值if (left<=right) {swap(a, left, right); // 交换位置left++;right--;}}return left;}

拓展：用partition方法找到中位数

3.算法分析

时间复杂度：平均O(nlogn) 最差O(n2)

空间复杂度：O(logn)