简介

疾速排序也采纳的是分而制之的思维。那么疾速排序和归并排序的区别在什么中央呢？

归并排序是将所有的元素拆分成一个个排好序的数组，而后将这些数组再进行合并。

而疾速排序尽管也是拆分，然而拆分之后的操作是从数组中选出一个两头节点，而后将数组分成两局部。

右边的局部小于两头节点，左边的局部大于两头节点。

而后再别离解决右边的数组合左边的数组。

疾速排序的例子

如果咱们有一个数组：29,10,14,37,20,25,44,15，怎么对它进行疾速排序呢？

先看一个动画：

咱们再剖析一下疾速排序的步骤。

咱们抉择的是最右边的元素29作为两头点元素，而后将数组分成三局部：[0, 14, 15, 20, 25],[29],[44, 37]。

两头节点29曾经排好序了，不须要解决。

接下来咱们再对左右别离进行疾速排序。最初就失去了一个所有元素都排序的数组。

疾速排序的java代码实现

咱们先来看最外围的局部partition，如何将数组以两头节点为界，分成左右两局部呢？

咱们的最终后果，是要将array宰割成为三局部。

首先咱们抉择最左侧的元素作为两头节点的值。而后遍历数组中的其余元素。

如果m=middleIndex，k=要遍历的元素index

思考两种状况，第一种状况是数组中的元素比两头节点的值要大。

这种状况下，m不须要挪动，k+1持续遍历即可。

第二种状况下，数组中的元素比两头节点的值要小。

因为m右边的元素都要比两头节点的值要小，所以这种状况下m须要+1，即右移一位。

当初m+1地位的元素要么还没有进行比拟，要么就是比两头节点的值要大，咱们能够奇妙的将m+1地位的元素和k地位的元素调换地位，这样依然可能保障m左侧的元素要比两头节点的值要小。

将下面的剖析总结成java代码如下：

 private int partition(int[] array, int i, int j) {        //抉择最左侧的元素作为中心点,middleValue就是中心点的值        int middleValue = array[i];        int middleIndex = i;        //从i+1遍历整个数组        for (int k = i+1; k <= j; k++) {            //如果数组元素小于middleValue，示意middleIndex须要右移一位            //右移之后，咱们须要将小于middleValue的array[k]挪动到middleIndex的右边，            // 最简略的方法就是替换k和middleIndex的值            if (array[k] < middleValue) {                middleIndex++;                //替换数组的两个元素                swap(array, k , middleIndex);            } //如果数组元素大于等于middleValue,则持续向后遍历,middleIndex值不变        }        // 最初将中心点放入middleIndex地位        swap(array, i, middleIndex);        return middleIndex;    }

最初咱们须要将最左侧的元素和两头节点应该在的index的元素调换下地位，这样就将两头节点挪动到了两头地位，并返回两头地位。

再来看下divide的代码：

    public void doQuickSort(int[] array, int low, int high) {        //递归的完结条件        if (low < high) {            //找出核心节点的值            int middleIndex = partition(array, low, high);            //数组分成了三局部：            // a[low..high] ~> a[low..m–1], pivot, a[m+1..high]            //递归遍历左侧局部            doQuickSort(array, low, middleIndex-1);            // a[m] 是核心节点，曾经排好序了，不须要持续遍历            //递归遍历右侧局部            doQuickSort(array, middleIndex+1, high);            log.info("QuickSort之后的数组:{}",array);        }    }

divide的代码就很简略了，找到两头节点的地位之后，咱们再别离遍历数组的左右两边即可。最初失去排好序的数组。

随机疾速排序的java实现

下面的例子中，咱们的两头节点的抉择是数组的最左元素，为了保障排序的效率，咱们能够从数组中随机抉择一个元素来作为两头节点。

 private int partition(int[] array, int i, int j) {        //随机抉择一个元素作为中心点,middleValue就是中心点的值        int randomIndex=i+new Random().nextInt(j-i);        log.info("randomIndex:{}",randomIndex);        //首先将randomIndex的值和i调换地位,就能够复用QuickSort的逻辑        swap(array, i , randomIndex);        int middleValue = array[i];        int middleIndex = i;        //从i遍历整个数组        for (int k = i+1; k <= j; k++) {            //如果数组元素小于middleValue，示意middleIndex须要右移一位            //右移之后，咱们须要将小于middleValue的array[k]挪动到middleIndex的右边，            // 最简略的方法就是替换k和middleIndex的值            if (array[k] < middleValue) {                middleIndex++;                //替换数组的两个元素                swap(array, k , middleIndex);            } //如果数组元素大于等于middleValue,则持续向后遍历,middleIndex值不变        }        // 最初将中心点放入middleIndex地位        swap(array, i, middleIndex);        return middleIndex;    }

下面的代码，咱们在分区的时候，先抉择出一个随机的节点，而后将这个随机的节点和最左侧的元素替换地位，前面的代码就能够重用下面的QuickSort的代码逻辑了。

疾速排序的工夫复杂度

从下面的剖析咱们能够看出，每次分区的工夫复杂度应该是O(N)，而divide又近似二分法，所以总的工夫复杂度是O(N logN)。

本文的代码地址：

learn-algorithm

本文作者：flydean程序那些事

本文链接：http://www.flydean.com/algorithm-quick-sort/

本文起源：flydean的博客

欢送关注我的公众号:程序那些事，更多精彩等着您！