前段看到過一個問題(忘記在哪裡了)，用非遞歸的方式實作快速排序，今天又翻了出來，把代碼貼上，給自己以後留個參考，代碼中包括自己當時對程式改進的過程，請大家多提意見。
#include
"stdafx.h"
#include
#include
#define
MAX_SIZE10
using
namespace std;
typedef
int elem;
typedef
std::stack 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;
}
posted on 2007-02-14 09:42 DexterChen 閱讀(4254) 評論(4) 編輯 收藏 引用 所屬分類: C++ 、Algorithms