程序設(shè)計(jì)基礎(chǔ)排序 計(jì)算機(jī)教學(xué)課件PPT

《程序設(shè)計(jì)基礎(chǔ)排序 計(jì)算機(jī)教學(xué)課件PPT》由會(huì)員分享，可在線閱讀，更多相關(guān)《程序設(shè)計(jì)基礎(chǔ)排序 計(jì)算機(jī)教學(xué)課件PPT（18頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1home back first prev next last 10 排序排序2home back first prev next last 排序排序 外排序外排序 內(nèi)排序內(nèi)排序插入排序插入排序冒泡排序冒泡排序快速排序快速排序3home back first prev next last 排序排序(Sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)關(guān)鍵記錄）的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列。字有序的序列。 例如，例如， 8 3 2 1 7 4 6 5 1 2 3

2、 4 5 6 7 8 4home back first prev next last 內(nèi)排序，指的是待排序記錄存放在計(jì)算機(jī)內(nèi)排序，指的是待排序記錄存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過(guò)程，內(nèi)排序有多種算內(nèi)存中進(jìn)行的排序過(guò)程，內(nèi)排序有多種算法，不同的算法，所用的時(shí)間和內(nèi)存空間法，不同的算法，所用的時(shí)間和內(nèi)存空間也不同也不同 外排序，指的是待排序記錄的數(shù)量很大，外排序，指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序以致內(nèi)存一次不能容納全部記錄，在排序過(guò)程中尚需對(duì)外存如硬盤(pán)進(jìn)行訪問(wèn)的排序過(guò)程中尚需對(duì)外存如硬盤(pán)進(jìn)行訪問(wèn)的排序過(guò)程過(guò)程5home back first prev next las

3、t 插入排序是這樣實(shí)現(xiàn)的：插入排序是這樣實(shí)現(xiàn)的： 1、新建一個(gè)空列表，用于保存已排序的有序數(shù)、新建一個(gè)空列表，用于保存已排序的有序數(shù)列（我們稱(chēng)之為列（我們稱(chēng)之為“有序列表有序列表”）。）。 2、從原數(shù)列中取出一個(gè)數(shù)，將其插入、從原數(shù)列中取出一個(gè)數(shù)，將其插入“有序列有序列表表”中，使其仍舊保持有序狀態(tài)中，使其仍舊保持有序狀態(tài) 3、重復(fù)、重復(fù)2號(hào)步驟，直至原數(shù)列為空。號(hào)步驟，直至原數(shù)列為空。 插入排序的，效率不高，但是容易實(shí)現(xiàn)。它借插入排序的，效率不高，但是容易實(shí)現(xiàn)。它借助了助了逐步擴(kuò)大成果逐步擴(kuò)大成果的思想，使有序列表的長(zhǎng)的思想，使有序列表的長(zhǎng)度逐漸增加，直至其長(zhǎng)度等于原列表的長(zhǎng)度。度逐漸增加，

4、直至其長(zhǎng)度等于原列表的長(zhǎng)度。6home back first prev next last 編程，通過(guò)插入排序，完成編程，通過(guò)插入排序，完成 49 38 65 97 76 13 27 的升序排列的升序排列7home back first prev next last 冒泡排序?qū)儆诮粨Q排序冒泡排序?qū)儆诮粨Q排序 1、將所有待排序的數(shù)字放入工作列表中。、將所有待排序的數(shù)字放入工作列表中。 2、從列表的第一個(gè)數(shù)字到倒數(shù)第二個(gè)數(shù)字，逐、從列表的第一個(gè)數(shù)字到倒數(shù)第二個(gè)數(shù)字，逐個(gè)檢查：若某一位上的數(shù)字大于他的下一位，個(gè)檢查：若某一位上的數(shù)字大于他的下一位，則將它與它的下一位交換。則將它與它的下一位交換。 3

