題目描述
在上一題中，實作了完整的快速排序法，能成功將一個陣列排序完成。但是這個演算法在劃分的時候需要將元素儲存到新的陣列中，浪費了許多時間和空間。為了進行優化，我們必須替快速排序法實作出一個「原地」(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小的元素皆要從同一方向開始(向左)，所以需要做一些小改變。
參考答案
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);
}
}