[HackerRank]快速排序3─原地的快速排序法(Quicksort In-Place)

題目描述

在上一題中，實作了完整的快速排序法，能成功將一個陣列排序完成。但是這個演算法在劃分的時候需要將元素儲存到新的陣列中，浪費了許多時間和空間。為了進行優化，我們必須替快速排序法實作出一個「原地」(in-place)的版本，讓它能夠只使用陣列自身的空間來完成排序。

與前兩題有些差異的地方是，這題的支點p不是p=ar[0]，而是p=ar[len(ar) - 1]。

原題網址

輸入格式

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

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

輸出格式

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

範例輸入

範例輸出

額外解釋

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