//當左邊部分有值(left<j)，遞歸左半邊 
if(left<j) 
run(pData,left,j); 
//當右邊部分有值(right>i)，遞歸右半邊 
if(right>i) 
run(pData,i,right); 
} 

void QuickSort(int* pData,int Count) 
{ 
run(pData,0,Count-1); 
} 

void main() 
{ 
int data[] = {10,9,8,7,6,5,4}; 
QuickSort(data,7); 
for (int i=0;i<7;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 

這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析算法：首先我們考慮最理想的情況 
1.數組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。 
2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。 
第一層遞歸，循環n次，第二層循環2*(n/2)...... 
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n 
所以算法復雜度為O(log2(n)*n) 
其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變 
成交換法（由于使用了遞歸，情況更糟）。但是你認為這種情況發生的幾率有多大？？呵呵，你完全 
不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。 
如果你擔心這個問題，你可以使用堆排序，這是一種穩定的O(log2(n)*n)算法，但是通常情況下速度要慢 
于快速排序（因為要重組堆）。 

三、其他排序 
1.雙向冒泡： 
通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。 
代碼看起來復雜，仔細理一下就明白了，是一個來回震蕩的方式。 
寫這段代碼的作者認為這樣可以在冒泡的基礎上減少一些交換（我不這么認為，也許我錯了）。 
反正我認為這是一段有趣的代碼，值得一看。 
#include <iostream.h> 
void Bubble2Sort(int* pData,int Count) 
{ 
int iTemp; 
int left = 1; 
int right =Count -1; 
int t; 
do 
{ 
//正向的部分 
for(int i=right;i>=left;i--) 
{ 
if(pData[i]<pData[i-1]) 
{ 
iTemp = pData[i]; 
pData[i] = pData[i-1]; 
pData[i-1] = iTemp; 
t = i; 
} 
} 
left = t+1; 

//反向的部分 
for(i=left;i<right+1;i++) 
{ 
if(pData[i]<pData[i-1]) 
{ 
iTemp = pData[i]; 
pData[i] = pData[i-1]; 
pData[i-1] = iTemp; 
t = i; 
} 
} 
right = t-1; 
}while(left<=right); 
} 

void main() 
{ 
int data[] = {10,9,8,7,6,5,4}; 
Bubble2Sort(data,7); 
for (int i=0;i<7;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 


2.SHELL排序 
這個排序非常復雜，看了程序就知道了。 
首先需要一個遞減的步長，這里我們使用的是9、5、3、1（最后的步長必須是1）。 
工作原理是首先對相隔9-1個元素的所有內容排序，然后再使用同樣的方法對相隔5-1個元素的排序 
以次類推。 
#include <iostream.h> 
void ShellSort(int* pData,int Count) 
{ 
int step[4]; 
step[0] = 9; 
step[1] = 5; 
step[2] = 3; 
step[3] = 1; 

int iTemp; 
int k,s,w; 
for(int i=0;i<4;i++) 
{ 
k = step[i]; 
s = -k; 
for(int j=k;j<Count;j++) 
{ 
iTemp = pData[j]; 
w = j-k;//求上step個元素的下標 
if(s ==0) 
{ 
s = -k; 
s++; 
pData[s] = iTemp; 
} 
while((iTemp<pData[w]) && (w>=0) && (w<=Count)) 
{ 
pData[w+k] = pData[w]; 
w = w-k; 
} 
pData[w+k] = iTemp; 
} 
} 
} 

void main() 
{ 
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1}; 
ShellSort(data,12); 
for (int i=0;i<12;i++) 
cout<<data[i]<<" "; 
cout<<"\n"; 
} 
呵呵，程序看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕松多了，這里是避免使用0 
步長造成程序異常而寫的代碼。這個代碼我認為很值得一看。 
這個算法的得名是因為其發明者的名字D.L.SHELL。依照參考資料上的說法：“由于復雜的數學原因 
避免使用2的冪次步長，它能降低算法效率。”另外算法的復雜度為n的1.2次冪。同樣因為非常復雜并 
“超出本書討論范圍”的原因（我也不知道過程），我們只有結果了。 


四、基于模板的通用排序： 
這個程序我想就沒有分析的必要了，大家看一下就可以了。不明白可以在論壇上問。 
MyData.h文件 
/////////////////////////////////////////////////////// 
class CMyData 
{ 
public: 
CMyData(int Index,char* strData); 
CMyData(); 
virtual ~CMyData(); 

int m_iIndex; 
int GetDataSize(){ return m_iDataSize; }; 
const char* GetData(){ return m_strDatamember; }; 
//這里重載了操作符： 
CMyData& operator =(CMyData &SrcData); 
bool operator <(CMyData& data ); 
bool operator >(CMyData& data ); 

private: 
char* m_strDatamember; 
int m_iDataSize; 
}; 
//////////////////////////////////////////////////////// 

MyData.cpp文件 
//////////////////////////////////////////////////////// 
CMyData::CMyData(): 
m_iIndex(0), 
m_iDataSize(0), 
m_strDatamember(NULL) 
{ 
} 

CMyData::~CMyData() 
{ 
if(m_strDatamember != NULL) 
delete[] m_strDatamember; 
m_strDatamember = NULL; 
} 

CMyData::CMyData(int Index,char* strData): 
m_iIndex(Index), 
m_iDataSize(0), 
m_strDatamember(NULL) 
{ 
m_iDataSize = strlen(strData); 
m_strDatamember = new char[m_iDataSize+1]; 
strcpy(m_strDatamember,strData); 
} 

CMyData& CMyData::operator =(CMyData &SrcData) 
{ 
m_iIndex = SrcData.m_iIndex; 
m_iDataSize = SrcData.GetDataSize(); 
m_strDatamember = new char[m_iDataSize+1]; 
strcpy(m_strDatamember,SrcData.GetData()); 
return *this; 
} 

bool CMyData::operator <(CMyData& data ) 
{ 
return m_iIndex<data.m_iIndex; 
} 

bool CMyData::operator >(CMyData& data ) 
{ 
return m_iIndex>data.m_iIndex; 
} 
/////////////////////////////////////////////////////////// 

////////////////////////////////////////////////////////// 
//主程序部分 
#include <iostream.h> 
#include "MyData.h" 

template <class T> 
void run(T* pData,int left,int right) 
{ 
int i,j; 
T middle,iTemp; 
i = left; 
j = right; 
//下面的比較都調用我們重載的操作符函數 
middle = pData[(left+right)/2]; //求中間值 
do{ 
while((pData[i]<middle) && (i<right))//從左掃描大于中值的數 
i++; 
while((pData[j]>middle) && (j>left))//從右掃描大于中值的數 
j--; 
if(i<=j)//找到了一對值 
{ 
//交換 
iTemp = pData[i]; 
pData[i] = pData[j]; 
pData[j] = iTemp; 
i++; 
j--; 
} 
}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次） 

//當左邊部分有值(left<j)，遞歸左半邊 
if(left<j) 
run(pData,left,j); 
//當右邊部分有值(right>i)，遞歸右半邊 
if(right>i) 
run(pData,i,right); 
} 

template <class T> 
void QuickSort(T* pData,int Count) 
{ 
run(pData,0,Count-1); 
} 

void main() 
{ 
CMyData data[] = { 
CMyData(8,"xulion"), 
CMyData(7,"sanzoo"), 
CMyData(6,"wangjun"), 
CMyData(5,"VCKBASE"), 
CMyData(4,"jacky2000"), 
CMyData(3,"cwally"), 
CMyData(2,"VCUSER"), 
CMyData(1,"isdong") 
}; 
QuickSort(data,8); 
for (int i=0;i<8;i++) 
cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n"; 
cout<<"\n"; 
}