1、【Word版本下載可任意編輯】 C+常用排序法分析 首先介紹一個計算時間差的函數，它在 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次) 循環次數：6次 交換次數：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次) 循環次數：6次 交換次數：3次 上面我們給出了程序段，現在我們分析它：這里，影響我們算法性能的主要部分是循環和交換， 顯然，次數越多，性能就越差。從上面的程序我們可以看出循環的次數是固定的，為1+2+.+n-1。 寫成公式就是1/2*(n-1)*n。 現在注意，我們給出O方

3、法的定義： 若存在一常量K和起點n0，使當n=n0時，有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次) 循環次數：6次 交換次數：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次) 循環次數：6次 交換次數：3次 從運行的表格來看，交換幾乎和冒泡一樣糟。事實確實如此。循環次數和冒泡一樣 也是1/2*(n-1)*n，所以算法的復雜度仍然是O(n*n)。由于我們無法給出所有的情況，所以 只能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。 3.選擇法： 現在我們終于可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下） 這種方法類似我們人為的排序習慣：從數據中選擇的同個值交換，在從省下的部分中 選擇的與第二個交換，這樣往復下去。 #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次) 循環次數：6次 交換次數：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次) 循環次數：6次 交換次數：3次 遺憾的是算法需要的循環次數依然是1/2*(n-1)*n。所以算法復雜度為O(n*n)。 我們來看他的交換。由于每次外層循環只產生交換（只有一個值）。所以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次)(循環1次) 第二輪：9,10,8,7-8,9,10,7(交換1次)(循環2次) 輪：8,9,10,7-7,8,9,10(交換1次)(循環3次) 循環次數：6次 交換次數：3次 其他： 輪：8,10,7,9-8,10,7,9(交換0次)(循環1次) 第二輪：8,10,7,9-7,8,10,9(交換1次)(循環2次) 輪：7,8,10,9-7,8,9,10(交換1次)(循環1次) 循環次數：4次 交換次數：2次 上面結尾的行為分析事實上造成了一種假象，讓我們認為這種算法是簡單算法中的，其實不是， 因為其循環次數雖然并不固定，我們仍可以使用O方法。從上面的結果可以看出，循環

8、的次數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; /下面的比較都調用我們重載的操作符函數 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