快速排序

快速排序的基本思想：通过一趟排序将待排序数据分隔为独立的两部分，其中的一部分数据均比另一部分小，则可分别对这两部分数据进行排序，以达到整个序列有序。

快速排序使用分治法把一个串分为两个子串。具体算法描述如下：

1、从数列中挑出一个元素，称为“基准”(pivot)

2、重新排序数列，所有元素比基准值小的摆放在基准的前面，所有元素比基准大的摆放在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个成为分区(partiton)操作

3、递归的把小于基准值元素的子数列和大于基准值元素的子数列排序。

//快速排序

func QuickSort(in []int, l, rint)  {

        if l < r {

                var i,j,xint

                 i = l

                 j = r

                x = in[i]

                for i < j {

                        for i < j && in[j] > x {

                                j--

                        }

                        if i < j {

                                in[i]=in[j]

                                i++

                        }

                        for i < j && in[i] < x {

                                i++

                        }

                        if i < j {

                                in[j] = in[i]

                                j--

                        }

                   }

                in[i] = x

                QuickSort(in,l, i-1)

                QuickSort(in, i+1,r)

        }

}

下面以数列a={30,40,60,10,20,50}为例，演示它的快速排序过程(如下图)

上图只是给出了第一趟快速排序的流程。在第一趟中，设置x=a[i],即x=30.

1、从“右-->左”查找小于x的数；找到满足条件的数a[j]=20,此时j=4；然后将a[j]赋值给a[i]，此时i=0；接着从左往右遍历。

2、从“左-->右”查找大于x的数；找到满足条件的数a[i]=40,此时i=2；然后将a[i]赋值给a[j]，此时j=4；接着从右往左遍历。

3、“右-->左”查找小于x的数；找到满足条件的数a[j]=10，此时j =3；然后将a[j]赋值给a[i],此时i=1；接着从左往右遍历

4、从“左-->右”查找大于x的数；找到满足条件的数a[i]=60，此时i=2；然后将a[i]赋值给a[j],此时j=3；接着从右往左遍历

5、从“右-->左”查找小于x的数；没有找到满足条件的数。当i>=j时，停止查找；然后将x赋值给a[i]。此趟遍历结束！

按照同样的方法，对子数列进行递归遍历。最后得到有序数组。

快速排序是不稳定的算法，它不满足稳定算法的定义。

算法稳定性：假设在数列中存在a[i] = a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的。

快速排序时间复杂度

快速排序的时间复杂度在最坏的情况下是O(n^2)，平均时间复杂度是O(N*lgN)

这句话很好理解，假设被排序的数列中有N个数。遍历一次的时间复杂度是O(n)，需要遍历多少次那？至少lg(N+1)次，最多N次。

1、为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数至少是lg(N+1)次。

2、为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快速排序的遍历次数最多是N次。