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