### **排序概念** 排序就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：輸入：n 個記錄 R1，R2，…，Rn，其相應的關鍵字分別為 K1，K2，…，Kn。輸出：Ril，Ri2，…，Rin，使得 Ki1≤Ki2≤…≤Kin。(或 Ki1≥Ki2≥…≥Kin)。 排序算法的依據--關鍵字，關鍵字可以是數字類型，也可以是字符類型。 ### **排序算法的穩定性** 當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序后這些具有相同關鍵字的記錄之間的*相對次序保持不變*，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。 ### **排序算法的空間復雜度** 若排序算法所需的輔助空間并不依賴于問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。 非就地排序一般要求的輔助空間為O(n)。