以關鍵字序列(
)為例
分別寫出執行以下排序算法的各趟排序結束時
關鍵字序列的狀態
(
) 直接插入排序 (
)希爾排序 (
)冒泡排序 (
)快速排序
(
) 直接選擇排序 (
) 堆排序 (
) 歸並排序 (
)基數排序
上述方法中
哪些是穩定的排序?哪些是非穩定的排序?對不穩定的排序試舉出一個不穩定的實例
上題的排序方法中哪些易於在鏈表(包括各種單雙循環鏈表)上實現?
當R[lowhigh]中的關鍵字均相同時Partion返回值是什麼?此時快速排序的的運行時間是多少?能否修改Partion使得劃分結果是平衡的(即劃分後左右區間的長度大致相等)?
若文件初態是反序的則直接插入直接選擇和冒泡排序哪一個更好?
若文件初態是反序的且要求輸入穩定則在直接插入直接選擇冒泡和快速排序中就選選哪種方法為宜?
有序數組是堆嗎?
高度為h的堆中最多有多少個元素?最少有多少個元素?在大根堆中關鍵字最小的元素可能存放在堆的哪些地方?
判別下列序列是否為堆(小根堆或大根堆)若不是則將其調整為堆
() ();
() ();
() ();
() ()
將兩個長度為n的有序表歸並為一個長度為n的有序表最小需要比較n次最多需要比較n次請說明這兩種情況發生時兩個被歸並的表有何特征?
設關鍵字序列為()給出桶排序的結果
若關鍵字是非負整數快速排序歸並堆和基數排序啊一個最快?若要求輔助空間為O()則應選擇誰? 若要求排序是穩定的且關鍵字是實數則應選擇誰?
對於節的表解釋下述問題
()當待排序的關鍵字序列的初始態分別為正序和反序時為什麼直接選擇排序的時間基本相同?若采用本書節的算法這兩種情況下的排序時間是否基本相同?
()為什麼數組的初態為正序時冒泡和直接插入排序的執行時間最少?
()若采用節的快速排序則數組初態為正序和反序時能得到與表類似的結果嗎?
From:http://tw.wingwit.com/Article/program/sjjg/201311/23760.html
