資料結構——排序

排序（sorting）

什麼是排序

将一組雜亂無章的資料按一定規律順次排列起來。

• 資料表 (datalist)：它是待排序資料對象的有限集合。
• 主關鍵字(key): 資料對象有多個屬性域, 即多個資料成員組成, 其中有一個屬性域可用來區分對象, 作為排序依據，稱為關鍵字。也稱為排序碼。

排序的目的是什麼？

便于查找！

什麼叫内部排序？什麼叫外部排序？

• 若待排序記錄都在記憶體中，稱為内部排序；
• 若待排序記錄一部分在記憶體，一部分在外存，則稱為外部排序。

外部排序時，要将資料分批調入記憶體來排序，中間結果還要及時放入外存，顯然外部排序要複雜得多。

排序算法的好壞如何衡量？

• 時間效率——排序速度（比較次數與移動次數）
• 空間效率——占記憶體輔助空間的大小
• 穩定性——A和B的關鍵字相等，排序後A、B的先後次序保持不變，則稱這種排序算法是穩定的。

排序的分類

内部排序

• 插入排序
  • 直接（折半）插入排序
  • 希爾排序
• 交換排序
  • 冒泡排序
  • 快速排序
• 選擇排序
• 歸并排序
• 基數排序

外部排序

• 借助外部的輔助存儲器（比如：硬碟），由于資料是存在外存中，故資料不可随機被存取

存儲方式

• 位址連續的一組存儲單元（記錄之間的次序關系由存儲位置決定，實作排序必須借助移動記錄）
• 靜态連結清單（記錄之間的次序關系由指針訓示，實作排序不需要移動記錄，僅需修改指針）－－連結清單排序
• 位址連續的一組存儲單元，另設一個訓示各個記錄存儲位置的位址向量，在排序過程中不移動記錄本身，而移動位址向量中的位址，在排序之後再按照位址向量中的值調整記錄的存儲位置－－位址排序

#define MAXSIZE 20  // 設記錄不超過20個
typedef int KeyType;  // 設關鍵字為整型量（int型）

typedef struct {
    // 定義每個記錄（資料元素）的結構
    KeyType key;  // 關鍵字
    InfoType otherinfo;  // 其他資料項
} RedType;

typedef struct {
    // 定義順序表的結構
    RedType r[MAXSIZE + 1];  // 存儲順序表的向量
    // r[0]一般作哨兵或緩沖區
    int length;  // 順序表的長度
} SqList;           

各種排序算法比較

（資料不是順次後移時将導緻方法不穩定）

排序算法比較

• 按平均時間排序方法分為四類
  • O(n^2)
  • O(nlogn)
  • O(n^(1+r))
  • O(n)
• 快速排序是基于比較的内部排序中平均性能最好的
• 基數排序時間複雜度最低，但對關鍵字結構有要求
• 為避免順序存儲時大量移動記錄的時間開銷，可考慮用連結清單作為存儲結構
  • 直接插入排序
• 不宜采用連結清單作為存儲結構的
  • 折半插入排序
  • 堆排序

排序算法選擇規則

• n較大時
  • 分布随機，穩定性不做要求，則采用快速排序
  • 記憶體允許，要求排序穩定時，則采用歸并排序
  • 可能會出現正序或逆序，穩定性不做要求，則采用堆排序或歸并排序
• n較小時
  • 基本有序，則采用直接插入排序
  • 分布随機，則采用簡單選擇排序，若排序碼不接近逆序，也可以采用直接插入排序