Like Share Discussion Bookmark Smile

J.J. Huang   2020-03-05   排序演算法   瀏覽次數:

排序演算法 | 簡介

在計算機科學與數學中,一個排序演算法(英語:Sorting algorithm)是一種能將一串資料依照特定排序方式進行排列的一種演算法。最常用到的排序方式是數值順序以及字典順序。有效的排序演算法在一些演算法(例如搜尋演算法與合併演算法)中是重要的,如此這些演算法才能得到正確解答。排序演算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上,排序演算法的輸出必須遵守下列兩個原則:

  • 輸出結果為遞增序列(遞增是針對所需的排序順序而言)
  • 輸出結果是原輸入的一種排列、或是重組

雖然排序演算法是一個簡單的問題,但是從計算機科學發展以來,在此問題上已經有大量的研究。舉例而言,泡沫排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題,有用的新演算法仍在不斷的被發明。

分類

在電腦科學所使用的排序演算法通常被分類為:

  • 計算的時間複雜度(最差、平均、和最好表現),依據串列(list)的大小(n)。一般而言,好的表現是O(n log n)(大O符號),壞的表現是O(n²)。對於一個排序理想的表現是O(n),但平均而言不可能達到。基於比較的排序演算法對大多數輸入而言至少需要O(n log n)。
  • 記憶體使用量(以及其他電腦資源的使用)
  • 穩定性:穩定排序演算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序演算法是穩定的,當有兩個相等鍵值的紀錄R和S,且在原本的串列中R出現在S之前,在排序過的串列中R也將會是在S之前。
  • 依據排序的方法:插入、交換、選擇、合併等等。

穩定性

當相等的元素是無法分辨的,比如像是整數,穩定性並不是一個問題。然而,假設以下的數對將要以他們的第一個數字來排序。

1
(4,1)(3,1)(3,7)(5,6)

在這個狀況下,有可能產生兩種不同的結果,一個是讓相等鍵值的紀錄維持相對的次序,而另外一個則沒有:

1
2
(3,1)(3,7)(4,1)(5,6)} (維持次序) 
(3,7)(3,1)(4,1)(5,6)} (次序被改變)

不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序,但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地實作為穩定。作這件事情的一個方式是人工擴充鍵值的比較,如此在其他方面相同鍵值的兩個物件間之比較,(比如上面的比較中加入第二個標準:第二個鍵值的大小)就會被決定使用在原先資料次序中的條目,當作一個同分決賽。然而,要記住這種次序通常牽涉到額外的空間負擔。

排序演算法列表

  • 穩定的排序

    • 泡沫排序(bubble sort)— O(n²)
    • 插入排序(insertion sort)—O(n²)
    • 雞尾酒排序(cocktail sort)—O(n²)
    • 桶排序(bucket sort)—O(n);需要O(k)額外空間
    • 計數排序(counting sort)—O(n+k);需要O(n+k)額外空間
    • 合併排序(merge sort)—O(n log n);需要O(n)額外空間
    • 原地合併排序— O(n log ² n)如果使用最佳的現在版本
    • 二元排序樹排序(binary tree sort)— O(n log n)期望時間;O(n²)最壞時間;需要O(n)額外空間
    • 鴿巢排序(pigeonhole sort)—O(n+k);需要O(k)額外空間
    • 基數排序(radix sort)—O(nk);需要O(n)額外空間
    • 侏儒排序(gnome sort)— O(n²)
    • 圖書館排序(library sort)— O(n log n)期望時間;O(n²)最壞時間;需要(1+𝓔)n額外空間
    • 塊排序(block sort)— O(n log n)
  • 不穩定的排序

    • 選擇排序(selection sort)—O(n²)
    • 希爾排序(shell sort)—O(n log² n)如果使用最佳的現在版本
    • 克洛弗排序(Clover sort)—O(n)期望時間,O(n²)最壞情況[來源請求]
    • 梳排序— O(n log n)
    • 堆積排序(heap sort)—O(n log n)
    • 平滑排序(smooth sort)— O(n log n)
    • 快速排序(quick sort)—O(n log n)期望時間,O(n²)最壞情況;對於大的、亂數串列一般相信是最快的已知排序
    • 內省排序(introsort)—O(n log n)
    • 耐心排序(patience sort)—O(n log n+k)最壞情況時間,需要額外的O(n+k)空間,也需要找 - 到最長的遞增子序列(longest increasing subsequence)
  • 不實用的排序

    • Bogo排序— O(n × n!)}O(n × n!)},最壞的情況下期望時間為無窮。
    • Stupid排序—O(n³);遞迴版本需要O(n²)額外記憶體
    • 珠排序(bead sort)— O(n) 或 O(∫n),但需要特別的硬體
    • 煎餅排序—O(n),但需要特別的硬體
    • 臭皮匠排序(stooge sort)演算法簡單,但需要約n².⁷的時間

簡要比較

結語

現在的IT行業並不像以前那麼好混了,從業人員過多,導致初級工程師過剩,這也間接導致了公司的招聘門檻越來越高,要求工程師掌握的知識也越來越多。
算法也是一個爭論了很久的話題,工程師到底該不該掌握算法?不同的人有不同的答案,而事實上,很多公司都對算法有一定的要求,有些公司直接在面試的時候便會要求面試者手寫算法題。這就對工程師的技術要求產生了很大的考驗,所以面對如今的大環境,我們必須掌握算法,才能在今後的工作中佔據一席之地。
後面的文章,我將會開始介紹一下幾個排序算法,好好增進一下自己在算法這塊的不足。


註:以上參考了
維基百科-排序演算法