關於Quick Sort排序方法與示意圖

    AllenLi
    Coding

    Quick Sort
    Traversal in Binary Tree：

    快速排序是選擇一個數值作為基準(基準值:pivot)，並將剩下的數值與基準進行大於、小於的群組分類，
並在運算的過程中完成升降冪排序。

ex.Input : nums = [3, 2, 1]
           pivot =       V

                      #
step.1     nums    = [3, 2]
           pivot   =     1
           newNums = [1 , 3]

                      #
step.2     nums    = [2]
           pivot   =     1
           newNums = [1, 2, 3]

    QuickSort

    Input: nums = [1, 2, 3, 2, 1, 6]

let quickSort = (nums) => {
  if (nums.length <= 1) return nums

  let pivot = nums[nums.length - 1]
  let left = [], right = []
  let i = 0
  
  while (i < nums.length - 1)  {
    if (nums[i] < pivot) {
      left.push(nums[i])
    } else {
      right.push(nums[i])
    }
  i++
  }
  return quickSort(left).concat(pivot, quickSort(right))
}

console.log(quickSort([1, 2, 3, 2, 1, 6]))

Output: newNums = [1, 1, 2, 2, 3, 6]

    Flow Chart:

    Input: nums = [1, 2, 3, 2, 1, 6]

console.log(pivot, left, right)

6, [ 1, 2, 3, 2, 1 ], [] //[6]
1, [], [ 1, 2, 3, 2 ]    //[1, ... ,6]
2, [ 1 ], [ 2, 3 ]       //[1, 1, 2, ... ,6]  
3, [ 2 ], []             //[1, 1, 2, 2, 3 ,6]  

Output: nums = [ 1, 1, 2, 2, 3, 6 ]

    .concat(a, b)：

    var num1 = [1, 2, 3],
    num2 = [4, 5, 6],
    num3 = [7, 8, 9];

var nums = num1.concat(num2, num3);

console.log(nums);
//Output：[1, 2, 3, 4, 5, 6, 7, 8, 9]

    Related Posts