題目描述

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



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

原題網址

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

輸入格式

輸入第一行為一個整數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」。

解題概念

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

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

這題所使用的快速排序法與上面連結的文章有點不太一樣,搜尋比pivot大和比pivot小的元素皆要從同一方向開始(向左),所以需要做一些小改變。

參考答案