以關鍵字序列()為例分別寫出執行以下排序算法的各趟排序結束時關鍵字序列的狀態
() 直接插入排序 ()希爾排序 ()冒泡排序 ()快速排序
() 直接選擇排序 () 堆排序 () 歸並排序 ()基數排序
上述方法中哪些是穩定的排序?哪些是非穩定的排序?對不穩定的排序試舉出一個不穩定的實例
答
()直接插入排序:(方括號表示無序區)
初始態: [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟 [ ]
第七趟 [ ]
第八趟 []
第九趟
()希爾排序(增量為)
初始態:
第一趟
第二趟
第三趟
()冒泡排序(方括號為無序區)
初始態 [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟
()快速排序（方括號表示無序區層表示對應的遞歸樹的層數）
初始態 [ ]
第二層 [ ] [ ]
第三層 [] [ ] [ ]
第四層 [] [ ] []
第五層 []
第六層
()直接選擇排序(方括號為無序區)
初始態 [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟 [ ]
第七趟 [ ]
第八趟 [ ]
第九趟
()堆排序（通過畫二叉樹可以一步步得出排序結果）
初始態 [ ]
建立初始堆 [ ]
第一次排序重建堆[ ]
第二次排序重建堆[ ]
第三次排序重建堆[ ]
第四次排序重建堆[ ]
第五次排序重建堆[ ]
第六次排序重建堆[ ]
第七次排序重建堆[ ]
第八次排序重建堆[ ]
第九次排序重建堆
()歸並排序（為了表示方便采用自底向上的歸並方括號為有序區）
初始態[] [] [] [] [] [] [] [] [] []
第一趟[ ] [ ] [ ] [ ] [ ]
第二趟[ ] [ ] [ ]
第三趟[ ] [ ]
第四趟[ ]
()基數排序（方括號內表示一個箱子共有個箱子箱號從到）
初始態
第一趟[] [ ] [] [] [] [] [] [] [] []
第二趟[] [] [] [ ] [] [] [ ] [] [] []
第三趟[] [] [] [] [] [] [] [ ] [] []
在上面的排序方法中直接插入排序冒泡排序歸並排序和基數排序是穩定的其他排序算法均是不穩定的現舉實例如下以帶*號的表示區別
希爾排序[*]
快速排序[*]
直接選擇排序[*]
堆排序[*]
上題的排序方法中哪些易於在鏈表(包括各種單雙循環鏈表)上實現?
答
上題的排序方法中直接插入排序冒泡排序直接選擇排序基數排序和歸並排序等方法易於在鏈表上實現
當R[lowhigh]中的關鍵字均相同時Partion返回值是什麼?此時快速排序的的運行時間是多少?能否修改Partion使得劃分結果是平衡的(即劃分後左右區間的長度大致相等)?
答
此時Partion 返回值是low此時快速排序的運行時間是
(highlow)(highlow)/=O((highlow)^)可以修改Partion 將其中RecType pivot=R[i];句改為RecType pivot=R[(j+i)/]也就是取中間的關鍵字為基准這樣就能使劃分的結果是平衡的
若文件初態是反序的則直接插入直接選擇和冒泡排序哪一個更好?
答
應選直接選擇排序為更好分析如下
()在直接插入排序算法中反序輸入時是最壞情況此時
關鍵字的比較次數Cmax=(n+)(n)/;
記錄移動次數為Mmax=(n)(n+)/;
Tmax=n^n (以上二者相加)
()在冒泡排序算法中反序也是最壞情況此時
Cmax=n(n)/; Mmax=n(n)/
Tmax=n^n
()在選擇排序算法中
Cmax=n(n)/ Mmax=(n)
Tmax=n^/n/
由此可見雖然它們的時間復雜度都是O(n^)但是選擇排序的常數因子為/因此選擇排序最省時間
若文件初態是反序的且要求輸入穩定則在直接插入直接選擇冒泡和快速排序中就選選哪種方法為宜?
答
這四種排序算法中直接選擇快速排序均是不穩定的因此先予以排除剩下兩種算法中由於直接插入算法所費時間比冒泡法更少(見上題分析)因此選擇直接排序算法為宜
有序數組是堆嗎?
答
有序數組是堆因為有序數組中的關鍵字序列滿足堆的性質若數組為降序則此堆為大根堆反之為小根堆
高度為h的堆中最多有多少個元素?最少有多少個元素?在大根堆中關鍵字最小的元素可能存放在堆的哪些地方?
答
高度為h的堆實際上為一棵高度為h的完全二叉樹因此根據二叉樹的性質可以算出它最少應有h個元素最多可有h個元素(注意一個有括號一個沒有)在大根堆中關鍵字最小的元素可能存放在堆的任一葉子結點上
判別下列序列是否為堆(小根堆或大根堆)若不是則將其調整為堆
() ();
() ();
() ();
() ()
答
堆的性質是任一非葉結點上的關鍵字均不大於(或不小於)其孩子結點上的關鍵字據此我們可以通過畫二叉樹來進行判斷和調整
() 此序列是大根堆
From:http://tw.wingwit.com/Article/program/sjjg/201311/23742.html
