C++常用排序法分析

1、【W(wǎng)ord版本下載可任意編輯】 C+常用排序法分析 首先介紹一個(gè)計(jì)算時(shí)間差的函數(shù)，它在 void BubbleSort(int* pData,int Count) int iTemp; for(int i=1;i=i;j-) if(pData iTemp = pData; pData = pData; pData = iTemp; void main() int data = 10,9,8,7,6,5,4; BubbleSort(data,7); for (int i=0;i10,9,7,8-10,7,9,8-7,10,9,8(交換3次) 第二輪：7,10,9,8-7,10,8,9-7,8,1

2、0,9(交換2次) 輪：7,8,10,9-7,8,9,10(交換1次) 循環(huán)次數(shù)：6次 交換次數(shù)：6次 其他： 輪：8,10,7,9-8,10,7,9-8,7,10,9-7,8,10,9(交換2次) 第二輪：7,8,10,9-7,8,10,9-7,8,10,9(交換0次) 輪：7,8,10,9-7,8,9,10(交換1次) 循環(huán)次數(shù)：6次 交換次數(shù)：3次 上面我們給出了程序段，現(xiàn)在我們分析它：這里，影響我們算法性能的主要部分是循環(huán)和交換， 顯然，次數(shù)越多，性能就越差。從上面的程序我們可以看出循環(huán)的次數(shù)是固定的，為1+2+.+n-1。 寫成公式就是1/2*(n-1)*n。 現(xiàn)在注意，我們給出O方

3、法的定義： 若存在一常量K和起點(diǎn)n0，使當(dāng)n=n0時(shí)，有f(n) void ExchangeSort(int* pData,int Count) int iTemp; for(int i=0;i9,10,8,7-8,10,9,7-7,10,9,8(交換3次) 第二輪：7,10,9,8-7,9,10,8-7,8,10,9(交換2次) 輪：7,8,10,9-7,8,9,10(交換1次) 循環(huán)次數(shù)：6次 交換次數(shù)：6次 其他： 輪：8,10,7,9-8,10,7,9-7,10,8,9-7,10,8,9(交換1次) 第二輪：7,10,8,9-7,8,10,9-7,8,10,9(交換1次) 輪：7,8,

4、10,9-7,8,9,10(交換1次) 循環(huán)次數(shù)：6次 交換次數(shù)：3次 從運(yùn)行的表格來看，交換幾乎和冒泡一樣糟。事實(shí)確實(shí)如此。循環(huán)次數(shù)和冒泡一樣 也是1/2*(n-1)*n，所以算法的復(fù)雜度仍然是O(n*n)。由于我們無法給出所有的情況，所以 只能直接告訴大家他們?cè)诮粨Q上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。 3.選擇法： 現(xiàn)在我們終于可以看到一點(diǎn)希望：選擇法，這種方法提高了一點(diǎn)性能（某些情況下） 這種方法類似我們?nèi)藶榈呐判蛄?xí)慣：從數(shù)據(jù)中選擇的同個(gè)值交換，在從省下的部分中 選擇的與第二個(gè)交換，這樣往復(fù)下去。 #include (iTemp=9)10,9,8,7-(iTemp=

5、8)10,9,8,7-(iTemp=7)7,9,8,10(交換1次) 第二輪：7,9,8,10-7,9,8,10(iTemp=8)-(iTemp=8)7,8,9,10(交換1次) 輪：7,8,9,10-(iTemp=9)7,8,9,10(交換0次) 循環(huán)次數(shù)：6次 交換次數(shù)：2次 其他： 輪：8,10,7,9-(iTemp=8)8,10,7,9-(iTemp=7)8,10,7,9-(iTemp=7)7,10,8,9(交換1次) 第二輪：7,10,8,9-(iTemp=8)7,10,8,9-(iTemp=8)7,8,10,9(交換1次) 輪：7,8,10,9-(iTemp=9)7,8,9,10(

6、交換1次) 循環(huán)次數(shù)：6次 交換次數(shù)：3次 遺憾的是算法需要的循環(huán)次數(shù)依然是1/2*(n-1)*n。所以算法復(fù)雜度為O(n*n)。 我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生交換（只有一個(gè)值）。所以f(n) void InsertSort(int* pData,int Count) int iTemp; int iPos; for(int i=1;i=0) & (iTemp pData = pData; iPos-; pData = iTemp; void main() int data = 10,9,8,7,6,5,4; InsertSort(data,7); for (int i=0;i9,

7、10,8,7(交換1次)(循環(huán)1次) 第二輪：9,10,8,7-8,9,10,7(交換1次)(循環(huán)2次) 輪：8,9,10,7-7,8,9,10(交換1次)(循環(huán)3次) 循環(huán)次數(shù)：6次 交換次數(shù)：3次 其他： 輪：8,10,7,9-8,10,7,9(交換0次)(循環(huán)1次) 第二輪：8,10,7,9-7,8,10,9(交換1次)(循環(huán)2次) 輪：7,8,10,9-7,8,9,10(交換1次)(循環(huán)1次) 循環(huán)次數(shù)：4次 交換次數(shù)：2次 上面結(jié)尾的行為分析事實(shí)上造成了一種假象，讓我們認(rèn)為這種算法是簡(jiǎn)單算法中的，其實(shí)不是， 因?yàn)槠溲h(huán)次數(shù)雖然并不固定，我們?nèi)钥梢允褂肙方法。從上面的結(jié)果可以看出，循環(huán)

8、的次數(shù)f(n) void run(int* pData,int left,int right) int i,j; int middle,iTemp; i = left; j = right; middle = pData; /求中間值 do while(pDatai)，遞歸右半邊 if(righti) 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=

9、0;i 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 iTemp = pData; pData = pData; pData = iTemp; t = i; left = t+1; /反向的部分 for(i=left;i int ShellPass(int * array,int d) /一趟增量為d的希爾插入排序 int temp; int k=0; for(int

10、 i=d+1;i1); cout(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* st

11、rData): m_iIndex(Index), m_iDataSize(0), m_strDatamember(NULL) m_iDataSize = strlen(strData); m_strDatamember = new char; strcpy(m_strDatamember,strData); CMyData& CMyData:operator =(CMyData &SrcData) m_iIndex = SrcData.m_iIndex; m_iDataSize = SrcData.GetDataSize(); m_strDatamember = new char; strcp

12、y(m_strDatamember,SrcData.GetData(); return *this; bool CMyData:operator (CMyData& data ) return m_iIndexdata.m_iIndex; / / /主程序部分 #include void run(T* pData,int left,int right) int i,j; T middle,iTemp; i = left; j = right; /下面的比較都調(diào)用我們重載的操作符函數(shù) middle = pData; /求中間值 do while(pDatai)，遞歸右半邊 if(righti) run(pData,i,right); template void QuickSort(T* pData,int Count) run(pData,0,Count-1); void main() CMyData data = CMyData(8,xulion), CMyData(7,sanzoo), CMyDa