1. 排序的基本概念

1) 排序過程可以是物理重排,也可以是通過指針,使得邏輯有序.

2) 內(nèi)部排序和外排序:所有的記錄都在內(nèi)存中,這樣的排序為內(nèi)部排序;如果排序的過程中要不斷的進行內(nèi)存與外存的交換,這樣的排序為外部排序.

2. 插入排序:

1) 直接插入排序:穩(wěn)定的排序算法，時間復(fù)雜度：最好情況O(n)；最差情況O（n^2）；平均情況為O（n^2）;

2) 折半插入排序：穩(wěn)定的排序算法

3) 希爾排序：不穩(wěn)定的排序算法，時間復(fù)雜度為：沒有最好情況；最差情況O（nlog2n）；平均情況為O(nlog2n)。

3. 交換排序

1) 氣泡排序：穩(wěn)定的排序算法，時間復(fù)雜度為:最好情況O（n）；最差情況O(n^2);平均情況為O（n^2）.

2) 快速排序:不穩(wěn)定的排序算法，時間復(fù)雜度為：最好的情況O(nlog2n)；最差情況O(n^2)，平均情況為O(nlog2n)；

4. 選擇排序

1) 簡單選擇排序：不穩(wěn)定的排序，時間復(fù)雜度為：最好情況O(n^2);最差情況為O（n^2）;平均情況為O（n^2）;與關(guān)鍵字的初始排列無關(guān)。

2) 堆排序:不穩(wěn)定的排序，時間復(fù)雜度為：最好情況O（nlog2n）；最差情況為O（nlog2n）；平均情況O（nlog2n）；

5. 二路歸并排序 

穩(wěn)定的排序，時間復(fù)雜度為：最好情況O（nlog2n）；最差情況為O（nlog2n）；平均情況O（nlog2n）；

6. 基數(shù)排序

穩(wěn)定的排序，時間復(fù)雜度為：最好情況O（d（n+rd））；最差情況為O（d（n+rd））；平均情況O（d（n+rd））；