快速排序算法的递归与非递归
程序员文章站
2022-03-24 13:17:19
...
//quick sort
void quicksort (int array[], int low, int high){
if(low<high){
int index = getindex(array,low,high);
quicksort(array,index+1,high);
quicksort(array,0,high);
}
}
int getindex(int array[],int low, int high){
int temp = array[low];
while (low<high){
if(array[high] >temp ){
high --;
}
array[low] = array[high];
if(array[low]<temp){
low++;
}
array[high] = array[low];
}
array[low] =temp;
return low;
}
//非递归的形式来实现快排
void quichsortnorecusive(int array[],int low,int high[]){
stack<int> s;
s.push(low);
s.push(high);
while(!s.empty()){
int h = s.top(); s.pop();
int l = s.top(); s.pop();
int index= getindex(array,l,h);
if(index-1>l){
s.push(l);//左边
s.push(index-1);//右边
}
else(index+1<h){
s.push(index +1);
s.push(h);
}
}
}
下一篇: PHP 魔术引号详解讲解_PHP教程