各种排序算法的稳定性和时间复杂度小结

冒泡 O(n2) O(n2) 稳定 O(1) n小时较好 交换 O(n2) O(n2) 不稳定 O(1) n小时较好 选择 O(n2) O(n2) 不稳定 O(1) n小时较好 插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好 基数 O(logRB) O(logRB) 稳定 O(n) B 是真数(0-9)，

R是基数(个十百)

Shell O(nlogn) O(ns) 1

以下是一个基于模板的通用排序：

这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。 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

bool CMyData::operator >(CMyData& data ) {

return m_iIndex>data.m_iIndex; }

///////////////////////////////////////////////////////////

////////////////////////////////////////////////////////// //主程序部分

#include #include \

template

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]

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

run(pData,left,j);

//当右边部分有值(right>i)，递归右半边 if(right>i)

run(pData,i,right); }

template

void QuickSort(T* pData,int Count) {

run(pData,0,Count-1); }

void main() {

CMyData data[] = { CMyData(8,\ CMyData(7,\ CMyData(6,\ CMyData(5,\ CMyData(4,\ CMyData(3,\ CMyData(2,\ CMyData(1,\ };

QuickSort(data,8); for (int i=0;i<8;i++)

cout<