內(nèi)部排序：指待排序記錄全部存放在內(nèi)存中排序的過(guò)程。
外部排序：指待排序記錄的數(shù)量很大，以至于內(nèi)存不能容納全部記錄，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的過(guò)程。
插入排序
1.直接插入排序
先將序列中的第一個(gè)記錄看成一個(gè)有序列，然后從第二個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序，排序過(guò)程為n-1躺插入。
- 時(shí)間效率：因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（0+1+...+n-1)—>O(n的平方），時(shí)間復(fù)雜度O(n的平方）。
- 空間效率：僅占用1個(gè)緩沖單元—O(1)
-
算法的穩(wěn)定性：穩(wěn)定
2、希爾排序
示意圖
選擇排序
每一次從待排序的數(shù)據(jù)元素中選出最小的一個(gè)元素，存放在已排序列的后面，直到全部待排序的數(shù)據(jù)元素排完。
- 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單
- 缺點(diǎn)：每趟只能確定一個(gè)元素，表長(zhǎng)為n時(shí)需要n-1趟
- 前提：順序存儲(chǔ)結(jié)構(gòu)
1、直接選擇排序
在所有記錄中選出最小的記錄，把它與第一個(gè)記錄交換，然后在剩余的記錄內(nèi)選出最小的記錄與第二個(gè)記錄交換...依次類推。
示意圖
2、堆排序
示意圖
堆排序的最壞時(shí)間復(fù)雜度為O(n倍的log以2為底的n次方），堆排序平均性能接近最壞性能。
堆排序的輔助空間為O(1)。
交換排序
1、冒泡排序
- 時(shí)間效率：O(n的平方)
- 空間效率：O(1)
- 穩(wěn)定性：穩(wěn)定
2、快速排序
- 優(yōu)點(diǎn)：因?yàn)槊刻丝梢源_定不止一個(gè)元素的位置，而且呈指數(shù)增加，所以特別
示意圖
快速排序最壞時(shí)間復(fù)雜度O(n的平方），最好時(shí)間復(fù)雜度為O(n倍的log以2為底的n次方）
歸并排序
可以把一個(gè)長(zhǎng)度為n的無(wú)序序列看成是n個(gè)長(zhǎng)度為1的有序子序列，首先做兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序子序列；再做兩兩歸并，如此重復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序序列。
示意圖
時(shí)間效率：O(nLog以2為底的n次方)
空間效率：O(n)
穩(wěn)定性：穩(wěn)定
算法復(fù)雜性比較
排序算法時(shí)間復(fù)雜度表
