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））；