教學(xué)目的： 掌握排序的基本概念，插入排序、快速排序的算法
教學(xué)重點： 插入排序、快速排序的算法
教學(xué)難點： 快速排序算法
授課內(nèi)容：
一、排序概述
排序：將一個數(shù)據(jù)元素的無序序列重新排列成一個按關(guān)鍵字有序的序列。
姓名 年齡 體重
1李由 57 62
2王天 54 76
3七大 24 75
4張強 24 72
5陳華 24 53
上表按年齡無序，如果按關(guān)鍵字年齡用某方法排序后得到下表：
姓名 年齡 體重
3七大 24 75
4張強 24 72
5陳華 24 53
2王天 54 76
1李由 57 62
注意反色的三條記錄保持原有排列順序，則稱該排序方法是穩(wěn)定的！
如果另一方法排序后得到下表：
姓名 年齡 體重
4張強 24 72
3七大 24 75
5陳華 24 53
2王天 54 76
1李由 57 62
原3,4,5記錄順序改變，則稱該排序方法是不穩(wěn)定的！
內(nèi)部排序：待排序記錄存放在計算機隨機存儲器中進(jìn)行的排序過程；
外部排序：待排序記錄的數(shù)量很大，以致內(nèi)存不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。
二、插入排序
1、直接插入排序
基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。排序過程：
38 49 65 97 76 13 27 49 ...
38 49 65 76 97 13 27 49 ...
13 38 49 65 76 97 27 49 ...
13 27 38 49 65 76 97 49 ...
13 27 38 49 49 65 76 97 ...
2、折半插入排序
在直接插入排序中，為了找到插入位置，采用了順序查找的方法。為了提高查找速度，可以采用折半查找，這種排序稱折半插入排序。
3、2－路插入排序
為減少排序過程中移動記錄的次數(shù)，在折半插入排序的基礎(chǔ)上加以改進(jìn)：
49 38 65 97 78 13 27 49 ...
i=1 49
first
i=2 49 38
final first
i=3 49 65 38
final first
i=4 49 65 97 38
final first
i=5 49 65 76 97 38
final first
i=6 49 65 76 97 13 38
final first
i=7 49 65 76 97 13 27 38
final first
i=8 49 49 65 76 97 13 27 38
final first
三、快速排序
1、起泡排序
首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個記錄交換之，然后比較第二個記錄和第三個記錄的關(guān)鍵字。直至第n-1個記錄和第n個記錄的關(guān)鍵字進(jìn)行過比較為止。
然后進(jìn)行第二趟起泡排序，對前n-1個記錄進(jìn)行同樣操作。
...直到在某趟排序過程中沒有進(jìn)行過交換記錄的操作為止。
49 38 38 38 38 13 13
38 49 49 49 13 27 27
65 65 65 13 27 38 38
97 76 13 27 49 49
76 13 27 49 49
13 27 49 65
27 49 78
49 97
初始 第一趟 第二趟 第三趟 第四趟 第五趟 第六趟
2、快速排序
通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。
初始關(guān)鍵字 49 38 65 97 76 13 27 49
i j j
1次交換之后 27 38 65 97 76 13 49
i i j
2次交換之后 27 38 97 76 13 65 49
i j j
3次交換之后 27 38 13 97 76 65 49
i i j
4次交換之后 27 38 13 76 97 65 49
ij j
完成一趟排序 27 38 13 49 76 97 65 49
初始狀態(tài) 49 38 65 97 76 13 27 49
劃分 27 38 13 49 76 97 65 49
分別進(jìn)行 13 27 38
結(jié)束 結(jié)束 49 65 76 97
49 65 結(jié)束
結(jié)束
有序序列 13 27 38 49 49 65 76 97
四、總結(jié)
幾種排序的簡單分析與比較。（時間、空間復(fù)雜度）
五、作業(yè)
實現(xiàn)直接插入排序、起泡排序、快速排序算法。
教學(xué)重點： 插入排序、快速排序的算法
教學(xué)難點： 快速排序算法
授課內(nèi)容：
一、排序概述
排序：將一個數(shù)據(jù)元素的無序序列重新排列成一個按關(guān)鍵字有序的序列。
姓名 年齡 體重
1李由 57 62
2王天 54 76
3七大 24 75
4張強 24 72
5陳華 24 53
上表按年齡無序，如果按關(guān)鍵字年齡用某方法排序后得到下表：
姓名 年齡 體重
3七大 24 75
4張強 24 72
5陳華 24 53
2王天 54 76
1李由 57 62
注意反色的三條記錄保持原有排列順序，則稱該排序方法是穩(wěn)定的！
如果另一方法排序后得到下表：
姓名 年齡 體重
4張強 24 72
3七大 24 75
5陳華 24 53
2王天 54 76
1李由 57 62
原3,4,5記錄順序改變，則稱該排序方法是不穩(wěn)定的！
內(nèi)部排序：待排序記錄存放在計算機隨機存儲器中進(jìn)行的排序過程；
外部排序：待排序記錄的數(shù)量很大，以致內(nèi)存不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。
二、插入排序
1、直接插入排序
基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。排序過程：
38 49 65 97 76 13 27 49 ...
38 49 65 76 97 13 27 49 ...
13 38 49 65 76 97 27 49 ...
13 27 38 49 65 76 97 49 ...
13 27 38 49 49 65 76 97 ...
2、折半插入排序
在直接插入排序中，為了找到插入位置，采用了順序查找的方法。為了提高查找速度，可以采用折半查找，這種排序稱折半插入排序。
3、2－路插入排序
為減少排序過程中移動記錄的次數(shù)，在折半插入排序的基礎(chǔ)上加以改進(jìn)：
49 38 65 97 78 13 27 49 ...
i=1 49
first
i=2 49 38
final first
i=3 49 65 38
final first
i=4 49 65 97 38
final first
i=5 49 65 76 97 38
final first
i=6 49 65 76 97 13 38
final first
i=7 49 65 76 97 13 27 38
final first
i=8 49 49 65 76 97 13 27 38
final first
三、快速排序
1、起泡排序
首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個記錄交換之，然后比較第二個記錄和第三個記錄的關(guān)鍵字。直至第n-1個記錄和第n個記錄的關(guān)鍵字進(jìn)行過比較為止。
然后進(jìn)行第二趟起泡排序，對前n-1個記錄進(jìn)行同樣操作。
...直到在某趟排序過程中沒有進(jìn)行過交換記錄的操作為止。
49 38 38 38 38 13 13
38 49 49 49 13 27 27
65 65 65 13 27 38 38
97 76 13 27 49 49
76 13 27 49 49
13 27 49 65
27 49 78
49 97
初始 第一趟 第二趟 第三趟 第四趟 第五趟 第六趟
2、快速排序
通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。
初始關(guān)鍵字 49 38 65 97 76 13 27 49
i j j
1次交換之后 27 38 65 97 76 13 49
i i j
2次交換之后 27 38 97 76 13 65 49
i j j
3次交換之后 27 38 13 97 76 65 49
i i j
4次交換之后 27 38 13 76 97 65 49
ij j
完成一趟排序 27 38 13 49 76 97 65 49
初始狀態(tài) 49 38 65 97 76 13 27 49
劃分 27 38 13 49 76 97 65 49
分別進(jìn)行 13 27 38
結(jié)束 結(jié)束 49 65 76 97
49 65 結(jié)束
結(jié)束
有序序列 13 27 38 49 49 65 76 97
四、總結(jié)
幾種排序的簡單分析與比較。（時間、空間復(fù)雜度）
五、作業(yè)
實現(xiàn)直接插入排序、起泡排序、快速排序算法。