快速排序的递归算法和非递归算法
程序员文章站
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;
}