快速排序中的partition函数详解
浏览数：21 /
时间：2015年06月08日
快速排序的精髓就在partition函数的实现。我们构建两个指针，将数组分为三部分，黑色部分全部小于pivot，中间蓝色部分都大于pivot，后面红色部分未知。i指针遍历整个数组，只要它指向的元素小于pivot就交换两个指针指向的元素，然后递增。
// arr[]为数组，start、end分别为数组第一个元素和最后一个元素的索引
// povitIndex为数组中任意选中的数的索引
int partition(int arr[], int start, int end, int pivotIndex)
{
int pivot = arr[pivotIndex];
swap(arr[pivotIndex], arr[end]);
int storeIndex = start;
//这个循环比一般的写法简洁高效
for(int i = start; i < end; ++i) {
if(arr[i] < pivot) {
swap(arr[i], arr[storeIndex]);
++storeIndex;
}
}
swap(arr[storeIndex], arr[end]);
return storeIndex;
}两次swap是为了将pivot先暂存在最后一个位置，在完成一次partition之后将pivot还原至storeIndex所指的位置。因为它之前的元素都小于它，之后的都大于它。
如果没有这两次swap，那么storeIndex将指向大于等于pivot的元素，并不能保证它之后的元素都大于pivot（能保证之前的都是小于的）。storeIndex位置的元素一旦固定直至程序结束将不会再改变，因此需要使用两次交换暂存pivot元素。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
