前言

快速排序可以说是使用最广的排序算法了，主要的特点是基于原地排序（不需要使用辅助数组，节省空间）；其实对于长度为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=hiif 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);    }}

文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。

最后，「写作不易，请不要白嫖我哟」，希望朋友们可以「点赞评论关注」三连，因为这些就是我分享的全部动力来源

❝

有需要的朋友回复「源码」或私信发送「源码」

❞

精美的淘客项目完全开源啦，有需要的朋友回复「源码」或私信发送「源码」