各種排序算法的總結和比較
各種排序算法的總結和比較
各種排序算法的總結和比較
1 快速排序(QuickSort)
快速排序是一個就地排序,分而治之,大規模遞歸的算法。從本質上來說,它是歸併排序的就地版本。快速排序可以由下面四步組成。
(1) 如果不多於1個數據,直接返回。
(2) 一般選擇序列最左邊的值作爲支點數據。
(3) 將序列分成2部分,一部分都大於支點數據,另外一部分都小於支點數據。
(4) 對兩邊利用遞歸排序數列。
快速排序比大部分排序算法都要快。儘管我們可以在某些特殊的情況下寫出比快速排序快的算法,但是就通常情況而言,沒有比它更快的了。快速排序是遞歸的,對於內存非常有限的機器來說,它不是一個好的選擇。
2 歸併排序(MergeSort)
歸併排序先分解要排序的序列,從1分成2,2分成4,依次分解,當分解到只有1個一組的時候,就可以排序這些分組,然後依次合併回原來的序列中,這樣就可以排序所有數據。合併排序比堆排序稍微快一點,但是需要比堆排序多一倍的內存空間,因爲它需要一個額外的數組。
3 堆排序(HeapSort)
堆排序適合於數據量非常大的場合(百萬數據)。
堆排序不需要大量的遞歸或者多維的暫存數組。這對於數據量非常巨大的序列是合適的。比如超過數百萬條記錄,因爲快速排序,歸併排序都使用遞歸來設計算法,在數據量非常大的時候,可能會發生堆棧溢出錯誤。
堆排序會將所有的數據建成一個堆,最大的數據在堆頂,然後將堆頂數據和序列的最後一個數據交換。接下來再次重建堆,交換數據,依次下去,就可以排序所有的數據。
Shell排序透過將數據分成不同的組,先對每一組進行排序,然後再對所有的元素進行一次插入排序,以減少數據交換和移動的次數。平均效率是O(nlogn)。其中分組的合理性會對算法產生重要的影響。現在多用h的分組方法。
Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相對比較簡單,它適合於數據量在5000以下並且速度並不是特別重要的場合。它對於數據量較小的數列重複排序是非常好的。
5 插入排序(InsertSort)
插入排序透過把序列中的值插入一個已經排序好的序列中,直到該序列的結束。插入排序是對冒泡排序的改進。它比冒泡排序快2倍。一般不用在數據大於1000的場合下使用插入排序,或者重複排序超過200數據項的序列。
冒泡排序是最慢的排序算法。在實際運用中它是效率最低的算法。它透過一趟又一趟地比較數組中的每一個元素,使較大的數據下沉,較小的數據上升。它是O(n^2)的算法。
7 交換排序(ExchangeSort)和選擇排序(SelectSort)
這兩種排序方法都是交換方法的排序算法,效率都是 O(n2)。在實際應用中處於和冒泡排序基本相同的地位。它們只是排序算法發展的初級階段,在實際中使用較少。
8 基數排序(RadixSort)
基數排序和通常的排序算法並不走同樣的路線。它是一種比較新穎的算法,但是它只能用於整數的排序,如果我們要把同樣的辦法運用到浮點數上,我們必須瞭解浮點數的存儲格式,並透過特殊的方式將浮點數映射到整數上,然後再映射回去,這是非常麻煩的事情,因此,它的使用同樣也不多。而且,最重要的是,這樣算法也需要較多的存儲空間。
-
人教版《分數的初步認識》教學反思
人教版《分數的初步認識》教學反思一、找準學生學習新知的“最近發展區”,在大背景下認識分數1.分數對於學生來說是全新的,如何將這一全新的知識內化爲學生自身的知識,找準學生學習的“最近發展區”是重要的,它是促使學生從“實際發展水平”向“潛在發展水平”的橋...
-
《信客》教案設計參考
《信客》教案設計參考教學目標1、知識和能力目標(1)、熟悉課文內容,瞭解信客職業。(2)、品讀精美語段,感受語言魅力。2、過程和方法目標(1)、學習從人物研究的角度整體把握作品的閱讀方法。(2)、把握作者的思想感情,揣摩其寫作意圖。3、情感、態度、價值觀目標剖...
-
《常見的量》教案
《常見的量》教案教學過程一、溫故知新1、師:下面是小紅的日記請同學們認真讀一遍2015年2月29日星期一晴今天是2015年2月29日,早上我從睡夢中醒來,一看錶已經是19點鐘了,我立刻爬起來馬上穿衣,刷牙、洗臉才用了10小時時間。想起不能遲到,我趕緊吃了一個100千克的麪包...
-
感想母親對我的愛
感想母親對我的愛在我們的腦海裏常常會想母愛是什麼?母愛是無私的,母愛是偉大的;母愛是純潔的。像春風,吹首你的心,那母愛是多麼溫暖啊!記得又一次我發高燒,那已經是深夜了,我不忍心叫媽媽起牀,但是我不得不叫媽媽起牀了,因爲我的頭像在火爐裏被燒似的,頭痛灸頭,燒的死去活...