重要題型整理：數據結構與算法——內排序

1. （數據結構與算法mooc）須要對1000個大型的記錄進行排序，記錄自己存儲在外存中，在內存中只保存了全部記錄的排序碼。排序碼之間的比較很是快，可是移動代價很大，由於一旦移動一個排序碼，相應的外存中的記錄也要移動，將涉及上百個磁盤塊的移動，應該使用何種排序方法( )
   A.堆排序 B.直接選擇排序 C.插入排序 D.快速排序

解析：Bhtml

• 堆排序：本質上是利用最大最小堆的直接選擇排序，可是建堆等過程要移來移去
• 直接選擇排序：每次直接從後面部分的元素中選擇最小的放到第i位，不用移動其餘元素
• 插入排序：每次都是相對順序，插入位置後面元素要日後移
• 快速排序：每輪肯定一個元素的位置，雖然和直接選擇排序同樣該元素能夠直接肯定，但肯定的過程當中多出了左右兩側元素比較的步驟

2. （數據結構與算法mooc）某整型數組Ａ的１０個元素值依次爲6,2,9,7,3,8,4,5,0,1,用快速排序方法（課程中介紹的快速排序實現方式），取第一個元素值６做爲分割數，將Ａ中元素由小到大排序，寫出快速排序第一次分隔後Ａ中的結果()。數字中間用一個空格隔開。

解析：1 2 0 5 3 4 6 8 7 9
快排的基礎練習，暴力對照算法web

參考的圖：算法

3. （數據結構與算法mooc）排序算法大都是基於數組實現的，大部分的算法也能用鏈表來實現，但有些特殊的算法不適合線性鏈表存儲，不適合（使算法複雜度增大）鏈式存儲的算法有()
   得分/總分
   A. 堆排序 B. 快速排序 C.shell排序 D.歸併排序

解析：AC
堆排序和shell排序都須要隨機訪問，依賴下標等shell

4. （數據結構與算法mooc）已知一組元素的排序碼爲(67, 34, 56, 12, 88, 3, 15, 36, 27, 98, 11, 55)，利用自頂向下劃分的非優化歸併排序方法（劃分到小於等於2個元素），寫出第二趟二路歸併排序後的結果()。中間用一個空格隔開。

解析：3 12 34 56 67 88 11 15 27 36 55 98
注意這裏不是兩兩排序就能夠了的，依據算法是逐步對半分的，因此最後分組結果爲1,2,1,2……第一趟二路歸併後就是3,3,3,3
此題中強調了「自頂向下」而若是是「自底向上」二路歸併則分爲2+2+2+……數組

5. （數據結構與算法mooc）如下排序算法中，不須要比較待排序記錄關鍵碼的算法是：
   A.基數排序 B.冒泡排序 C.堆排序 D. 直接選擇排序

解析：A數據結構

6. （書面做業）給定數組 A[1,…,n]，在空間複雜度 O(1) 的條件下實現歸併排序（時間複雜度儘量小）。給出算法流程，並分析時間複雜度。

解析：（手搖算法，三重反轉算法）
1）指針 i 指向左子段的開頭，指針 j 指向右子段的開頭。
2）i 指針不斷向後移動，直到找到第一個比 j 指向的元素大的元素或者直到和 j 相遇。
3）index 指針先代替 j 指向右端的第一個元素。
4）j 指針不斷向後移動，直到找到第一個比 i 指向元素大的元素或者直到遇到數組的末尾。
5）將 [i, index) 段和 [index, j) 段進行內存反轉（手搖算法），以後將 i 移動 j-index+1 空位。以 i 開始的子序列和以j開始的子序列又是最初的問題模型，因此繼續上述操做（一旦i、j相遇或者j到達末尾，在該操做 5 結束後直接結束算法）
手搖算法：經過逆序完成位置轉換：反轉前一段->反轉後一段->總體反轉app

時間複雜度：
（空間O(1)但要犧牲時間）
最好的狀況：左子段和右子段直接所有交換，手搖算法時間複雜度O(n)，此時原地歸併的複雜度仍是 O(nlogn)
最壞的狀況：一段一段的緩慢前進的狀況，手搖算法時間複雜度 $O(n^2)$,原地歸併的複雜度就是 $O(n^2log n)$svg