iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
Software Development

30天用JavaScript刷題刷起來!系列 第 27

Day 27 : 快速排序法 Quick Sort

今天要來實作的快速排序法Quick Sort,雖然不是最佳的(以前學習的時候看到他的名字以為它會是最快的),不過它仍是必須學習的經典。
/images/emoticon/emoticon15.gif
我們就直接開始吧!

Input: nums = [5,1,1,2,0,0]

一開始我們要先先挑一個基準數(pivot),這邊我拿每次都固定subArray的第一個元素當作pivot(當然你也可以隨便拿一個數當作pivot,只要我們確定拿的是哪以個方便之後操作),假設為n,而後我們希望把大於P的數移到它的右邊,小於P的數移到它的左邊

這裡我們直接挑5為pivot(P),然後我們建立一個left pointer(L)放在pivot的右邊,這裡也就是nums[1] = 1的位置 以及 建立一個 right pointer(R)放在nums的最後一個位置也就是nums[nums.length -1 ] = 0的地方

接下來我們要把
左邊指標(L)指到的數和P比較,如果他小於或等於P我們就把L往右移動,直到遇到比P大的數停止
右邊指標(R),如果他大於P我們就把R往左移動,直到遇到比P小的數停止

然後我們把L指到的數和R指到的數交換swap

接下來要做的事情會重複到左指標越過右指標,我們拿右指標和pivot做交換

而pivot換到的位置,會是它最後的位置,也就是說它會是已經被排好不會再改變。而和pivot做完交換後pivot的左右兩邊會產生兩個subArray分別繼續執行quick sort。

nums = [5,1,1,2,0,0]
        ^ ^       ^
        | |       |
        P L       R

--------------------------
R:第一次我們發現 0 < 5 所以符合我們要停留的條件
L:過程中的都符合小於5的條件,直接飛越過了R

nums = [5,1,1,2,0,0]
        ^         ^
        |         |
        P         R
                    ^
                    |
                    L
--------------------------
因為L超越了R,把P和R做swap交換的動作
nums = [0,1,1,2,0,5]
        ^         ^
        |         |
        P         R
                    ^
                    |
                    L
--------------------------
我們現在得到了 [0,1,1,2,0,5]
其中5是已經確定排好的
所以繼續把subArray[0,1,1,2,0]來執行quick sort 
--------------------------
nums = [0,1,1,2,0,5]
        ^ ^     ^
        | |     |
        P L     R

--------------------------
因為 L指的1 > 0,且R指的0沒有大於0,
所以這裡L和R要做swap的動作
nums = [0,0,1,2,1,5]
        ^ ^     ^
        | |     |
        P L     R
--------------------------
然後L和R再繼續下一步
可以發現L走到1就發現1>0
而R要走到0才回停止,這時因為R和L已經交會
就把P和R交換得到
nums = [0,0,1,2,1,5]
--------------------------
現在我們的頭 [.,0,...,5]這兩個數是已經排好的了
我們剩下 [0]和[1,2,1]兩個subArray去呼叫quicksort繼續執行
因為[0]的長度是1已經可以停止
於是我們把P,L,R分別擺在
nums = [0,0,1,2,1,5]
            ^ ^ ^
            | | |
            P L R
--------------------------
按照之前的行為我們可以獲得
nums = [0,0,1,1,2,5]

我們來看平均時間複雜度: O(nlogn),空間複雜度為: O(logn)

  • 在最糟的情況會遇到由大到小排列像是[5,4,3,2,1],這種會需要O(n^2)
  • 而最好的情況會是pivot剛好切在中間的時候,時間為O(nlogn)
  • 空間複雜度推薦大家閱讀Tail Call Elimination
function quickSort(array) {
  quicksortHelper(array, 0, array.length - 1);
  return array;
}

function quicksortHelper(array, start, end) {
  // array的長度為0或1
  if (start >= end) return;
  // pivot為subArray的第一個元素
  const pivot = start;
  let left = start + 1;
  let right = end;
  while (right >= left) {
    // 確定是否需要左右交換
    if (array[left] > array[pivot] && array[right] < array[pivot]) {
      swap(left, right, array);
    }
    if (array[left] <= array[pivot]) left++;
    if (array[right] >= array[pivot]) right--;
  }
  swap(pivot, right, array);
  // 確保最多呼叫O(logn)空間複雜度
  // 我們採取每次先呼叫較小的subarray,利用tail recursion的方式
  const leftSubArrIsSmaller = right - start < end - right;
  if (leftSubArrIsSmaller) {
    quicksortHelper(array, start, right - 1);
    quicksortHelper(array, right + 1, end);
  } else {
    quicksortHelper(array, right + 1, end);
    quicksortHelper(array, start, right - 1);
  }
}

function swap(a, b, array) {
  let tmp = array[b];
  array[b] = array[a];
  array[a] = tmp;
}

建議一開始不熟的時候最好拿紙筆出來畫畫看!
畫的時候寫一下pseudo code,對於組成整個答案就會有信心許多!

明日預告:Merge Sort


上一篇
Day 26: Insertion sort & Selection sort
下一篇
Day 28:合併排序法 Merge Sort
系列文
30天用JavaScript刷題刷起來!30

尚未有邦友留言

立即登入留言