常用排序算法递归篇之快速排序
上一篇讲了几种非递归实现的常用排序算法，接下来把常用的几种用递归实现的排序算法也讲一下。本篇先讲快速排序，首先来描述一下快速排序的基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序的实现描述：
1、首先设置两个变量i、j，排序开始的时候：i = 0，j = N - 1；
2、以第一个数组元素作为关键数据，赋值给compare，即compare = A[0]；
3、从J开始向前搜索，即由后开始向前搜索（j = j - 1即j--），找到第一个小于compare的值A[j]，A[j]与A[i]交换；
4、从i开始向后搜索，即由前开始向后搜索（i = i + 1即i++），找到第一个大于compare的A[i]，A[i]与A[j]交换；
5）重复第3、4、5步，直到 i=j； (3,4步在程序中没找到的时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i，j指针位置不变。)
根据以上算法描述，具体实现代码如下：
void quick_sort(int *array, int length){ _quick_sort(array, 0, length - 1);}void _quick_sort(int *array, int begin, int end){ int compare = array[begin]; int left = begin; int right = end; if (left > right) { return; } while (left < right) { while ((left < right) && (array[right] >= compare)) right--; swap(array[left], array[right]); while ((left < right) && (array[left] < compare)) left++; swap(array[right], array[left]); } _quick_sort(array, begin, right - 1); _quick_sort(array, right + 1, end);}从上面的算法描述和实现中都可以看出，其实每一次交换都是在跟关键数据compare在进行，只要在右边找到一个小于compare的数据或者在左边找到一个大于compare的数据就跟compare进行交换。接下来，给出另外一种方法：在左边找到一个大于compare数据的同时在右边找到一个小于compare数据才进行一次交换。具体实现代码可以参考如下：
void _quick_sort(int *array, int begin, int end){ int left = begin; int right = end; int middle = (begin + end) / 2; int compare = array[middle]; //选择中间元素作为基准 if (left > right) { return; } while (left <= right) { while (array[left] < compare) left++; while (array[right] > compare) right--; if (left <= right) { swap(array[right], array[left]); right--; left++; } } _quick_sort(array, left, end); _quick_sort(array, begin, right);}