iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 8
0

快速排序法透過取一個pivot值,將陣列分成左右兩邊,然後開始遞迴地將值與pivot比大小,小的放左邊、大的放右邊,直到比到最後一個。

先看一下這段影片

我在網路上看到一篇很好懂的範例,但這是比較耗記憶體的做法,姑且先記錄下來,後續再改寫一個符合影片中的程式範例。來源出處

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; 
  }
  //Pick the value in the middle of the array as a pivot.
  const pivotIndex = Math.floor(arr.length / 2);
  //Delete the pivot value in the array.
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  //separate the array by the pivot value
  for (let i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
   } else {
      right.push(arr[i]);
   }
  }

  //recursive doing quickSort
  return quickSort(left).concat([pivot], quickSort(right));
};

const arr=[4,2,8,6,0,5,1,7,3,9];
console.log(quickSort(arr));

完整程式碼


上一篇
合併排序法(Merge Sort)
下一篇
堆積排序法(Heap Sort)
系列文
透過JavaScript學習演算法與資料結構30

尚未有邦友留言

立即登入留言