|
前幾天應(yīng)一個朋友的要求,，幫他完成了數(shù)據(jù)排序的一個作業(yè),。覺得很有給大家參考的價值，所以經(jīng)過他同意,，作了些修改帖了上來,。源代碼見附件，代碼中實現(xiàn)了8種排序算法，各算法名稱見下表或見源碼,。運行程序時,，將需要你輸入一數(shù)值，以確定對多少隨機數(shù)進(jìn)行排序,。然后將會顯示各排序算法的耗時,。并且你可選擇時否進(jìn)行正序和反序測試。 由于水平有限,，可能存在一些錯誤,，還請各位多多指點！ 通過實驗我們可將結(jié)果列入下表,。 以下是VC6.0(Release)＋win2000pro+128MDDR+P4(1.6G) 因為在多任務(wù)操作系統(tǒng)下,，系統(tǒng)將進(jìn)行進(jìn)程序調(diào)度，影響實驗結(jié)果,。以下是經(jīng)過稍微修正過的值,。如果要取得更準(zhǔn)確的值，我們得多次實驗求其平均值,。 排序算法實驗比較(單位：秒)
算法與結(jié)果聯(lián)合分析 冒泡排序：在最優(yōu)情況下只需要經(jīng)過n-1次比較即可得出結(jié)果,，（這個最優(yōu)情況那就是序列己是正序，從100K的正序結(jié)果可以看出結(jié)果正是如此）,，但在最壞情況下,，即倒序（或一個較小值在最后），下沉算法將需要n(n-1)/2次比較,。所以一般情況下,，特別是在逆序時，它很不理想,。它是對數(shù)據(jù)有序性非常敏感的排序算法,。 冒泡排序２：它是冒泡排序的改良（一次下沉再一次上浮）,，最優(yōu)情況和最壞情況與冒泡排序差不多,，但是一般情況下它要好過冒泡排序，它一次下沉,，再一次上浮,，這樣避免了因一個數(shù)的逆序，而造成巨大的比較,。如（2,3,4,…,n-1,n,1）,，用冒泡排序需要n(n-1)/2次比較，而此排序只要3輪,共比較(n-1)+(n-2)+(n-3)次,，第一輪1將上移一位,，第二輪1將移到首位,，第三輪將發(fā)現(xiàn)無數(shù)據(jù)交換，序列有序而結(jié)束,。但它同樣是一個對數(shù)據(jù)有序性非常敏感的排序算法,，只適合于數(shù)據(jù)基本有序的排序。 快速排序：它同樣是冒泡排序的改進(jìn),，它通過一次交換能消除多個逆序,，這樣可以減少逆序時所消耗的掃描和數(shù)據(jù)交換次數(shù)。在最優(yōu)情況下,，它的排序時間復(fù)雜度為Ｏ(nlog2n),。即每次劃分序列時，能均勻分成兩個子串,。但最差情況下它的時間復(fù)雜度將是Ｏ(n^2),。即每次劃分子串時，一串為空,，另一串為m-1（程序中的100K正序和逆序就正是這樣,，如果程序中采用每次取序列中部數(shù)據(jù)作為劃分點，那將在正序和逆時達(dá)到最優(yōu)）,。從100K中正序的結(jié)果上看“快速排序”會比“冒泡排序”更慢,，這主要是“冒泡排序”中采用了提前結(jié)束排序的方法。有的書上這解釋“快速排序”,，在理論上講,，如果每次能均勻劃分序列，它將是最快的排序算法,，因此稱它作快速排序,。雖然很難均勻劃分序列，但就平均性能而言,，它仍是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者,。 直接選擇排序：簡單的選擇排序，它的比較次數(shù)一定：n(n-1)/2,。也因此無論在序列何種情況下,，它都不會有優(yōu)秀的表現(xiàn)（從上100K的正序和反序數(shù)據(jù)可以發(fā)現(xiàn)它耗時相差不多，相差的只是數(shù)據(jù)移動時間）,，可見對數(shù)據(jù)的有序性不敏感,。它雖然比較次數(shù)多,，但它的數(shù)據(jù)交換量卻很少,。所以我們將發(fā)現(xiàn)它在一般情況下將快于冒泡排序。 堆排序：由于它在直接選擇排序的基礎(chǔ)上利用了比較結(jié)果形成,。效率提高很大,。它完成排序的總比較次數(shù)為Ｏ(nlog2n),。它是對數(shù)據(jù)的有序性不敏感的一種算法。但堆排序?qū)⑿枰鰞蓚€步驟：－是建堆,，二是排序（調(diào)整堆）,。所以一般在小規(guī)模的序列中不合適，但對于較大的序列,，將表現(xiàn)出優(yōu)越的性能,。 直接插入排序：簡單的插入排序，每次比較后最多移掉一個逆序,，因此與冒泡排序的效率相同,。但它在速度上還是要高點，這是因為在冒泡排序下是進(jìn)行值交換,，而在插入排序下是值移動,，所以直接插入排序?qū)⒁獌?yōu)于冒泡排序。直接插入法也是一種對數(shù)據(jù)的有序性非常敏感的一種算法,。在有序情況下只需要經(jīng)過n-1次比較,，在最壞情況下，將需要n(n-1)/2次比較,。 希爾排序：增量的選擇將影響希爾排序的效率,。但是無論怎樣選擇增量，最后一定要使增量為１,，進(jìn)行一次直接插入排序,。但它相對于直接插入排序，由于在子表中每進(jìn)行一次比較,，就可能移去整個經(jīng)性表中的多個逆序,，從而改善了整個排序性能。希爾排序算是一種基于插入排序的算法,，所以對數(shù)據(jù)有序敏感,。 歸并排序：歸并排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間,。在使用它對兩個己有序的序列歸并,，將有無比的優(yōu)勢。其時間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n),。對數(shù)據(jù)的有序性不敏感,。若數(shù)據(jù)節(jié)點數(shù)據(jù)量大，那將不適合,。但可改造成索引操作,，效果將非常出色。 基數(shù)排序：在程序中采用的是以數(shù)值的十進(jìn)制位分解,，然后對空間采用一次性分配,，因此它需要較多的輔助空間(10*n+10), （但我們可以進(jìn)行其它分解,，如以一個字節(jié)分解，空間采用鏈表將只需輔助空間n+256）,?；鶖?shù)排序的時間是線性的(即O(n))。由此可見,，基數(shù)排序非常吸引人,，但它也不是就地排序，若節(jié)點數(shù)據(jù)量大時宜改為索引排序,。但基數(shù)排序有個前提，要關(guān)鍵字能象整型,、字符串這樣能分解,，若是浮點型那就不行了。 按平均時間將排序分為類：
因為不同的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求,，所以選擇合適的排序方法很重要 前幾天應(yīng)一個朋友的要求,，幫他完成了數(shù)據(jù)排序的一個作業(yè),。覺得很有給大家參考的價值，所以經(jīng)過他同意,，作了些修改帖了上來,。源代碼見附件，代碼中實現(xiàn)了8種排序算法,，各算法名稱見下表或見源碼,。運行程序時,，將需要你輸入一數(shù)值，以確定對多少隨機數(shù)進(jìn)行排序,。然后將會顯示各排序算法的耗時,。并且你可選擇時否進(jìn)行正序和反序測試。 由于水平有限,，可能存在一些錯誤,，還請各位多多指點！ 通過實驗我們可將結(jié)果列入下表,。 以下是VC6.0(Release)＋win2000pro+128MDDR+P4(1.6G) 因為在多任務(wù)操作系統(tǒng)下,，系統(tǒng)將進(jìn)行進(jìn)程序調(diào)度，影響實驗結(jié)果,。以下是經(jīng)過稍微修正過的值,。如果要取得更準(zhǔn)確的值，我們得多次實驗求其平均值,。 排序算法實驗比較(單位：秒)
算法與結(jié)果聯(lián)合分析 冒泡排序：在最優(yōu)情況下只需要經(jīng)過n-1次比較即可得出結(jié)果,，（這個最優(yōu)情況那就是序列己是正序，從100K的正序結(jié)果可以看出結(jié)果正是如此）,，但在最壞情況下,，即倒序（或一個較小值在最后），下沉算法將需要n(n-1)/2次比較,。所以一般情況下,，特別是在逆序時，它很不理想,。它是對數(shù)據(jù)有序性非常敏感的排序算法,。 冒泡排序２：它是冒泡排序的改良（一次下沉再一次上浮）,，最優(yōu)情況和最壞情況與冒泡排序差不多,，但是一般情況下它要好過冒泡排序，它一次下沉,，再一次上浮,，這樣避免了因一個數(shù)的逆序，而造成巨大的比較,。如（2,3,4,…,n-1,n,1）,，用冒泡排序需要n(n-1)/2次比較，而此排序只要3輪,共比較(n-1)+(n-2)+(n-3)次,，第一輪1將上移一位,，第二輪1將移到首位，第三輪將發(fā)現(xiàn)無數(shù)據(jù)交換，序列有序而結(jié)束,。但它同樣是一個對數(shù)據(jù)有序性非常敏感的排序算法,，只適合于數(shù)據(jù)基本有序的排序。 快速排序：它同樣是冒泡排序的改進(jìn),，它通過一次交換能消除多個逆序,，這樣可以減少逆序時所消耗的掃描和數(shù)據(jù)交換次數(shù)。在最優(yōu)情況下,，它的排序時間復(fù)雜度為Ｏ(nlog2n),。即每次劃分序列時,，能均勻分成兩個子串。但最差情況下它的時間復(fù)雜度將是Ｏ(n^2)。即每次劃分子串時,，一串為空,，另一串為m-1（程序中的100K正序和逆序就正是這樣，如果程序中采用每次取序列中部數(shù)據(jù)作為劃分點,，那將在正序和逆時達(dá)到最優(yōu)）,。從100K中正序的結(jié)果上看“快速排序”會比“冒泡排序”更慢，這主要是“冒泡排序”中采用了提前結(jié)束排序的方法,。有的書上這解釋“快速排序”,，在理論上講，如果每次能均勻劃分序列,，它將是最快的排序算法,，因此稱它作快速排序。雖然很難均勻劃分序列,，但就平均性能而言,，它仍是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者。 直接選擇排序：簡單的選擇排序,，它的比較次數(shù)一定：n(n-1)/2,。也因此無論在序列何種情況下，它都不會有優(yōu)秀的表現(xiàn)（從上100K的正序和反序數(shù)據(jù)可以發(fā)現(xiàn)它耗時相差不多,，相差的只是數(shù)據(jù)移動時間）,，可見對數(shù)據(jù)的有序性不敏感。它雖然比較次數(shù)多,，但它的數(shù)據(jù)交換量卻很少,。所以我們將發(fā)現(xiàn)它在一般情況下將快于冒泡排序。 堆排序：由于它在直接選擇排序的基礎(chǔ)上利用了比較結(jié)果形成,。效率提高很大,。它完成排序的總比較次數(shù)為Ｏ(nlog2n)。它是對數(shù)據(jù)的有序性不敏感的一種算法。但堆排序?qū)⑿枰鰞蓚€步驟：－是建堆,，二是排序（調(diào)整堆）,。所以一般在小規(guī)模的序列中不合適，但對于較大的序列,，將表現(xiàn)出優(yōu)越的性能,。 直接插入排序：簡單的插入排序，每次比較后最多移掉一個逆序,，因此與冒泡排序的效率相同,。但它在速度上還是要高點，這是因為在冒泡排序下是進(jìn)行值交換,，而在插入排序下是值移動,，所以直接插入排序?qū)⒁獌?yōu)于冒泡排序。直接插入法也是一種對數(shù)據(jù)的有序性非常敏感的一種算法,。在有序情況下只需要經(jīng)過n-1次比較,，在最壞情況下，將需要n(n-1)/2次比較,。 希爾排序：增量的選擇將影響希爾排序的效率,。但是無論怎樣選擇增量，最后一定要使增量為１,，進(jìn)行一次直接插入排序,。但它相對于直接插入排序，由于在子表中每進(jìn)行一次比較,，就可能移去整個經(jīng)性表中的多個逆序,，從而改善了整個排序性能。希爾排序算是一種基于插入排序的算法,，所以對數(shù)據(jù)有序敏感,。 歸并排序：歸并排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間,。在使用它對兩個己有序的序列歸并,，將有無比的優(yōu)勢。其時間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n),。對數(shù)據(jù)的有序性不敏感,。若數(shù)據(jù)節(jié)點數(shù)據(jù)量大，那將不適合,。但可改造成索引操作,，效果將非常出色。 基數(shù)排序：在程序中采用的是以數(shù)值的十進(jìn)制位分解,，然后對空間采用一次性分配,，因此它需要較多的輔助空間(10*n+10), （但我們可以進(jìn)行其它分解，如以一個字節(jié)分解，空間采用鏈表將只需輔助空間n+256）,?；鶖?shù)排序的時間是線性的(即O(n))。由此可見,，基數(shù)排序非常吸引人,，但它也不是就地排序，若節(jié)點數(shù)據(jù)量大時宜改為索引排序,。但基數(shù)排序有個前提,，要關(guān)鍵字能象整型、字符串這樣能分解,，若是浮點型那就不行了,。 按平均時間將排序分為類：
因為不同的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求,，所以選擇合適的排序方法很重要 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
