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）答案可互換，但兩空全部答對方可得分

return （3）

}

【問題2】(5分)

(1) 假設要排序包含n個元素的數組，請給出在各種不同的劃分情況下，快速排序的時間復雜度，用O記號。最佳情況為 (4)，平均情況為 (5) ，最壞情況為 (6) 。

(2) 假設要排序的n個元素都具有相同值時，快速排序的運行時間復雜度屬于哪種情況? (7) 。(最佳、平均、最壞)

【問題3】(4分)

(1) 待排序數組是否能被較均勻地劃分對快速排序的性能有重要影響，因此樞軸元素的選取非常重要。有人提出從待排序的數組元素中隨機地取出一個元素作為樞軸元素，下面是隨機化快速排序劃分的偽代碼—利用原有的快速排序的劃分操作，請填充其中的空缺處。其中，RANDOM(i,j)表示隨機取i到j之間的一個數，包括i和j。

RANDOMIZED-PARTITION(A,p,r){

i = RANDOM(p,r);

交換(8)和(9);//注：空(8)和空(9)答案可互換，但兩空全部答對方可得分

return PARTITION(A,p,r);

}

(2) 隨機化快速排序是否能夠消除最壞情況的發生? (10) 。(是或否)

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]