前段看到过一个问题（忘记在哪里了），用非递归的方式实现快速排序，今天又翻了出来，把代码贴上，给自己以后留个参考，代码中包括自己当时对程序改进的过程，请大家多提意见。
#include
"stdafx.h"
#include
<iostream>
#include
<stack>
#define
MAX_SIZE 10
using
namespace std;
typedef
int elem;
typedef
std::stack<int> Stack;
int
partition(elem *pData, int low, int high);
void
swap(elem& a, elem& b);
void
qsort(elem* pData, int low, int high);
void
qsort2(elem* pData, int low, int high);
void
qsort3(elem* pData, int low, int high);
int
partition(elem *pData, int low, int high)
{
elem key = pData[low];
while(low < high)
{
while(low < high && pData[high] >= key)
high--;
swap(pData[low], pData[high]);
while(low < high && pData[low] <= key)
low++;
swap(pData[low], pData[high]);
}
return low;
}
void swap(elem& a, elem& b)
{
if(&a != &b)
{
a ^= b;
b ^= a;
a ^= b;
}
}
//这个是原始的算法
void
qsort(elem* pData, int low, int high)
{
if(low < high)
{
int pivot = partition(pData, low, high);
qsort(pData, low, pivot - 1);
qsort(pData, pivot + 1, high);
}
}
//这个是第一次转化成递归以后的算法
void
qsort2(elem* pData, int low, int high)
{
Stack st;
if(low < high)
{
int pivot = partition(pData, low, high);
st.push(low);
st.push(pivot - 1);
st.push(pivot + 1);
st.push(high);
while(!st.empty())
{
high = st.top();
st.pop();
low = st.top();
st.pop();
pivot = partition(pData, low, high);
if(low < high)
{
st.push(low);
st.push(pivot - 1);
st.push(pivot + 1);
st.push(high);
}
}
}
}
//这个是转化成递归以后改进的算法
void qsort3(elem* pData, int low, int high)
{
Stack st;
int tmp;
if(low < high)
{
int pivot = partition(pData, low, high);
st.push(low);
st.push(pivot - 1);
st.push(pivot + 1);
st.push(high);
while(!st.empty())
{
high = st.top();
st.pop();
low = st.top();
st.pop();
if(low < high)
{
pivot = partition(pData, low, high);
tmp = pivot - 1;
if(low < tmp)
{
st.push(low);
st.push(tmp);
}
tmp = pivot + 1;
if(tmp < high)
{
st.push(tmp);
st.push(high);
}
}
}
}
}
//测试代码
int _tmain(int argc, _TCHAR* argv[])
{
elem data[MAX_SIZE] = {12, 1, 13, 14, 67, 23, 12, 3, 90, 76};
//qsort(data, 0, MAX_SIZE - 1);
//qsort2(data, 0, MAX_SIZE - 1);
qsort3(data, 0, MAX_SIZE - 1);
for(int i=0; i< MAX_SIZE; i++)
{
cout << data[i] << " ";
}
cout << endl;
cin.get();
return 0;
}