軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2023/7/18）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2023/7/18

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2023/7/18）

試題四
閱讀下列說明，回答問題1至問題3，將解答填入對(duì)應(yīng)欄內(nèi)。
【說明】
快速排序是一種典型的分治算法。采用快速排序?qū)?shù)組A[p..r]排序的3個(gè)步驟如下。
1．分解：選擇一個(gè)樞軸(pivot)元素劃分?jǐn)?shù)組。將數(shù)組A[p..r]劃分為兩個(gè)子數(shù)組 (可能為空)A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1)中的每個(gè)元素，小于 A[q+1..r]中的每個(gè)元素。q的值在劃分過程中計(jì)算。
2．遞歸求解：通過遞歸的調(diào)用快速排序，對(duì)子數(shù)組A[p..q-1]和A[q+1..r]分別排序。
3．合并：快速排序在原地排序，故不需合并操作。
【問題1】
下面是快速排序的偽代碼，請?zhí)钛a(bǔ)其中的空缺；偽代碼中的主要變量說明如下。
A：待排序數(shù)組
p，r: 數(shù)組元素下標(biāo)，從p到r
q: 劃分的位置
x：樞軸元素
i：整型變量，用于描述數(shù)組下標(biāo)。下標(biāo)小于或等于i的元素的值小于或等于樞軸元素的值
j：循環(huán)控制變量，表示數(shù)組元素下標(biāo)
QUICKSORT (A，p，r){
if  (p ＜r){
q=PARTITION(A，p，r) ；
QUICKSORT(A，p，q-1)；
QUICKSORT(A，q+1，r)；
}
}
PARTITION(A，p，r){
x=A[r]；i=p-1；
for(j=p；j≤r-1；j++){
if  (A[j]≤x){
i=i+1；
交換A[i]和A[j]
}
}
交  (1)  和  (2)  //注：空(1)和空(2)答案可互換，但兩空全部答對(duì)方可得分 return   (3)
}
【問題2】
(1)假設(shè)要排序包含n個(gè)元素的數(shù)組，請給出在各種不同的劃分情況下，快速排序的時(shí)間復(fù)雜度，用O記號(hào)。最佳情況為  (4)  ，平均情況為  (5)  ，最壞情況為  (6)  。
(2)假設(shè)要排序的n個(gè)元素都具有相同值時(shí)，快速排序的運(yùn)行時(shí)間復(fù)雜度屬于哪種情況?  (7)  。(最佳，平均、最壞)
【問題3】
(1)待排序數(shù)組是否能被較均勻地劃分對(duì)快速排序的性能有重要影響，因此樞軸元素的選取非常重要。有人提出從待排序的數(shù)組元素中隨機(jī)地取出一個(gè)元素作為樞軸元素，下面是隨機(jī)化快速排序劃分的偽代碼——利用原有的快速排序的劃分操作，請?zhí)畛淦渲械目杖碧?。其中，RANDOM(i，j)表示隨機(jī)取i到j(luò)之間的一個(gè)數(shù)，包括i和j。
RANDOMIZED- PARTITION(A，p，r){
i=RANDOM(p，rl)；
交換  (8)  和  (9)  ；//注：空(8)和空(9)答案可互換，但兩空全部答對(duì)方可得分
return PARTITION (A，p，r)；
}
(2)隨機(jī)化快速排序是否能夠消除最壞情況的發(fā)生?  (10)  。(是或否)