藍橋杯——快速排序（2018JavaB組第5題9分）

快速排序（18JavaB5,9’）

以下代碼可以從數組a[]中找出第k小的元素。

它使用了類似快速排序中的分治算法，期望時間復雜度是O(N)的。

請仔細閱讀分析源碼，填寫劃線部分缺失的內容。

import java.util.Random;
public class Main{public static int quickSelect(int a[], int l, int r, int k) {Random rand = new Random();int p = rand.nextInt(r - l + 1) + l;int x = a[p];int tmp = a[p]; a[p] = a[r]; a[r] = tmp;int i = l, j = r;while(i < j) {while(i < j && a[i] < x) i++;if(i < j) {a[j] = a[i];j--;}while(i < j && a[j] > x) j--;if(i < j) {a[i] = a[j];i++;}}a[i] = x;p = i;if(i - l + 1 == k) return a[i];if(i - l + 1 < k) return quickSelect( _________________________________ ); //填空else return quickSelect(a, l, i - 1, k);    }public static void main(String args[]) {int [] a = {1, 4, 2, 8, 5, 7};System.out.println(quickSelect(a, 0, 5, 4));}
}

注意：只提交劃線部分缺少的代碼，不要抄寫任何已經存在的代碼或符號。

---

先看看典型的快速排序

快速排序

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序

它采用了一種分治(Divide-and-ConquerMethod)的策略

基本思想

1．先從數列中取出一個數作為基準數。

2．分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。

3．再對左右區間重復第二步，直到各區間只有一個數。

先把基準值（最左）存起來

高位（右）大的往左邊拉

低位（左）小的往右邊拉

最后，存的那個基準值（曾經最左）放中間

對左：相同處理

對右：相同處理

package bb;
public class QuickSortMy {static void printArray(int a[]) {for (int i : a) {System.out.print(i + "\t");}System.out.println();}static void qsort(int a[], int left, int right) {if (left >= right) {return;}printArray(a);int key = a[left];int i = left, j = right;while (i < j) {while (i < j && a[j] > key) {j--;}if (i < j) {System.out.printf("a[%d]=%d <- a[%d]=%d\n", i, a[i], j, a[j]);a[i++] = a[j];}while (i < j && a[i] < key) {i++;}if (i < j) {System.out.printf("a[%d]=%d -> a[%d]=%d\n", i, a[i], j, a[j]);a[j--] = a[i];}}a[i] = key;printArray(a);qsort(a, left, i - 1);qsort(a, i + 1, right);}public static void main(String[] args) {int a[] = { 3, 4, 5, 1, 2 };qsort(a, 0, a.length - 1);}
}

---

2018JavaB組第5題的參考答案+注釋如下所示：

package bb;
import java.util.Random;
public class JB18_5快速排序 {public static int quickSelect(int a[], int l, int r, int k) {Random rand = new Random();int p = rand.nextInt(r - l + 1) + l;int x = a[p];int tmp = a[p];a[p] = a[r];a[r] = tmp;int i = l, j = r;while (i < j) {while (i < j && a[i] < x)i++;if (i < j) {a[j] = a[i];j--;}while (i < j && a[j] > x)j--;if (i < j) {a[i] = a[j];i++;}}a[i] = x;p = i;if (i - l + 1 == k)// (1)說明到底了return a[i];if (i - l + 1 < k)return quickSelect(a, i + 1, r, k - i + l - 1); // 填空// qsort(a, i + 1, right);// (3)先試試k，// (4)再考慮：k要移動到等于（i - l + 1），試試k-(i - l + 1)else// i - l + 1 > kreturn quickSelect(a, l, i - 1, k);// (2)qsort(a, left, i -// 1);對上了，k不變}public static void main(String args[]) {int[] a = { 1, 4, 2, 8, 5, 7 };System.out.println(quickSelect(a, 0, 5, 4));// int [] a = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12, 2};// System.out.println(quickSelect(a, 0, a.length-1, 6));}
}