排序算法-快速排序

前言：排序是现在程序员的必备技能，是很多公司的面试必考点，不管是做移动端，后端开发，排序是绕不过的，众生平等。学习其排序的思想往往能解决不同类型的问题，所以静下心来，研究一下不同的排序算法，算是对自己有一个提升。

排序概述：排序就是将一组对象按照某种逻辑顺序重新排列的过程。

十大排序算法：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序，希尔排序，计数排序，基数排序，桶排序。

本文对快速排序走一个解析：

快速排序步骤：

1.快速排序是对冒泡排序的一种改进，也是采用分治法的一个典型的应用。

2.首先任意选取一个数据（比如数组的第一个数）作为关键数据，我们称为基准数，然后将所有比它小的数都放在它前面，所有比它大的数都放在它后面，这个过程称为一趟快速排序，也称为分区操作。

3.通过一趟快速排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一个数据都要小或者大，然后再按此方法对这两个部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数组变成有序序列。

4.为了提升性能，有时候在分割后独立的两部分的个数小于某个数比如15的情况下，会采用其他排序算法，比如插入排序。

代码举例：

对一个数组进行排序：（86,11,77,23,32,45,58,63,93,4,37,22）

int[] array = {86,11,77,23,32,45,58,63,93,4,37,22};

排序代码展示： 

调用sort方法后打印如下：

快速排序打印

 对该案例进行分析：（86,11,77,23,32,45,58,63,93,4,37,22）

这里只分析一次过程，其他雷同。选取77元素为基准数则，因为根据快速排序步骤第二点基准数和最后一个位置要进行交换步骤则：（86,11,22,23,32,45,58,63,93,4,37,77）

（1）

      初始：  86,11, 22 ,23,32,45,58,63,93,4,37,77

       i = 0    zoneIndex = -1

      86 > 77  不做任何操作

      结果： 86,11, 22 ,23,32,45,58,63,93,4,37,77

（2）

    初始： 86,11, 22 ,23,32,45,58,63,93,4,37,77

     i = 1    zoneIndex = -1

    11 < 77  zoneIndex++ = 0;

    i > zongIndex

    结果： 11,86, 22 ,23,32,45,58,63,93,4,37,77

 (3)

    初始： 11,86, 22 ,23,32,45,58,63,93,4,37,77

     i = 2    zoneIndex = 0

    22 < 77  zoneIndex++ = 1;

    i > zongIndex

   结果： 11,22,86,23,32,45,58,63,93,4,37,77

 (4)

     初始： 11,22,86,23,32,45,58,63,93,4,37,77

     i = 3    zoneIndex = 1

     23 < 77  zoneIndex++ = 2;

     i > zongIndex

    结果： 11,22,23,86,32,45,58,63,93,4,37,77

 (5)

    初始： 11,22,23,86,32,45,58,63,93,4,37,77

    i = 4    zoneIndex = 2

    32 < 77  zoneIndex++ = 3;

    i > zongIndex

   结果： 11,22,23,32,86,45,58,63,93,4,37,77

 (6)

    初始： 11,22,23,86,32,45,58,63,93,4,37,77

    i = 5    zoneIndex = 3

    45 < 77  zoneIndex++ = 4;

    i > zongIndex

    结果： 11,22,23,32,45,86,58,63,93,4,37,77

 (7)

    初始： 11,22,23,32,45,86,58,63,93,4,37,77

    i = 6    zoneIndex = 4

    58 < 77  zoneIndex++ = 5;

    i > zongIndex

    结果： 11,22,23,32,45,58,86,63,93,4,37,77

 (8)

    初始：11,22,23,32,45,58,86,63,93,4,37,77

    i = 7    zoneIndex = 5

    63 < 77  zoneIndex++ = 6;

    i > zongIndex

   结果： 11,22,23,32,45,58,63,86,93,4,37,77

 (9)

   初始：11,22,23,32,45,58,86,63,93,4,37,77

    i = 8    zoneIndex = 6

   93 > 77  zoneIndex 不变 = 6

   i > zongIndex

   结果： 11,22,23,32,45,58,63,86,93,4,37,77

 (10)

   初始：11,22,23,32,45,58,86,63,93,4,37,77

   i = 9    zoneIndex = 6

   4 < 77  zoneIndex ++ = 7

   i > zongIndex

   结果： 11,22,23,32,45,58,63,4,93,86,37,77

 (11)

   初始：11,22,23,32,45,58,63,4,93,86,37,77

   i = 10    zoneIndex = 7

   37 < 77  zoneIndex ++ = 8

    i > zongIndex

   结果： 11,22,23,32,45,58,63,4,37,86,93,77

 (12)

   初始：11,22,23,32,45,58,63,4,37,86,93,77

   i = 11    zoneIndex = 8

   77 == 77  zoneIndex ++ = 9

    i > zongIndex

    结果： 11,22,23,32,45,58,63,4,37,77,93,86

  每一次执行完partition方法后，在基准数的左边都是小于基础数的，基准数的右边是大于基准数的。一直到最终，递 归完成。 

 代码打印：打印这里就不进行递归了，对应上面的一次过程分析，其他都是差不多的：

 至此快速排序就到这里讲解结束了，细看的话其实一点也不复杂。

后序：

1.对于基准的选取，最好的情况是基准值刚好取在无序区数值的中位数，这样能够最大效率地让两边排序，同时最大地减少递归划分的次数，但是一般很难做到最优。基准的选取一般有三种方式，选取数组的第一个元素，选取数组的最后一个元素，以及选取第一个，最有一个以及中间的元素的中位数比如4，5，6，7第一个是4，最后一个是7，中间为5，这三个数的中位数为5，所以选择5作为基准。

2.Dual-Pivot快排：双基准快速排序算法，其实就是用两个基准数，把整个数组分成三份来进行快速排序，这个比经典快排节省了10%的时间。