5、、重復(fù)、重復(fù)2號(hào)步驟，直至再也不能交換。號(hào)步驟，直至再也不能交換。 冒泡排序的平均時(shí)間復(fù)雜度與插入排序相同，冒泡排序的平均時(shí)間復(fù)雜度與插入排序相同，也是非常容易實(shí)現(xiàn)的算法也是非常容易實(shí)現(xiàn)的算法8home back first prev next last9home back first prev next last 快速排序（快速排序（Quick sort）是對(duì)冒泡排序的一）是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：種改進(jìn)。它的基本思想是： 通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分部分，其中一部分的所有數(shù)據(jù)都比另外一

6、部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，以此達(dá)到整個(gè)數(shù)據(jù)分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列變成有序序列10home back first prev next last 設(shè)要排序的數(shù)組是設(shè)要排序的數(shù)組是A1AN， 首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，作為關(guān)鍵數(shù)據(jù)， 然后將所有比它小的數(shù)都放到它前面，所有比然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，它大的數(shù)都放到它后面， 這個(gè)過(guò)程稱(chēng)為一趟快速排序。這個(gè)過(guò)程稱(chēng)為一趟快速排序。 值得注意

7、的是，快速排序不是一種穩(wěn)定的排序值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說(shuō)，多個(gè)相同的值的相對(duì)位置也算法，也就是說(shuō)，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)11home back first prev next last 一趟快速排序的算法是：一趟快速排序的算法是： 1）設(shè)置兩個(gè)變量）設(shè)置兩個(gè)變量I、J，排序開(kāi)始的時(shí)候：，排序開(kāi)始的時(shí)候：I=1，J=N； 2）以第一個(gè)元素作為關(guān)鍵數(shù)據(jù)，賦值給）以第一個(gè)元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即，即 key=A1； 3）從）從J開(kāi)始向前搜索，即由后開(kāi)始向前搜索，即每次開(kāi)始向前搜索，即由后開(kāi)始向前搜索，即每次J=

8、J-1，找到第一個(gè)小于，找到第一個(gè)小于key的值的值A(chǔ)J，并與，并與AI交換；交換； 4）從）從I開(kāi)始向后搜索，即由前開(kāi)始向后搜索，即每次開(kāi)始向后搜索，即由前開(kāi)始向后搜索，即每次I=I+1，找到第一個(gè)大于，找到第一個(gè)大于key的的AI，與，與AJ交換；交換； 5）重復(fù)第）重復(fù)第3、4、5步，直到步，直到 I=J12home back first prev next last 例如：待排序的數(shù)組例如：待排序的數(shù)組A的值分別是：的值分別是： 49 38 65 97 76 13 27 初始關(guān)鍵數(shù)據(jù)：初始關(guān)鍵數(shù)據(jù)：X=49 注意注意X在一趟排序中不變，在一趟排序中不變，每次都是和每次都是和X進(jìn)行比較，

9、無(wú)論在什么位置，一趟進(jìn)行比較，無(wú)論在什么位置，一趟排序的目的就是把排序的目的就是把X放在中間，小的放前面，大放在中間，小的放前面，大的放后面。的放后面。 按照第三步從后面開(kāi)始找，第一次交換后：按照第三步從后面開(kāi)始找，第一次交換后：27 38 65 97 76 13 49 第二次交換后：第二次交換后：27 38 49 97 76 13 65 ( 按照第四按照第四步從前面開(kāi)始找步從前面開(kāi)始找X的值，的值，6549,兩者交換兩者交換) 13home back first prev next last 第三次交換后：第三次交換后：27 38 13 97 76 49 65 ( 按照第五按照第五步將又一次

10、執(zhí)行算法的第三步從后開(kāi)始找步將又一次執(zhí)行算法的第三步從后開(kāi)始找 ) 第四次交換后：第四次交換后：27 38 13 49 76 97 65 ( 按照第四按照第四步從前面開(kāi)始找大于步從前面開(kāi)始找大于X的值，的值，9749,兩者交換兩者交換) 此時(shí)再執(zhí)行第三步的時(shí)候就發(fā)現(xiàn)此時(shí)再執(zhí)行第三步的時(shí)候就發(fā)現(xiàn) I=J，從而結(jié)束，從而結(jié)束一趟快速排序一趟快速排序 經(jīng)過(guò)一趟快速排序之后的結(jié)果是：經(jīng)過(guò)一趟快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所有大于，即所有大于49的數(shù)全部在的數(shù)全部在49的后面，所的后面，所有小于有小于49的數(shù)全部在的數(shù)全部在49的前面的前面14home back fi

