一、排序的基本概念

1-1、穩(wěn)定性

穩(wěn)定性指的是相同的數(shù)據(jù)所在的位置經(jīng)過排序后是否發(fā)生變化。若是排序后，次序不變，則是穩(wěn)定的。

1-2、歸位

每一趟排序能確定一個(gè)元素的最終位置。

1-3、內(nèi)部排序

排序記錄全部存放在內(nèi)存中進(jìn)行排序的過程。

1-4、外部排序

待排序記錄的數(shù)量很大，以至于內(nèi)存不能容納全部記錄，在排序過程中尚需對(duì)外存進(jìn)行訪問的排序過程。

1-5、排序小結(jié)（要背）

比較最好時(shí)間復(fù)雜度，會(huì)發(fā)現(xiàn)，當(dāng)待排序的序列基本有序的話，適合采用：

• 直接插入排序
• 希爾排序
• 冒泡排序?

二、直接插入排序

穩(wěn)定的?

不歸位

三、希爾排序

直接插入排序的改進(jìn)。

基本思想：現(xiàn)將整個(gè)待排記錄序列分割成若干子序列，然后分別進(jìn)行直接插入排序；待整個(gè)序列中的記錄基本有序的時(shí)候，再對(duì)全體記錄進(jìn)行一次直接插入排序。

示例：

不穩(wěn)定

不歸位?

四、真題1

真題1：

真題2：

?真題3：

真題4：

五、簡單選擇排序

算法思想：從待排數(shù)組中找到最小值，再將最小值與已排好序的數(shù)組后一位進(jìn)行交換。

歸位

不穩(wěn)定?

六、堆排序（簡單了解）?

示例：

此時(shí)，根元素80是最大的元素，將根元素80和隊(duì)列最后一個(gè)元素10交換，并將80脫離當(dāng)前序列（歸位），此時(shí)，新的二叉樹不滿足大頂堆的規(guī)則，則繼續(xù)調(diào)整。

每次調(diào)整完得到的根節(jié)點(diǎn)都是當(dāng)前序列的最大元素！！！

歸位

不穩(wěn)定

七、真題2

真題1：

?

真題2：

八、冒泡排序

基本思想：相鄰兩個(gè)元素，倆倆交換。

穩(wěn)定

歸位?

?

九、快速排序

快速排序首先選擇了一個(gè)基準(zhǔn)值，然后分別選擇兩個(gè)指針在數(shù)組中一個(gè)找大，一個(gè)找小，然后進(jìn)行交換。

通過一趟排序?qū)⒋判虻挠涗浺曰鶞?zhǔn)值為分界，分為獨(dú)立的兩個(gè)部分，稱為前半?yún)^(qū)和后半?yún)^(qū)；前半?yún)^(qū)均小于基準(zhǔn)值，后半?yún)^(qū)均大于基準(zhǔn)值。

然后再分別對(duì)這兩個(gè)部分在進(jìn)行快速排序，從而使得整個(gè)序列有序。

分治：分而治之。

歸位

不穩(wěn)定！！！?

糾錯(cuò)：空間時(shí)間復(fù)雜度是：O(log2n)；?

十、真題2

真題1：

真題2：

真題3：

真題4：

十一、歸并排序

示例：

?

設(shè)計(jì)方法：分治法

不歸并

穩(wěn)定

11-1、真題

真題1：

真題2：

?真題3：

真題4：

真題5：

真題6：

十二、排序小結(jié)

12-1、簡單排序

1、直接插入排序（穩(wěn)定）

2、冒泡排序（穩(wěn)定）

3、簡單選擇排序（不穩(wěn)定）

時(shí)間復(fù)雜度都是：O(n^2)

空間復(fù)雜度：O(1)

12-2、希爾排序（不穩(wěn)定）

時(shí)間復(fù)雜度：O(n^1.3)

空間復(fù)雜度：O(1)

12-3、快速排序（不穩(wěn)定）

分治思想

時(shí)間復(fù)雜度：O(nlog2n)——性能最好

空間時(shí)間復(fù)雜度：O(log2n)

但是，當(dāng)待排序列基本有序的時(shí)候，是最壞的情況，時(shí)間復(fù)雜度退化為：O(n^2)

12-4、堆排序（不穩(wěn)定）

時(shí)間復(fù)雜度：O(nlog2n)

空間時(shí)間復(fù)雜度：O(1)

12-5、歸并排序（穩(wěn)定）

倆倆歸并，n/2向上取整

整個(gè)歸并排序，需要進(jìn)行l(wèi)og2n趟（向上取整）

空間復(fù)雜度：O(n)

時(shí)間復(fù)雜度：O(nlogn)

12-6、小結(jié)-穩(wěn)定的排序

• 直接插入排序；
• 冒泡排序
• 歸并排序

12-7、真題

真題1：

真題2：

真題3：

直接插入排序：局部有序

冒泡：每一趟排序，都將最大的泡泡在最后的位置。