//主要考虑的因素，可读性，分解均衡性。如果大家对快速排序遗忘，在看了这段代码很
//容易回忆出来，目的就达到了
#include <cstdlib>
#include <iostream>
using namespace std;
class QuickSort
{
private:
int* m_array;
int m_first;
int m_last;
public :
QuickSort(int* unSortedArray,int low,int high);
virtual ~QuickSort();
bool Process();
private:
int Partition(int key,int low,int high);
int ExtendLargeRegion(int key,int lowVac,int high);
int ExtendSmallRegion(int key,int low,int HighVac);
};
QuickSort::QuickSort(int* unSortedArray,int low,int high)
{
m_array = unSortedArray;
m_first = low;
m_last = high;
};
QuickSort::~QuickSort()
{
};
bool QuickSort::Process()
{
if(m_array == NULL)
{
return false;
}
if(m_first<m_last)
{
int pivot = m_array[m_first];
int splitPoint = Partition(pivot,m_first,m_last);
m_array[splitPoint] = pivot;
QuickSort *quickSortLeft = new QuickSort(m_array,m_first,splitPoint-1);
quickSortLeft->Process();
delete quickSortLeft;
QuickSort *quickSortRight = new QuickSort(m_array,splitPoint+1,m_last);
quickSortRight->Process();
delete quickSortRight;
}
return true;
};
int QuickSort::Partition(int key,int low,int high)
{
int lowVac = low;
int highVac = -1;
while(low<high)
{
highVac = ExtendLargeRegion(key,lowVac,high);
lowVac = ExtendSmallRegion(key,low+1,highVac);
low = lowVac;
high = highVac - 1;
}
return low;
};
int QuickSort::ExtendLargeRegion(int key,int lowVac,int high)
{
int highVac,curr;
highVac = lowVac;
for(curr = high;curr>lowVac;curr--)
{
if(m_array[curr]<key)
{
m_array[lowVac]= m_array[curr];
highVac = curr;
break;
}
}
return highVac;
};
int QuickSort::ExtendSmallRegion(int key,int low,int highVac)
{
int lowVac,curr;
lowVac = highVac;
for(curr = low;curr<highVac;curr++)
{
if(m_array[curr]>=key)
{
m_array[highVac]= m_array[curr];
lowVac = curr;
break;
}
}
return lowVac;
};
int main(int argc, char *argv[])
{
int unSortedArray[] = {31,45,36,27,88,3,4,56,78,44,65,102,-5,0};
QuickSort *Sorter = new QuickSort(&unSortedArray[0],0,13);
Sorter->Process();
delete Sorter;
cout<<endl;
for(int i=0;i<14;i++)
{
cout<<unSortedArray[i]<<endl;
}
system("PAUSE");
return EXIT_SUCCESS;
}
[此贴子已经被作者于2006-1-16 10:44:26编辑过]
[返回] 计算机科学论坛 →
计算机技术与应用 → 『 编程心得 』 → 刚写的一段快速排序算法，尽可能的面向对象，请大家在质量属性各个方面给出批评意见。
(订阅本版)
2006/1/16 0:58:00
顶端 
刚写的一段快速排序算法，尽可能的面向对象，请大家在质量属性各个方面给出批评意见。..(2609字) － pennyliang，2006年1月16日
新浪微博
