數(shù)據(jù)結(jié)構(gòu)10排序PPT學(xué)習(xí)教案

1、會計學(xué)1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)10排序排序 第1頁/共51頁 姓名年齡 體重 爾康 1 87 0 紫薇 1 64 8 五阿哥 1 76 0 小燕子 1 65 0 乾隆 4 07 0 原始數(shù)據(jù) 姓名年齡 體重 紫薇 1 64 8 小燕子1 6 5 0 五阿哥1 7 6 0 爾康 1 87 0 乾隆 4 07 0 按年齡排序(穩(wěn)定？) 姓名年齡體重 小燕子 1 65 0 紫薇 1 64 8 五阿哥 1 76 0 爾康 1 87 0 乾隆 4 07 0 按年齡排序(不穩(wěn)定) 第2頁/共51頁 第3頁/共51頁 第4頁/共51頁 時間復(fù)雜度空間復(fù)雜度時間復(fù)雜度空間復(fù)雜度 構(gòu)造平衡的構(gòu)造平衡的 二叉排序樹二

2、叉排序樹 O(nlogn) 注意：一趟排序(插入 元素)的時間復(fù)雜度 為：O(logn) O(logn)O(logn)O(logn) 排序方法 排序查找 第5頁/共51頁 趟次 4 93 86 59 77 6 13 2 74 9 * - - - - - - 1 13 4 93 86 59 77 6 27 4 9 * 21 3 27 4 9 38 6 59 77 6 49 * 31 32 7 38 4 9 49 * 6 59 7 76 41 32 73 84 94 9 * 6 5 76 9 7 注意：第5趟沒有交換操作，排序結(jié)束。 第6頁/共51頁 第2趟 1 3 27 4 9 38 6 59

3、77 6 49 * 第3趟 1 32 7 38 4 9 49 * 6 59 7 76 第7頁/共51頁 第2趟 1 3 27 4 9 38 6 59 77 6 49 * 第3趟 1 32 7 38 4 9 49 * 6 59 7 76 第8頁/共51頁 問題：如何增加交換的跨度以提高性能？ 第9頁/共51頁 -1-234-3-212 p - -1-2-334 low - high - 比較n次，移動2n次，空間2n -1-23-34-1-22 p - -1-2-343 low - - high 比較n次，最多移動n+1次，空間1 第13頁/共51頁 第14頁/共51頁 或為if(lowhigh

4、) L.rlow+ = L.rhigh; 但 不能省略if判斷，否則上一句while循環(huán)最 后是執(zhí)行high時，返回的low值有問題 注意不能省略兩處比較 中的等號，否則死循環(huán) 第15頁/共51頁 第16頁/共51頁 第17頁/共51頁 趟次 49 3 86 59 77 6 13 2 74 9 * 1 1338 6 59 77 6 4927 4 9 * 21 32 7 65 9 77 64 9 38 4 9 * 31 32 73 8 97 7 6 49 6 54 9 * 41 32 73 84 9 76 9 76 5 49 * 51 32 73 84 94 9 * 9765 7 6 61 32

5、 73 84 94 9 * 6 5 9776 71 32 73 84 94 9 * 6 57 6 97 第18頁/共51頁 第2趟 1 32 7 65 9 77 64 9 38 4 9 * 第3趟 1 32 73 8 97 7 6 49 6 54 9 * 第19頁/共51頁 第20頁/共51頁 問題：如何提高選擇的速度以提高性能？ 第21頁/共51頁 第22頁/共51頁 注意該方法與通過構(gòu)造二叉排序樹來排序不同 (二叉排序樹的非終端結(jié)點存儲有真正的記錄) 第23頁/共51頁 第24頁/共51頁 答：是，小頂堆答：是，小頂堆 提問：序列提問：序列123456是堆嗎？是堆嗎？ 第25頁/共51頁

6、第26頁/共51頁 注：排序思路按圖示過程不斷對小頂堆小頂堆 進(jìn)行輸出堆調(diào)整，各趟堆調(diào)整全部結(jié)束以后 ，整個序列將變成一個從大到小的有序序列從大到小的有序序列 。 第27頁/共51頁 第28頁/共51頁 4 7 5 6 356 s jj+1 rc 第29頁/共51頁 第30頁/共51頁 第31頁/共51頁 趟次 4 93 86 59 77 61 32 74 9 * 4 9 38 6 59 77 61 32 74 9 * 1 38 4 9 65 9 77 61 32 74 9 * 23 84 9 6597 7 61 32 74 9 * 33 84 96 5 9776 1 32 74 9 * 43

7、 84 96 5 76 9 7 13 2 74 9 * 5 13 3 84 96 57 69 7 27 4 9 * 61 3 27 3 84 96 57 69 7 49 * 71 32 73 84 9 49 * 6 57 69 7 第32頁/共51頁 第33頁/共51頁 第34頁/共51頁 第35頁/共51頁 第36頁/共51頁 趟次 4 93 86 59 77 61 32 74 9 * 5 54 4 91 3 3 82 7 6 54 9 * 9 75 5 7 64 1327 4 9 * 554 4 9 3865 9 7 76 2 (增量3 ) 134 4 9 * 3827 4 9 5565

8、9 7 76 3 (增量1 ) 41 32 73 84 9 * 4 95 56 57 69 7 1 (增量5 ) 第37頁/共51頁 第38頁/共51頁 第39頁/共51頁 趟次 4938 6 59 7 7613 2 74 9 * 13 84 96 59 71 37 62 74 9 * 23 84 96 59 71 32 74 9 * 7 6 31 32 73 84 94 9 * 6 57 69 7 第40頁/共51頁 第41頁/共51頁 第42頁/共51頁 第43頁/共51頁 第44頁/共51頁 第45頁/共51頁 最好時間 性能 平均時間 性能 最壞時間 性能 平均輔助 空間 穩(wěn)定性 O

9、(n lo g n )O (n lo g n )O (n lo g n ) O(logn) 穩(wěn)定穩(wěn)定 冒泡排序 O (n ) O (n 2 )O (n 2 ) O (1 ) 穩(wěn)定 快速排序 O (n lo g n )O (n lo g n ) O (n 2 ) O(logn) 不穩(wěn)定 簡單選擇排序 O (n 2 )O (n 2 )O (n 2 ) O (1 ) 不穩(wěn)定不穩(wěn)定 /穩(wěn)定 穩(wěn)定* 堆排序 O (n lo g2n )O (n lo g2n ) O (n lo g n )O (1 ) 不穩(wěn)定 插入直接插入排序 O (n ) O (n 2 )O (n 2 ) O (1 ) 穩(wěn)定 排序希爾排序 -約O (n 1 .3 ) -O (1 ) 不穩(wěn)定 O (n lo g n )O (n lo g n )O (n lo g n ) O(n) 穩(wěn)定穩(wěn)定 (基于鏈隊)O (m n )O (m n )