題目描述

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



原題網址

https://www.hackerrank.com/challenges/quicksort2/

輸入格式

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

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

輸出格式

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

範例輸入

7
5 8 1 3 7 9 2

範例輸出

2 3
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」方法結束執行時,印出目前正在處理的陣列範圍所包含的元素。

有關於快速排序法的詳細介紹可以參考這篇文章:

https://magiclen.org/sorting-algorithm/

參考答案