題目描述
在上一題中,你已經知道如何將一個集合劃分為left(左邊)、right(右邊)或是equal(相等)三個集合了。你能夠重複進行劃分的動作,來完成整個集合的排序嗎?
原題網址
輸入格式
輸入第一行為一個整數n,範圍在1到1000之間(包含1和1000)。
第二行為n個用空格分隔的整數,範圍在-1000到1000之間(包含-1000和1000),不會重複。
輸出格式
將劃分過的子陣列輸出成新的一行。
範例輸入
7
5 8 1 3 7 9 2
5 8 1 3 7 9 2
範例輸出
2 3
1 2 3
7 8 9
1 2 3 5 7 8 9
1 2 3
7 8 9
1 2 3 5 7 8 9
額外解釋
[5, 8, 1, 3, 7, 9, 2]:支點是「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」。
[5, 8, 1, 3, 7, 9, 2]此時已被排序成[1, 2, 3, 5, 7, 8, 9]:輸出「1 2 3 5 7 8 9」。
解題概念
將上一題撰寫出來的程式,另外做成一個「quickSort」方法,把原本劃分出來的left和right部份再去呼叫「quickSort」方法進行遞迴處理。在每次的「quickSort」方法結束執行時,印出目前正在處理的陣列範圍所包含的元素。
有關於快速排序法的詳細介紹可以參考這篇文章:
參考答案
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 quickSort(final int A[], final int start, final int end) {
final ArrayList<Integer> left = new ArrayList<>();
final ArrayList<Integer> right = new ArrayList<>();
final int p = A[start];
for (int i = start + 1; i < end; i++) {
final int e = A[i];
if (e <= p) {
left.add(e);
} else {
right.add(e);
}
}
final int ls = start;
final int le = ls + left.size();
final int rs = le + 1;
final int re = rs + right.size();
left.add(p);
left.addAll(right);
int i = start;
for (final int n : left) {
A[i++] = n;
}
if (le - ls > 1) {
quickSort(A, ls, le);
}
if (re - rs > 1) {
quickSort(A, rs, re);
}
if (end - start > 1) {
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);
}
}