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]
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]