快速排序的递归和非递归实现

作者: veaxen 分类: 数据结构与算法 发布时间: 2017-04-14 16:36

首先参考《递归如何转换为非递归》,然后根据文中的思想将递归快排转换为非递归快排。

先来看看递归快速排序的代码:

/*以递归的方式实现快速排序*/
void quick_sort(int array[],int left,int right)
{
    if(left>=right)
        return ;
    int key = array[left];
    int low = left;
    int high = right;

    while(low<high){
        while(low<high && array[high]>=key)
            high--;
        if(low<high)
            array[low++] = array[high];

        while(low<high && array[low]<key)
            low++;
        if(low<high)
            array[high--] = array[low];
    }
    array[low] = key;
    quick_sort1(array,left,low-1);
    quick_sort1(array,low+1,right);
}

非递归的快速排序代码:

/*非递归形式的快速排序*/

typedef struct LOCATION{
    int left;
    int right;
}location;

void quick_sort(int array[],int left,int right)
{
    location loc;
    stack<location> loc_stack;
    int key;
    int low,high;

    loc.left = left;
    loc.right = right;

    key = array[left];
    low =left;
    high =right;

    loc_stack.push(loc);
    while(!loc_stack.empty()){

        loc = loc_stack.top();
        loc_stack.pop();

        low = loc.left;
        high = loc.right;
        key = array[low];

        while(low<high){
            while(low<high && array[high]>=key)
                high--;
            if(low<high)
                array[low++] = array[high];

            while(low<high && array[low]<key)
                low++;
            if(low<high)
                array[high--] = array[low];
        } 
        array[low] = key;

        if(low+1 < loc.right){/*不满足递归结束条件*/
            location tmp;
            tmp.left = low+1;
            tmp.right = loc.right;
            loc_stack.push(tmp);
        }
        if(loc.left < low-1){/*不满足递归结束条件*/
            location tmp;
            tmp.left = loc.left;
            tmp.right = low-1;
            loc_stack.push(tmp);
        }
    }
}

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

一条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.