本文已被Github仓库收录 https://github.com/silently9527/JavaCore程序员罕用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin
齐全开源的淘客我的项目：https://github.com/silently9527/mall-coupons-server
微信公众号：贝塔学Java
前言
疾速排序能够说是应用最广的排序算法了，次要的特点是基于原地排序（不须要应用辅助数组，节俭空间）；其实对于长度为N的数组应用疾速排序工夫复杂度为 NlogN；在前几篇也一起探讨了其余的排序算法，都没可能把这两个特点联合起来。
疾速排序思路
疾速排序也是一种分治的排序算法，把数组划分为两个子数组，而后递归对子数组进行排序，最终保障整个数组有序。
算法思路：
- 随机抉择一个切分元素，通常抉择的是数组的第一个元素
- 从数组的右边开始扫描找出大于等于切分元素的值，从数组的左边开始扫描找出小于等于切分元素的值，替换这两个值
- 循环这个过程直到左右两个指针相遇，这样就排定了一个元素，保障了切分元素右边的值都是小于它的值，左边的元素都是大于它的值
- 递归这个过程，最终保障整个数组有序
算法实现
依据疾速排序算法的思路，咱们能够写出第一版实现：
public class QuickSort implements SortTemplate { @Override public void sort(Comparable[] array) { quickSort(array, 0, array.length - 1); } private void quickSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } int partition = partition(array, lo, hi); quickSort(array, lo, partition - 1); quickSort(array, partition + 1, hi); } private int partition(Comparable[] array, int lo, int hi) { int i = lo, j = hi + 1; Comparable el = array[lo]; while (true) { while (less(array[++i], el)) { if (i == hi) { break; } } while (less(el, array[--j])) { if (j == lo) { break; } } if (i >= j) { break; } exch(array, i, j); } exch(array, lo, j); return j; }}其中exch、less办法的实现请看之前的文章《常见的高级排序算法，这次全搞懂》
这段代码是实现疾速排序的惯例实现，思考最蹩脚的状况，如果须要排序的数组是曾经有序的[1,2,3,4,5,6,7,8]，执行疾速排序的过程如图：
对一个长度为N的数组，最蹩脚的状况下须要递归N-1次，所以工夫复杂度是O(n²)，为了防止这种状况呈现，咱们来看下算法如何改良
算法改良
- 保障随机性
为了防止最蹩脚的状况呈现，有两个方法，第一是在排序数组之前先随机打乱数组；第二是在partition办法中随机取切分元素，而不是固定取第一个，简略实现：
private int partition(Comparable[] array, int lo, int hi) { int i = lo, j = hi + 1; int random = new Random().nextInt(hi - lo) + lo; exch(array, lo, random); Comparable el = array[lo]; while (true) { while (less(array[++i], el)) { if (i == hi) { break; } } while (less(el, array[--j])) { if (j == lo) { break; } } if (i >= j) { break; } exch(array, i, j); } exch(array, lo, j); return j;}- 切换到插入排序
这点和归并排序一样，对于小数组的排序间接切换成插入排序
private void quickSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } if (hi - lo < 5) { //测试，小于5就切换到插入排序 insertionSort(array, lo, hi); return; } int partition = partition(array, lo, hi); quickSort(array, lo, partition - 1); quickSort(array, partition + 1, hi);}//插入排序private void insertionSort(Comparable[] array, int lo, int hi) { for (int i = lo; i <= hi; i++) { for (int j = i; j > lo && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); } }}- 三向切分
当咱们须要排序的数组中呈现了大量的反复元素，咱们实现的疾速排序在递归的时候会遇到许多全副反复的子数组，咱们的算法仍然会对其进行切分，这里有很大的晋升空间。
思路就是先随便抉择一个切分元素(el)，而后把数组切换成大于、等于、小于三个局部，一次递归能够排定所有等于切分元素的值；
保护一个指针lt、gt，使得a[lo..lt-1]都小于切分元素，a[gt+1..hi]都大于切分元素；
- 初始化变量：lt=lo, i=lo+1, gt=hi
- if a[i] < el ; 替换a[i]与a[lt], i++, lt++
- if a[i] > el ; 替换a[gt]与a[i], gt--
- a[i] == el; i++
代码实现：
public class Quick3waySort implements SortTemplate { @Override public void sort(Comparable[] array) { quickSort(array, 0, array.length - 1); } @SuppressWarnings("unchecked") private void quickSort(Comparable[] array, int lo, int hi) { if (lo >= hi) { return; } int lt = lo, i = lo + 1, gt = hi; Comparable el = array[lo]; while (i <= gt) { int tmp = el.compareTo(array[i]); if (tmp > 0) { exch(array, lt++, i++); } else if (tmp < 0) { exch(array, i, gt--); } else { i++; } } quickSort(array, lo, lt - 1); quickSort(array, gt + 1, hi); }}最初（点关注，不迷路）
文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。
最初，写作不易，请不要白嫖我哟，心愿敌人们能够点赞评论关注三连，因为这些就是我分享的全副能源起源????
文中所有源码已放入到了github仓库https://github.com/silently9527/JavaCore