演算法:排序(Sorting)


在計算機科學與數學中,一個排序演算法(英語:Sorting algorithm)是一種能將一串資料依照特定排序方式進行排列的一種演算法。有效的排序演算法在一些演算法(例如搜尋演算法與合併演算法)中是重要的,如此這些演算法才能得到正確解答。

預先對資料實行適度的排序作業會讓許多運算或問題變得容易進行。實際上,早期許多演算法研究都聚焦於資料合集的排序,這些是難以儲存在電腦記憶體中的大量資料集。因為目前的電腦比起五十年前的電腦處理能力要高出許多,現气能夠處理的資料集大小是兆位元組(terabytes)的等級。如何在針對各種狀況的問題來選擇最佳的排序演算法是很重要且必須的。

基本上,排序演算法的輸出必須遵守下列兩個原則:

  1. 輸出結果為遞增序列(遞增是針對所需的排序順序而言)

  2. 輸出結果是原輸入的一種排列、或是重組

在選擇排序演算法時也要注意下面的一些方法:

˙ 計算的時間複雜度(最差、平均、和最好表現)

˙ 記憶體使用量

˙穩定性:穩定排序演算法會讓原本有相等鍵值的紀錄維持相對次序。也就是說,有未排序的合集中的兩個元素Ai和Aj,如果兩個元素內容相等,且i<j,則Ai最終的位置一定是Aj最終位置的左邊。保證此一屬性的演算法就被視為穩定的演算法。

˙依據排序的方法:插入、交換、選擇、合併等等

簡單舉例一些常用的排序演算法

穩定:

泡沫排序(bubble sort)

插入排序(insertion sort)

合併排序(merge sort)

二元排序樹排序(binary tree sort)

不穩定:

快速排序(quick sort)

選擇排序(selection sort)

希爾排序(shell sort)

堆積排序(heap sort)

也有為了選擇排序演算法來運作或實作而有的性質準則


圖片
圖片
圖片
圖片
圖片
圖片
(使用 Facebook 留言外掛程式 留言無法滿足本網站參加活動之資格,僅供非會員討論使用)
互動地圖
interactive taiwan map