[ 資料結構 小學堂 ] 排序 : 排序簡介

前言 :
排序 (Sorting) 是指將一群資料, 按特定規則調換位置, 使資料具有某種次序關係 (遞增或遞減). 例如資料庫內可針對某一欄位進行排序, 而此欄位稱為 "鍵 (key)", 欄位裡面的值我們稱為 "鍵值". 在排序的過程中, 資料的移動方式可分為 "直接移動" 與 "邏輯移動" 兩種. 直接移動是直接交換儲存資料的位置, 而邏輯移動並不會移動資料儲存的位置, 僅是改變指向這些資料的輔助指標的值. 兩者的優劣在於直接移動會浪費需多時間進行資料的更動, 而邏輯移動只要改變輔助指標指向的位置就能輕易達成排序的目的.

排序的分類 :
排序可以依照執行時所使用的記憶體區分為以下兩種方式.
1. 內部排序 : 排序資料量小, 可以完全在記憶體內進行排序.
2. 外部排序 : 排序的資料量無法直接在記憶體內進行, 而必須使用到輔助記憶體 (如硬碟).
常見的內部排序法有 : 氣泡排序, 選擇排序, 插入排序, 合併排序與快速排序等, 而外部排序法有 : 直接合併排序, k 路合併法等.

排序演算法分析 :
排序演算法的選擇將會影響到排序的結果與績效, 通常可以由以下幾點決定 :
演算法是否穩定 :

穩定的演算法是指資料在經過排序後, 兩個相同鍵值的記錄仍然保持原來的次序.

時間複雜度 (Time complexity) :

當資料量相當大時, 排序演算法所花費的時間就顯得相當重要. 排序演算法的時間複雜度可以分為最好 (Best case), 最壞情況 (Worst case) 及平均情況 (Average case). 最好情況就是資料已經完成排序, 而最壞情況就是指每一鍵值均須重新排列, 簡單的例子就是由遞增排序重新排列成遞減.

空間複雜度 (Space complexity) :
空間複雜度就是指演算法在執行過程所需付出額外記憶體空間, 例如所挑選的排序法必須藉由遞迴的方式進行, 那麼遞迴過程中使用到的堆疊動作就是這個排序法必須付出的額外空間. 另外任何排序法都有資料對調的動作, 資料對調就會暫時使用到一個額外的空間, 它也是排序法中空間複雜度要考慮的問題. 排序法所使用到的額外空間越少, 它的空間複雜度就越佳. 例如氣泡法在排序過程中僅會用到一個額外的空間, 在所有排序演算法中, 這樣的空間複雜度就算是最好.

內部排序法 :
排序的各種演算法稱得上是資料結構這門課的精隨所在. 每一種排序方法都有其適用的情況與資料種類. 首先我們將內部排序法依照演算法的時間複雜度與空間複雜度整理如下 :

This message was edited 2 times. Last update was at 21/11/2010 20:31:04