欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序算法的递归与非递归

程序员文章站 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);
         }

     }
     
}

 

相关标签: 数据结构