iT邦幫忙

2021 iThome 鐵人賽

DAY 8
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 8

【第八天 - Quick Sort 介紹】

Q1. Quick Sort是什麼

  • 與前天介紹的 bubble sort 一樣,是一種計算排序的方法,但是此種演算法比起 bubble sort 平均所花費的時間更少

  • 時間複雜
    (表格來源 https://www.runoob.com/w3cnote/ten-sorting-algorithm.html )

  • 時間複雜度,越小代表效率越好,關於詳細的時間複雜度,可以參考此篇文章:https://ithelp.ithome.com.tw/articles/10203082

  • Quick Sort 擁有許多種變形,所以在網路上找相關文章時,有些文章 Quick Sort 方式有些微不同,但是他們整體概念基本上都是

  1. 先從一串要排序的資料中,找出一個值,將他定為 Pivot
    選pivot
  2. 然後比 pivot 小的放左邊,比 pivot 大的放右邊
    比較小的放左,大的放右
  3. 排序好一輪 pivot 的位置就會固定下來,重複第1與第2步驟,從剩下的數字選 pivot,將比較小的放左邊,比較大的放右邊
    重複1與2
  • 所以 Quick Sort 在實作上,有兩個要考慮的重點
    1. 在排序上,可能會有極端狀況導致效能不佳,所以 pivot 有很多選法:
      a. 每次選第一個元素
      b. 每次選最後一個元素
      c. 選擇特定位置(如中位數)的元素
      d. 隨機選擇任意元素
      • 假設有一個序列恰好「已/接近排序完成」,此時若選擇 第一個或是最後一個元素 作為 pivot,則會遇到極端情況,每次都要比較 N、N-1、N-2 .... 個數字
        • N-1
      • 若是能夠選擇中位數做為 pivot ,那麼就只要比較 N/2 與 N/2-1 的數量,類似二分搜的概念
        • 中位數 pivot
    2. 如何將比較小的排左邊,比較大的排右邊,算法主要分為兩種:
      • Lomuto (較易實作與理解,常被做為教材,所以網路上教學文章主要都是使用此種方法)
        • 排序方法:
          • Lomuto 的 pivot 時常選定最後一個
          • 會有兩個指標指向開始
          • 兩個指標
          • 指針分別:
            • j 指標專門停在比 pivot 大的位置
            • k 指標專門在 j 指標停之後(遇到比 pivot 大的值後),停在比 pivot 小的位置
            • 當 k 與 j 指標都停止後,兩者的值就會做交換
            • Lo 1
            • Lo 2
          • 你會發現,比 pivot 大的數字,逐漸被往後放,最終 pivot 左邊都是比較小的,右邊都是比 pivot 大的值
          • Lomuto 影片連結:https://www.youtube.com/watch?v=86WSheyr8cM
        • Hoare (效率比 Lomuto 更好一些,交換次數更少)
          • 排序方法
            • Hoare 的 pivot 時常選定中位數
            • 會有兩個指標,一個指向開始,一個指向結尾
            • start
          • 指針分別:
            • k 指標逐漸往後,專門停在比 pivot 大的數字
            • j 指標逐漸往前,專門停在比 pivot 小的數字
            • 當 k 與 j 指標都停止後,兩者的值就會做交換 (把大的丟到右邊,把小的丟到左邊)
            • swap
          • 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 的變數,須回傳排序好的資料
    • I/O
  • 題目的條件:

    • 可能會有 1~ 50000 個數字要進行排序
    • 每個數字會在 - 0.0005 ~ 50000 之間
    • I/O
  • 看完題目你需要思考的是:

    • 使用 Quick sort 這個算法,會不會可能造成超時?
    • 有沒有其他排序方法可以使用 ?

上一篇
【第七天 - Bubble Sort 題目分析】
下一篇
【第九天 - Quick Sort 題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言