穩(wěn)定排序：若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，則該排序方法是穩(wěn)定的。

穩(wěn)定的排序

1.冒泡

時間：最好O(n)，最壞和平均O(n^2)；空間：1

2. 插入排序

時間：最好O(n)，最壞和平均O(n^2)；空間：1

3. 歸并排序

時間：最好，最壞和平均O(nlogn)；空間：O(n)

4. 基數(shù)排序

時間：O(dn)；空間：O(n)

不穩(wěn)定的排序

1. 選擇排序

時間：最壞和平均O(n^2)；空間：1

2. 希爾排序

時間：O(nlogn)；空間：1

3. 堆排序

時間：都是O(nlogn)；空間：1

4. 快速排序

時間：平均O(nlogn)，最壞O(n^2)；空間：O(nlogn)

內(nèi)部排序

整個文件都放在內(nèi)存中，不涉及數(shù)據(jù)的內(nèi)、外存交換，適用于計數(shù)個數(shù)不是很多的小文件。

按策略劃分內(nèi)存排序：

插入排序，選擇排序，交換排序，歸并排序