11、rst prev next last 快速排序就是遞歸調(diào)用此過(guò)程快速排序就是遞歸調(diào)用此過(guò)程在以在以49為中點(diǎn)分為中點(diǎn)分割這個(gè)數(shù)據(jù)序列，分別對(duì)前面一部分和后面一部割這個(gè)數(shù)據(jù)序列，分別對(duì)前面一部分和后面一部分進(jìn)行類(lèi)似的快速排序，從而完成全部數(shù)據(jù)序列分進(jìn)行類(lèi)似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個(gè)有序的的快速排序，最后把此數(shù)據(jù)序列變成一個(gè)有序的序列序列 根據(jù)這種思想對(duì)于上述數(shù)組根據(jù)這種思想對(duì)于上述數(shù)組A的快速排序的全過(guò)程的快速排序的全過(guò)程: 初始狀態(tài)初始狀態(tài) 49 38 65 97 76 13 27 進(jìn)行一次快速排序之后劃分為進(jìn)行一次快速排序之后劃分為 27 38 13

12、 49 76 97 65 分別對(duì)前后兩部分進(jìn)行快速排序分別對(duì)前后兩部分進(jìn)行快速排序 27 38 13 經(jīng)第三步和第四步交換后變成 13 27 38 完成排序 76 97 65 經(jīng)第三步和第四步交換后變成 65 76 97 完成排序 15home back first prev next last 實(shí)踐證明，快速排序是所有排序算法中最高效的實(shí)踐證明，快速排序是所有排序算法中最高效的一種。它采用了分治的思想：先保證列表的前半一種。它采用了分治的思想：先保證列表的前半部分都小于后半部分，然后分別對(duì)前半部分和后部分都小于后半部分，然后分別對(duì)前半部分和后半部分排序，這樣整個(gè)列表就有序了。這是一種半部分排

13、序，這樣整個(gè)列表就有序了。這是一種先進(jìn)的思想，也是它高效的原因。因?yàn)樵谂判蛩阆冗M(jìn)的思想，也是它高效的原因。因?yàn)樵谂判蛩惴ㄖ校惴ǖ母咝c否與列表中數(shù)字間的比較次法中，算法的高效與否與列表中數(shù)字間的比較次數(shù)有直接的關(guān)系，而數(shù)有直接的關(guān)系，而保證列表的前半部分都小于保證列表的前半部分都小于后半部分后半部分就使得前半部分的任何一個(gè)數(shù)從此以后就使得前半部分的任何一個(gè)數(shù)從此以后都不再跟后半部分的數(shù)進(jìn)行比較了，大大減少了都不再跟后半部分的數(shù)進(jìn)行比較了，大大減少了數(shù)字間不必要的比較。數(shù)字間不必要的比較。16home back first prev next last 鏈表鏈表 list 用于存儲(chǔ)待排序的數(shù)據(jù)

14、用于存儲(chǔ)待排序的數(shù)據(jù) 因?yàn)橐驗(yàn)?Scratch 不支持遞歸，因此建立一個(gè)輔不支持遞歸，因此建立一個(gè)輔助的鏈表助的鏈表 sub_seq 用來(lái)記錄生成的子序列的用來(lái)記錄生成的子序列的起始和終止元素的位置起始和終止元素的位置 變量變量 i, j 代表一趟排序的起始和終止元素的代表一趟排序的起始和終止元素的位置位置 變量變量 key 表示一趟排序的關(guān)鍵數(shù)據(jù)表示一趟排序的關(guān)鍵數(shù)據(jù) 變量變量 temp 是臨時(shí)變量，用于鏈表是臨時(shí)變量，用于鏈表 list 第第i, j 元素的交換元素的交換17home back first prev next last18home back first prev next last 排序排序 外排序外排序 內(nèi)排序內(nèi)排序插入排序插入排序冒泡排序冒泡排序快速排序快速排序