直觀感受幾種常用排序算法,具體內容如下
1 快速排序
介紹:
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下,排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較,但這種狀況并不常見。事實上,快速排序通常明顯比其他Ο(n log n) 算法更快,因為它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來,且在大部分真實世界的數據,可以決定設計的選擇,減少所需時間的二次方項之可能性。
步驟:
從數列中挑出一個元素,稱為 "基準"(pivot),
重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊)。在這個分區退出之后,該基準就處于數列的中間位置。這個稱為分區(partition)操作。
遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序。
排序效果:
2 歸并排序
介紹:
歸并排序(Merge sort,臺灣譯作:合并排序)是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用
步驟:
申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合并后的序列
設定兩個指針,最初位置分別為兩個已經排序序列的起始位置
比較兩個指針所指向的元素,選擇相對小的元素放入到合并空間,并移動指針到下一位置
重復步驟3直到某一指針達到序列尾
將另一序列剩下的所有元素直接復制到合并序列尾
排序效果:
3 堆排序
介紹:
堆積排序(Heapsort)是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構,并同時滿足堆性質:即子結點的鍵值或索引總是小于(或者大于)它的父節點。
步驟:
(比較復雜,自己上網查吧)
排序效果:
4 選擇排序
介紹:
選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續尋找最小元素,然后放到排序序列末尾。以此類推,直到所有元素均排序完畢。
排序效果:
新聞熱點
疑難解答