題目描述
在上一題中，實作了完整的快速排序法，能成功將一個陣列排序完成。但是這個演算法在劃分的時候需要將元素儲存到新的陣列中，浪費了許多時間和空間。為了進行優化，我們必須替快速排序法實作出一個「原地」(in-place)的版本，讓它能夠只使用陣列自身的空間來完成排序。
與前兩題有些差異的地方是，這題的支點p不是p=ar[0]，而是p=ar[len(ar) - 1]。
原題網址
輸入格式
輸入第一行為一個整數n，範圍在1到1000之間(包含1和1000)。
第二行為n個用空格分隔的整數，範圍在-1000到1000之間(包含-1000和1000)，不會重複。
輸出格式
將劃分過的子陣列輸出成新的一行。
範例輸入
7
1 3 9 8 2 7 5
範例輸出
1 3 2 5 9 7 8
1 2 3 5 9 7 8
1 2 3 5 7 8 9
額外解釋
[1, 3, 9, 8, 2, 7, 5]：支點是「5」，可以被劃分成[1, 3, 2](left)、[5](equal)和[8, 7, 9](right)。
[1, 3, 2]：支點是「1」，可以被劃分成[3, 2](left)、[1](equal)。
[3, 2]：支點是「3」，可以被劃分成[2](left)、[3](equal)。因此將輸出「2 3」。
[1, 3, 2]此時已被排序成[1, 2, 3]：輸出「1 2 3」。
[8, 7, 9]：支點是「8」，可以被劃分成[7](left)、[8](equal)、[9](right)。因此將輸出「7 8 9」。
[8, 1, 3, 7, 9, 2, 5]此時已被排序成[1, 2, 3, 5, 7, 8, 9]：輸出「1 2 3 5 7 8 9」。
解題概念
有關於快速排序法的詳細介紹可以參考這篇文章：
這題所使用的快速排序法與上面連結的文章有點不太一樣，搜尋比pivot大和比pivot小的元素皆要從同一方向開始(向左)，所以需要做一些小改變。
參考答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | import java.util.*; public class Solution { private static void printArray(final int A[], final int a, final int b) { final StringBuilder sb = new StringBuilder(); for (int i = a; i < b; ++i) { sb.append(A[i]).append(' '); } System.out.println(sb.toString().trim()); } private static void swap(final int[] A, final int a, final int b) { final int tmp = A[a]; A[a] = A[b]; A[b] = tmp; } private static void quickSort(final int A[], final int start, final int end) { final int[] stack = new int[end - start + 1]; // 建立堆疊空間。因為又把上一題的遞迴版本改為迭代版本，因此需要額外的堆疊空間來儲存陣列分割的位置。這樣的方式依然算是「原地的」快速排序法。 int top = -1; int s, e; stack[++top] = start; stack[++top] = end - 1; while (top >= 0) { e = stack[top--]; s = stack[top--]; final int x = A[e]; // pivot int a = s; int b; int c; while (a < e && A[a] <= x) { ++a; } b = a; c = b; int d = 0; while (c < e && A[c] >= x) { ++c; if (A[c] < x && c < e) { swap(A, b + d++, c); } } final int f = b + d; if (f < e) { swap(A, f, e); } final int ls = s, le = f - 1; final int rs = f + 1, re = e; final int ll = le - ls + 1, rl = re - rs + 1; if (rl > 1) { stack[++top] = rs; stack[++top] = re; } if (ll > 1) { stack[++top] = ls; stack[++top] = le; } printArray(A, start, end); } } public static void main(final String[] args) { final Scanner in = new Scanner(System.in); final int n = in.nextInt(); final int[] A = new int[n]; for (int i = 0; i < n; ++i) { A[i] = in.nextInt(); } quickSort(A, 0, n); } } |
