Q1. Quick Sort是什麼
- 先從一串要排序的資料中,找出一個值,將他定為 Pivot
- 然後比 pivot 小的放左邊,比 pivot 大的放右邊
- 排序好一輪 pivot 的位置就會固定下來,重複第1與第2步驟,從剩下的數字選 pivot,將比較小的放左邊,比較大的放右邊
- 所以 Quick Sort 在實作上,有兩個要考慮的重點
- 在排序上,可能會有極端狀況導致效能不佳,所以 pivot 有很多選法:
a. 每次選第一個元素
b. 每次選最後一個元素
c. 選擇特定位置(如中位數)的元素
d. 隨機選擇任意元素
- 假設有一個序列恰好「已/接近排序完成」,此時若選擇 第一個或是最後一個元素 作為 pivot,則會遇到極端情況,每次都要比較 N、N-1、N-2 .... 個數字
- 若是能夠選擇中位數做為 pivot ,那麼就只要比較 N/2 與 N/2-1 的數量,類似二分搜的概念
- 如何將比較小的排左邊,比較大的排右邊,算法主要分為兩種:
- Lomuto (較易實作與理解,常被做為教材,所以網路上教學文章主要都是使用此種方法)
- 排序方法:
- Lomuto 的 pivot 時常選定最後一個
- 會有兩個指標指向開始
-
- 指針分別:
- j 指標專門停在比 pivot 大的位置
- k 指標專門在 j 指標停之後(遇到比 pivot 大的值後),停在比 pivot 小的位置
- 當 k 與 j 指標都停止後,兩者的值就會做交換
-
-
- 你會發現,比 pivot 大的數字,逐漸被往後放,最終 pivot 左邊都是比較小的,右邊都是比 pivot 大的值
- Lomuto 影片連結:https://www.youtube.com/watch?v=86WSheyr8cM
- Hoare (效率比 Lomuto 更好一些,交換次數更少)
- 排序方法
- Hoare 的 pivot 時常選定中位數
- 會有兩個指標,一個指向開始,一個指向結尾
-
- 指針分別:
- k 指標逐漸往後,專門停在比 pivot 大的數字
- j 指標逐漸往前,專門停在比 pivot 小的數字
- 當 k 與 j 指標都停止後,兩者的值就會做交換 (把大的丟到右邊,把小的丟到左邊)
-
- Hoare 影片連結:https://www.youtube.com/watch?v=NuQYFXmLUrM
Q2. 學會 Quick Sort 可以做什麼?
- 生活中時常會需要使用到排序好的資料 (尤其是可以處理資料量相對較多的),例如
Lab. 明天要解的題目:912. Sort an Array
-
題目連結:https://leetcode.com/problems/sort-an-array/
-
我們上次使用 bubble sort 的算法解這一題,但是發現會效率不高,會出現 Time Limit Exceeded 的情況,我們這次使用今天介紹的 Quick Sort 的方法來解這一題
-
為了避免新加入的讀者需要往前翻題目,我們再將題目敘述一遍:
-
題目敘述:
- 會有一個 nums 變數,裡面儲存著要排序的內容,我們要將內容由小到大進行排序
-
-
測資的 Input/Output:
- 會拿到 nums 的變數,須回傳排序好的資料
-
-
題目的條件:
- 可能會有 1~ 50000 個數字要進行排序
- 每個數字會在 - 0.0005 ~ 50000 之間
-
-
看完題目你需要思考的是:
- 使用 Quick sort 這個算法,會不會可能造成超時?
- 有沒有其他排序方法可以使用 ?