iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 21
1

今天要介紹的是快速排序法 Quick Sort,它普遍被認為最快的排序演算法,並且採用分治法(Divide and Conquer)。運作方式是在資料列設定一個基準點(pivot),然後分別從最左邊和最右邊的數開始比較,將比基準點小的資料移到左邊,比基準點大的資料移到右邊。

之後就變成: "小資料 + 基準點 + 大資料" 這樣的順序,之後可以在小資料和大資料的部分再各找基準點,然後再做數次資料移動,不斷重複這些步驟,最後會得到一個有排序過的資料列。

此網頁有小動畫可以參考看看,非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php

接著我們來實作吧!完成後會討論其時間複雜度~

// 交换
function swap(arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

function partition(arr, left, right) {
  // 設定基準值在資料列中間
  const pivot = arr[Math.floor((right + left) / 2)];

  // 左邊索引小於等於右邊索引都會持續比較
  while (left <= right) {

    // 從左到右找到不小於基準值的元素為止
    // 注意遇到相等的情况也要停下
    while (arr[left] < pivot) {
      left++;
    }

    // 從右到左找到不大於基準值的元素為止
    // 注意遇到相等的情况也要停下
    while (arr[right] > pivot) {
      right--;
    }

    // 當右邊元素大於等於左邊元素就做交換
    if (left <= right) {
      swap(arr, left, right);
      
      left++;
      right--;
    }
  }
  // 回傳分區的索引
  return left;
}

function quickSort(arr, left, right) {
  // 紀錄分裂的索引
  let index;

  // 確保原本陣列長度大於1
  if (arr.length > 1) {

    // 一開始left和right都是undefined,因此設定typeof判斷是否是數字來給left和right初始值
    left = typeof left != "number" ? 0 : left;
    right = typeof right != "number" ? arr.length - 1 : right;
    console.log(left, right);

    // 獲得分裂位置索引
    index = partition(arr, left, right);

    // 從基準值位置判斷,確保左邊陣列還有元素存在
    if (left < index - 1) {
      quickSort(arr, left, index - 1);
    }

    // 從基準值位置判斷,確保右邊陣列還有元素存在
    if (index < right) {
      quickSort(arr, index, right);
    }
  }
  return arr;
}

console.log(quickSort([1, 234, -5, 78, -182, 45]));

時間複雜度:

  • 最佳時間複雜度: Ο(n log n)
    第一個基準值的位置剛好是中位數,將資料均分成二等份
  • 平均時間複雜度: Ο(n log n)
  • 最差時間複雜度: Ο(n^2)
    當資料的順序恰好為由大到小或由小到大時

本次程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day21-quick-sort.js

排序相關的演算法到這邊結束。明天將會介紹搜尋演算法-循序搜尋法!


上一篇
Day20-排序法系列(四)-合併排序法
下一篇
Day22-搜尋法系列(一)-循序搜尋法
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言