快速排序算法总结

据说快速排序算法是实际当中最常用的一种排序算法，是冒泡排序的一种改进，速度快，效率高。于是我查了一下百科，然后按照自己的思路给实现了一下。

快速排序的百科

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

理解：其实他的基本思想就是在要排序的数中随便取一个数（既然是随便，那就不如取第一个）为参考数，通过排序，以参考数为中心，使小于参考数的都在左边，大于的在右边，至于等于参考数的我理解没有必要特意移动他的位置了，哪里都一样，反正跟参考数相等。之后再递归参考数左右两边的数据。

一次快速排序的过程：

（1）取数组第一个数作为参考数key；

（2）设置坐标值i为0，j为数组count-1；

（3）从j开始向前搜索，当遇到第一个比key小的值的时候，将坐标为j的数据与坐标为i的数据进行交换；

（4）从i开始向后搜索，当遇到第一个比key大的值的时候，将坐标为i的数据与坐标为j的数据进行交换；

（5）重复（3）和（4），直到i>=j，停止搜索，此时的数据则是以key为参考值，key左边的数据都小于等于key，右边的都大于等于key。

图示举例：

初始状态：

i = 0, j = 10, key = 12

第一次查询替换,从右向左    

i = 0, j = 8, key = 12

第二次查询替换，从左向右  

i = 1, j = 8, key = 12

第三次查询替换，从右向左，从上图可以看出，12的右边已经没有比12小的数了，所以依次搜索到j = 1 = i后，搜索停止。此时就已经完成了第一轮的快速排序。

完整的快速排序：

完成一轮的排序之后，已经将数据以key值为中心分成了左右小大数两派了，接下来就是递归这两派就好了，一般都不会采取将数据直接截开然后再拼接的做法，而是将需要递归的范围传入到方法当中，比如第一轮的排序是从0到count-1，那么第二轮就应该是从0到i，从j + 1到count-1。

注意，这里有一个坑！！！之前我的理解是，第二轮的排序从j + 1到count - 1和从j到count - 1是一样的，区别只是把参考值再重新排一遍。但是这是不对的，一定要注意这里，否则容易出现死循环。对于一个第一个数是最小数的数组，那么第一轮排序时是从0到count-1，排序过后的关键值是i=0，j=0，那么如果第二次排序的时候是按照j到count-1，则依然是0到count-1。所以，如果是选择第一个数据为参考数，那么第二次排序的时候一定是j+1到count-1，0到i（或者是0到i - 1，这个无所谓，因为不会出现上述情况）。同理，如果喜欢以最后一个数据作为参考数的话，那么第二段排序的分段则是从0到i - 1，j到count-1（或者j+1到count - 1）。

接下来为OC的关键代码：

快排的大致原理就是这样，测试的时候一定记得测试特殊情况：

（1）取第一个数为参考数，第一数即为最小或者最大数。

（2）取最后一个数为参考数，最后一个数即为最大或者最小数。