[HackerRank]快速排序2─排序(Quicksort 2 - Sorting)

題目描述

在上一題中，你已經知道如何將一個集合劃分為left(左邊)、right(右邊)或是equal(相等)三個集合了。你能夠重複進行劃分的動作，來完成整個集合的排序嗎？

原題網址

輸入格式

輸入第一行為一個整數n，範圍在1到1000之間(包含1和1000)。

第二行為n個用空格分隔的整數，範圍在-1000到1000之間(包含-1000和1000)，不會重複。

輸出格式

將劃分過的子陣列輸出成新的一行。

範例輸入

範例輸出

額外解釋

[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);
    }
}