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

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

程序员文章站 2022-03-24 13:32:52
...

先写上代码,过后再补

#include<iostream>
#include<stack>
using namespace std;

//一趟快排排序
int sort(int num[], int low, int high)
{
    int n = 8;
    int pivotkey = num[low];
    while (low < high)
    {
        while (low < high&&num[high] >= pivotkey)
        {
            --high;
        }
        num[low] = num[high];
        while (low < high&&num[low] <= pivotkey)
        {
            ++low;
        }
        num[high] = num[low];
    }
    num[low] = pivotkey;
    for (int i = 0; i < n; ++i)
    {
        cout << num[i] << " ";
    }
    cout << endl;
    cout << low << " " << high << endl;
    return low;
}

//递归调用
void recursion(int num[], int low, int high)
{
    if (low < high)
    {
        int pivotkey = sort(num, low, high);
        recursion(num, low, pivotkey - 1);
        recursion(num, pivotkey + 1, high);
    }
}

//非递归调用
void storenum(int num[], int low, int high) 
{
    stack<int> st;
    if (low < high)
    {
        int mid = sort(num, low, high);
        if (low < mid - 1)
        {
            st.push(low);
            st.push(mid - 1);
        }
        if (mid + 1 < high)
        {
            st.push(mid + 1);
            st.push(high);
        }
        while (!st.empty())
        {
            int q = st.top();
            st.pop();
            int p = st.top();
            st.pop();
            mid = sort(num, p, q);
            if (p < mid - 1)
            {
                st.push(p);
                st.push(mid - 1);
            }
            if (mid + 1 < q)
            {
                st.push(mid + 1);
                st.push(q);
            }
        }
    }
}

int main()
{
    int num[8] = { 49,38,65,97,76,13,27,49 };

    //快速排序的递归算法
    recursion(num, 0, 7);
    for (int i = 0; i < 8; ++i)
    {
        cout << num[i] << " ";
    }

    //快速排序的非递归算法
    //storenum(num, 0, 7);
    //for (int i = 0; i < 8; ++i)
    //{
    //  cout << num[i] << " ";
    //}
    return 0;
}