排序關鍵字

基本概念

排序:將數據表(datalist)中無規律數據按關鍵碼在一定的規律順次下排列起來。

關鍵碼(key):通常數據對象有多個屬性域，即多個數據成員組成，其中有一個屬性域可用來區分對象，作為排序依據。該域即為關鍵碼。每個數據表用哪個屬性域作為關鍵碼，要視具體的套用需要而定。即使是同一個表，在解決不同問題的場合也可能取不同的域做關鍵碼。

主關鍵碼:如果在數據表中各個對象的關鍵碼互不相同，這種關鍵碼即主關鍵碼。按照主關鍵碼進行排序，排序的結果是唯一的。

次關鍵碼:數據表中有些對象的關鍵碼可能相同，這種關鍵碼稱為次關鍵碼。按照次關鍵碼進行排序，排序的結果可能不唯一。

排序算法的穩定性:如果在對象序列中有兩個對象:f[i]和:f[j]，它們的關鍵碼k[i] - k[j]，且在排序之前，對象:r[i]排在r[j]前面。如果在排序之後，對象r[i]仍在對象r[j]的前面，則稱這個排序方法是穩定的，否則稱這個排序方法是不穩定的。

內排序與外排序:內排序是指在排序期間數據對象全部存放在記憶體的排序;外排序是指在排序期間全部對象個數太多，不能同時存放在記憶體，必須根據排序過程的要求，不斷在內、外存之間移動的排序。

排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標誌。排序的時間開銷可用算法執行中的數據比較次數與數據移動次數來衡量。

靜態排序:排序的過程是對數據對象本身進行物理地重排，經過比較和判斷，將對象移到合適的位置。這時，數據對象一般都存放在一個順序的表中。

動態排序:給每個對象增加一個連結指針，在排序的過程中不移動對象或傳送數據，僅通過修改連結指針來改變對象之間的邏輯順序從而達到排序的目的。

算法思想:將一個待排序的記錄插入到已排好序的有序表中的適當位置，從而得到一個新的、記錄數增1的有序表。

算法思想:希爾排序是對直接插入排序改進後提出的，又稱“縮小增量排序”。先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。

算法思想:對待排序的記錄關鍵字進行兩兩比較，若兩個記錄是反序的，則進行交換，直到無反序的記錄為止。

算法思想:是對冒泡排序的一種改進、通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄進行排序，已達到整個序列有序。

算法思想:每一趟排序是通過進行n-i次關鍵字的比較，從n-i+ 1個待排序記錄中選出關鍵字最小的記錄後和第i個記錄進行交換，直到待排序的數據元素有序為止。

算法思想:堆排序是一種樹形選擇排序。首先需要將待排序記錄按排序關鍵字建成一個小(或大)頂堆，即子結點的關鍵字總是小於(或者大於)它的父節點。然後輸出堆頂的元素，把剩餘n-1個元素的序列重新調整成一個堆，重複此過程，直到待排序的數據元素有序為止。