排序算法之快速排序

前面谈论了简单排序里面的冒泡，选择还有插入排序，就我个人而言，觉得还是挺简单的，比较容易理解，可能也就只有插入排序稍微有点复杂，多敲几遍就ok啦！

今天来谈论一下快速排序法吧。首先这个快速排序法的发明人是C. A. R. Hoare在1962年提出来的，基本的思想是“分治法”。

那么它的主要步骤如下：

1、设定一个基准数，一般我喜欢设定左边第一个数为基准数。例如left = 0;tmp = a[left];

2、从数组的右边往左边遍历，寻找比基准数小的数；i = left; j = N - 1;

3、从数组的左边往右边遍历，寻找比基准数大的数；

4、以上两个操作是基于左边的下标小于右边的下标所进行的。i < j;交换这两个数swap(&a[i], &a[j]);之后再把tmp这个基准数填补到i == j的位置上去，一次操作就完成了。这个时候数组被分成了两个部分，大于基准数的部分，和小于基准数的部分，然后通过对这两部分进行操作，再次的切割，直到完成排序。下面举个例子，毕竟文字看不太懂。

例如需要排序的数组a为  4,5,1,3,8,9 这六个数。left = 0; right = 6 - 1 = 5;

1、设定基准数为4

2、先从右向左寻找比4小的数，发现3符合条件，这个时候 j 指向 3；

3、从左向右寻找比4大的数，发现 5 符合条件，这个时候 i 指向 5；

此时i = 1, j = 3,i<j成立。

4、交换a[i] 和 a[j] ,此时数组变为：4,3,1,5,8,9再次重复以上动作，直到i和j相遇。如果小伙伴的推导没有错的话，数组的结果如下：

1,3,4,5,8,9  因为i和j都到达了数字1，这个时候该将基准数填补到对应的1这个位置了所以才会是前面这个结果。

此时基准数4将数组切割成了两个部分，大于4的和小于4的部分，只要通过递归，再次对剩余的部分进行排序，就可以完成排序啦！下面来代码：

小结一下：

1、快速排序最坏情况的时间复杂度为O(n^2),而平均时间复杂度为O(nlog2n);

2、快速排序属于比较排序，并且快速排序是不稳定的排序。

3、快速排序通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。