相關文章：

2008年上半年軟件設計師上午試卷I

2008年上半年軟件設計師上午試卷II

2008年上半年軟件設計師下午試卷I

試題四(共15分)

閱讀下列說明，回答問題1至問題3，將解答填入答題紙的對應欄內。

【說明】

快速排序是一種典型的分治算法。采用快速排序對數組A[p..r]排序的三個步驟如下:

分解：選擇一個樞軸(pivot)元素劃分數組。將數組A[p..r]劃分為兩個子數組(可能為空) A[p..q-1]和A[q+1..r]，使得A[q]大于等于A[p..q-1]中的每個元素，小于A[q+1..r]中的每個元素。q的值在劃分過程中計算。

遞歸求解：通過遞歸的調用快速排序，對子數組A[p..q-1]和A[q+1..r]分別排序。

合并：快速排序在原地排序，故不需合并操作。

【問題1】(6 分)

下面是快速排序的偽代碼，請填補其中的空缺。偽代碼中的主要變量說明如下：

A：待排序數組

p, r：數組元素下標，從p到r

q：劃分的位置

x：樞軸元素

i：整型變量，用于描述數組下標。下標小于或等于i的元素的值小于或等于樞軸元素的值

j：循環控制變量，表示數組元素下標

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