一、排序的基本概念

1-1、穩定性

穩定性指的是相同的數據所在的位置經過排序后是否發生變化。若是排序后，次序不變，則是穩定的。

1-2、歸位

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

1-3、內部排序

排序記錄全部存放在內存中進行排序的過程。

1-4、外部排序

待排序記錄的數量很大，以至于內存不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程。

1-5、排序小結（要背）

比較最好時間復雜度，會發現，當待排序的序列基本有序的話，適合采用：

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

二、直接插入排序

穩定的?

不歸位

三、希爾排序

直接插入排序的改進。

基本思想：現將整個待排記錄序列分割成若干子序列，然后分別進行直接插入排序；待整個序列中的記錄基本有序的時候，再對全體記錄進行一次直接插入排序。

示例：

不穩定

不歸位?

四、真題1

真題1：

真題2：

?真題3：

真題4：

五、簡單選擇排序

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

歸位

不穩定?

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

示例：

此時，根元素80是最大的元素，將根元素80和隊列最后一個元素10交換，并將80脫離當前序列（歸位），此時，新的二叉樹不滿足大頂堆的規則，則繼續調整。

每次調整完得到的根節點都是當前序列的最大元素！！！

歸位

不穩定

七、真題2

真題1：

?

真題2：

八、冒泡排序

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

穩定

歸位?

九、快速排序

快速排序首先選擇了一個基準值，然后分別選擇兩個指針在數組中一個找大，一個找小，然后進行交換。

通過一趟排序將待排序的記錄以基準值為分界，分為獨立的兩個部分，稱為前半區和后半區；前半區均小于基準值，后半區均大于基準值。

然后再分別對這兩個部分在進行快速排序，從而使得整個序列有序。

分治：分而治之。

歸位

不穩定！！！?

糾錯：空間時間復雜度是：O(log2n)；?

十、真題2

真題1：

真題2：

真題3：

真題4：

十一、歸并排序

示例：

?

設計方法：分治法

不歸并

穩定

11-1、真題

真題1：

真題2：

?真題3：

真題4：

真題5：

真題6：

十二、排序小結

12-1、簡單排序

1、直接插入排序（穩定）

2、冒泡排序（穩定）

3、簡單選擇排序（不穩定）

時間復雜度都是：O(n^2)

空間復雜度：O(1)

12-2、希爾排序（不穩定）

時間復雜度：O(n^1.3)

空間復雜度：O(1)

12-3、快速排序（不穩定）

分治思想

時間復雜度：O(nlog2n)——性能最好

空間時間復雜度：O(log2n)

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

12-4、堆排序（不穩定）

時間復雜度：O(nlog2n)

空間時間復雜度：O(1)

12-5、歸并排序（穩定）

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

整個歸并排序，需要進行log2n趟（向上取整）

空間復雜度：O(n)

時間復雜度：O(nlogn)

12-6、小結-穩定的排序

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

12-7、真題

真題1：

真題2：

真題3：

直接插入排序：局部有序

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