排序算法大全

《排序算法大全》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、排序算法是一種基本并且常用的算法。由于實際工作中處理的數(shù)量巨大，所以排序算法對算法本身的速度要求很高。而一般我們所謂的算法的性能主要是指算法的復雜度，一般用O方法來表示。在后面我將給出詳細的說明。對于排序的算法我想先做一點簡單的介紹，也是給這篇文章理一個提綱。我將按照算法的復雜度，從簡單到難來分析算法。第一部分是簡單排序算法，后面你將看到他們的共同點是算法復雜度為O(N*N)（因為沒有使用word,所以無法打出上標和下標）。第二部分是高級排序算法，復雜度為O(Log2(N))。這里我們只介紹一種算法。另外還有幾種算法因

2、為涉及樹與堆的概念，所以這里不于討論。第三部分類似動腦筋。這里的兩種算法并不是最好的（甚至有最慢的），但是算法本身比較奇特，值得參考（編程的角度）。同時也可以讓我們從另外的角度來認識這個問題?，F(xiàn)在，讓我們開始吧：一、簡單排序算法由于程序比較簡單，所以沒有加什么注釋。所有的程序都給出了完整的運行代碼，并在我的VC環(huán)境下運行通過。因為沒有涉及MFC和WINDOWS的內(nèi)容，所以在BORLANDC++的平臺上應該也不會有什么問題的。在代碼的后面給出了運行過程示意，希望對理解有幫助。1.冒泡法：這是最原始，也是眾所周知的最慢的算

3、法了。他的名字的由來因為它的工作看來象是冒泡：#includevoidBubbleSort(int*pData,intCount){intiTemp;for(inti=1;i=i;j--){if(pData[j]

4、Sort(data,7);for(inti=0;i<7;i++)cout<10,9,7,8->10,7,9,8->7,10,9,8(交換3次)第二輪：7,10,9,8->7,10,8,9->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->8,7,10,9->7,8,10,9(交換2次)第二輪：7,8,10,9-

5、>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?，F(xiàn)在注意，我們給出O方法的定義：若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n),則f(n)=O(g(n))。（呵呵，不要說沒學好數(shù)學呀，對于編程數(shù)學

6、是非常重要的?。。。┈F(xiàn)在我們來看1/2*(n-1)*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)=O(g(n))=O(n*n)。所以我們程序循環(huán)的復雜度為O(n*n)。再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同，交換不同。其實交換本身同數(shù)據(jù)源的有序程度有極大的關系，當數(shù)據(jù)處于倒序的情況時，交換次數(shù)同循環(huán)一樣（每次循環(huán)判斷都會交換），復雜度為O(n*n)。當數(shù)據(jù)為正序，將不會有交換。復雜度為O(0)。亂序時處于中間狀態(tài)。正是由于這樣的原

7、因，我們通常都是通過循環(huán)次數(shù)來對比算法。2.交換法：交換法的程序最清晰簡單，每次用當前的元素一一的同其后的元素比較并交換。#includevoidExchangeSort(int*pData,intCount){intiTemp;for(inti=0;i

8、){intdata[]={10,9,8,7,6,5,4};ExchangeSort(data,7);for(inti=0;i<7;i++)cout<9,10,8,7->8,10,9,7->7,10,9,8(交換3次)第二輪：7,10,9,