數據結構——排序

排序（sorting）

什么是排序

排序的目的是什么？

什么叫內部排序？什么叫外部排序？

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

排序的分類

內部排序

外部排序

存儲方式

各種排序算法比較

排序算法比較

排序算法選擇規則

排序（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;

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

各種排序算法比較

（數據不是順次后移時將導致方法不穩定）

排序算法比較

按平均時間排序方法分為四類

O(n^2)

O(nlogn)

O(n^(1+r))

O(n)

快速排序是基于比較的內部排序中平均性能最好的

基數排序時間復雜度最低，但對關鍵字結構有要求

為避免順序存儲時大量移動記錄的時間開銷，可考慮用鏈表作為存儲結構

直接插入排序

歸并排序

基數排序

不宜采用鏈表作為存儲結構的

折半插入排序

希爾排序

快速排序

堆排序

排序算法選擇規則

n較大時

分布隨機，穩定性不做要求，則采用快速排序

內存允許，要求排序穩定時，則采用歸并排序

可能會出現正序或逆序，穩定性不做要求，則采用堆排序或歸并排序

n較小時

基本有序，則采用直接插入排序

分布隨機，則采用簡單選擇排序，若排序碼不接近逆序，也可以采用直接插入排序

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。