最近面试的时候，遇到很多次关于快速排序的问题以及其变种问题，所以做一个总结，梳理一下知识。
快速排序的原理 通过设定基准值（一般取第一个数据），进行一趟排序，将待排数据分成独立的两部分，其中一部分数据都小于基准值，另外一部分数据都大于基准值；接着继续使用该方法分别对这两部分数据进行排序，直到所有数据成为有序序列。 快速排序的示例 一开始设定基准值为数组第一个数据49排序的全过程
快速排序的实现 import java.util.Arrays;/** * 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分， * 其中一部分的所有数据都比另外一部分的所有数据都要小， * 然后再按此方法对这两部分数据分别进行快速排序， * 整个排序过程可以递归进行，以此实现整个数据变成有序序列。 */public class QuickSort {private static int MAXNUM = 10;public static void main(String[] args) {int[] array = new int[MAXNUM];for(int i = 0; i < MAXNUM; i++){array[i] = (int) (100 * Math.random() + 1);}System.out.println("Original array:");//打印排序前的数组System.out.println(Arrays.toString(array));System.out.println("QuickSort:");//打印排序后的数组quickSort(array, 0, array.length-1);System.out.println(Arrays.toString(array));}public static void quickSort(int[] array, int left, int right){if(left < right){//如果只有1个元素就不执行，2个及以上元素才会执行int pivot = array[left];//设置为基准值int low = left;//左指针int high = right;//右指针while(low < high){while(low < high && array[high] >= pivot)//右指针指向的值大于等于基准值high--;//右指针左移，直到指向的值小于基准值array[low] = array[high];//将左指针指向的值和该值交换while(low < high && array[low] <= pivot)//左指针指向的值小于等于基准值low++;//左指针右移，直到指向的值大于基准值array[high] = array[low];//将该值与右指针指向的值交换}array[low] = pivot;//将基准值填入正确的位置，这样得到基准值左边的数据都小于它，右边同理System.out.println("pivot = " + pivot + "," + Arrays.toString(array));quickSort(array, left, low - 1);quickSort(array, low + 1, right);}}} 时间复杂度 平均为O(nlogn)，最好为O(nlogn)，最差为O(logn2) 变种问题 链表数据的快速排序 由于链表的特殊结构，无法像数组一样通过左右指针的方法来指定数据，所以解法有所不同。下面一篇文章介绍下链表下的快速排序。
文中图片来自程序人生微信公众号，如侵删。