各种排序算法小结.txt

各种排序算法小结

//当左边部分有值(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"; 
}