深入剖析快速排序过程
快速排序的过程十分简洁明了，就是将待排序元素序列进行切分，然后分支递归。以数组从小到大排序为例，现将快速排序算法中切分数组独立出来作为一个方法partition来说明。
void quick_sort(int array[], int low, int high){ if(low>= high) return; int index = partition(array, low, high); quick_sort(array, low, index-1); quick_sort(array, index+1, high);}
?
int partion(int array[], int low, int high){ int index = low; int pivot = array[high]; for(int i = low; i < high; i++) { if(array[i] <= pivot) { swap(&array[i], &array[index++]); } } swap(&array[high], &array[index]); return _low;}?
int partion(int array[], int low, int high){ int pivot = array[low]; int _low = low; int _high = high; while(_low < _high) { while(_low<_high && array[_low] <= pivot) { _low++; } while(_low<_high && array[_high] >= pivot) { _high--; } swap(&array[_low], &array[_high]); } swap(&array[_low],&array[low]); return _low;}?
如果十分熟悉快速排序的人恐怕会一眼就可以看出来上述代码是错误的（那么这些朋友们应该可以跳过这么一大段了）。这里我们也要讨论的就是这个问题，pivot的取值与先_high--还是先_low++的顺序有联系吗？起初，我也认为这个决策的先后顺序对排序结果应该是没有什么影响的，草草了解了下其思想就匆匆带着代码上阵了，代码实现倒是很快，但纠结了很长时间愣是找不出来错在哪儿。调试了半天，弄得焦头烂额，最终决定坐下来好好分析一下，这才发现原来这个顺序还真是起着决定性的作用的。那么究竟问题出在哪里呢？问题就出来快速排序的思想并没掌握好吧（如果你也说不出个为什么顺序存在的意义的话）
?
int partion(int array[], int low, int high){ int pivot = array[low]; int _low = low; int _high = high; while(_low < _high) { while(_low<_high && array[_high] >= pivot) { _high--; } while(_low<_high && array[_low] <= pivot) { _low++; } swap(&array[_low], &array[_high]); } swap(&array[_low],&array[low]); return _low;}?
再给定同样的输入，却得到的是正确的结果。开始时，_low指向的是元素4，_high指向的元素是5；在循环结束还未进行最后的swap时，_low指向的元素是1，_high指向的元素也是1,此时数组的状态是[4,3,2,1,5]，而在swap之后，则是[1,3,2,4,5]。现在可算是切片成功了！
?
int partion(int array[], int low, int high){ int pivot = array[low]; int _low = low; int _high = high; while(_low < _high) { while(_low<_high && array[_high] >= pivot) { _high--; } array[_low] = array[_high]; while(_low<_high && array[_low] <= pivot) { _low++; } array[_high] = array[_low]; } swap(&array[_low],&array[low]); return _low;}?
?
?
ⅹ
PS：在随机化版本的快速排序中，也只是将随机选取的枢纽值与array[low]或array[high]交换一下，最后所要面对的问题也还是一样的。
?
当然，这两种思想下数组切分的还是很有区别的，虽然感觉上第一种要好实现和好理解一点，但按我的理解，还是第二种思想要高效一点。其原因有二：
一.?第一种数组切分要进行的交换实在是太多了（相对来说），大约为第二种数组切分方式的两倍。（但时间复杂度都是O(n)）
二.?另外感觉第一种数组切分情况下，在最终结果中与pivot相等的数要么全都集中到左子数组中（如果采用<=来比较）要么全都集中到右子数组中（如果采用<来比较）；而在第二种切分数组方式下，则可以混合搭配<=,<与>=,>，能将与之相等的元素更好的“均匀”分配到两个子数组中，可以更好的贯彻分治的思想。
?
?
不得不感叹算法的奇妙之处，有一个简单的快速排序也还是有那么些细节是极其需要注意的。同时也不得不意识到理解算法的原理与能够转换成代码来实现还是很有区别的，只有自己独立的做了才会真正意识到自己掌握还是没掌握….
