佚名通过本文主要向大家介绍了实时统计数据排序结果,定量计分排序结果,excel排序结果不对,塑料膜实验的排序结果,sql查询结果排序等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：快速排序结果出错
描述:
解决方案1:
描述:
正确的快排:
void quick_sort( vector<int>& numbers, int begin, int end )
{
if( begin >= end-1 )
return;
int k = partition( numbers, index, begin, end);
quick_sort( numbers, index, begin, k);
quick_sort( numbers, index, k+1, end );
}
int partition(vector<int>& numbers, int begin, int end)
{
int pivot = numbers[begin];
int i = begin;
int j = end;
while( i < j ){
while( numbers[++i] < pivot && i < end );
while( numbers[--j] > pivot && j > begin );
if( i < j ){
int tmp = numbers[i ];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
}
numbers[begin] = numbers[j];
numbers[j] = pivot;
return j;
}
我自己写的partition函数有一点不同,就是i,j的初始值不同,内层的while循环也有相应的改变,我觉得没有什么不同,但是使用我的partition函数排序结果就是错误的,求教这是怎么回事?
下面是我的partition函数
int partition(vector<int>& numbers, vector<int>& index, int begin, int end)
{
int pivot = numbers[begin];
int i= begin+1;//这里
int j = end-1;
while( i < j ){
while( numbers[i] < pivot && i <= end-1){
++i;
}
while( numbers[j] > pivot && j > begin ){
--j;
}
if( i < j ){
int tmp = numbers[i ];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
}
numbers[begin] = numbers[j];
numbers[j] = pivot;
return j;
}
解决方案1:
int i= begin+1;//这里
int j = end-1;
while( i < j )
你这里循环的次数就变了啊