在 Javascript 中遇到排序問題，通常可直接使用原生 function — sort()
因此很少自己實作排序的功能，此次透過刷題，嘗試用各種排序演算法，期待能更深入地對個演算法有記憶，並瞭解使用情境；相關的時間、空間複雜度，將會另撰寫文章

搭配相關的視覺化工具：VisualGo, VISUALIZE CODE EXECUTION
我個人是圖像化學習較能吸收，尤其在針對演算法這種較抽象的概念，能夠直觀地看逐步的過程，可以有更深入的理解。

摘要

將會用到的排序：

插入排序 Insert Sort
快速排列 Quick Sort (use space and in place )
堆排序 Bucket Sort

尋找第 K 個元素問題

其中在理解插入排序時，對於要用兩個迴圈這件事，我卡了好一陣子，直到查到這部影片，很生動地呈現，才頓悟，推薦給大家。
原來雙迴圈是使用了「雙指標」的概念：一個指標往前遍尋，一個指標往後遍尋。

	//Topic: find Kth elements

	//quick sort use space
	var qsort = function(nums,k) {
	if(nums.length <= 1) {
	return nums
	}

	let leftAry = [];
	let rightAry = [];
	let pivot = nums[0];
	for(let i = 1; i < nums.length ; i++){
	nums[i] > pivot ? rightAry.push(nums[i]) : leftAry.push(nums[i])
	}
	return qsort(leftAry).concat(pivot, qsort(rightAry));
	}

	//native sort
	var nativeSort = (nums,k) => {
	nums.sort((a,b) => a-b)
	return nums[nums.length – k]
	}

	const swap = (nums,a,b) => {
	[nums[a],nums[b]] = [nums[b],nums[a]]
	}

	// insert sort
	var insertSort = (nums,k) => {
	for(let i = 1; i < nums.length; i++) {
	let position = i;
	while(position >= 0 && nums[position – 1] > nums[position]) {
	swap(nums,position,position-1);
	position–;
	}
	}
	return nums[nums.length – k]
	}


	var findKthLargest = function(nums, k , sort) {
	return sort(nums,k);
	};
	const nums = [3,2,1,5,6,4];
	const k = 2;
	console.log('qsort result:', findKthLargest(nums,k,qsort)[nums.length – k]);
	console.log('nativeSort result:', findKthLargest(nums,k,nativeSort))
	console.log('insertSort result:', findKthLargest(nums,k,insertSort))

view raw leetCode215.js hosted with ❤ by GitHub

LeetCode 75: Sort Colors
實作：
1. 使用 quick sort use space 實作 sort (僅實作，題目要求要 in place)
2. 使用 quick sort in place (原地實作，不另外佔空間)實作 sort (LeetCode 實測結果：68 ms, 39.8 MB)
3. 使用 native sort (LeetCode 實測結果：68 ms, 39.8 MB)

同樣的我們可以先來看一支舞 XD

	//use space
	var sortColors1 = function(nums) {
	const pivot = nums[0];
	let left = [];
	let right = [];
	let i = 0;
	while(i < nums.length -1) {
	nums[i] < pivot ? left.push(nums[i]) : right.push(nums[i])
	i++;
	}
	return […left,pivot,…right]
	};

	//native sort in js used quick sort when less data
	var sortColorsNativeSort = (nums) => {
	nums.sort((a,b) => a – b)
	}

	//implement quick sort in place
	var swap = (list,a,b) => [list[a],list[b]] = [list[b],list[a]]
	var getPointer = (nums,start,end) => {
	const v = nums[start];
	let pointer = start;
	for(let i = start + 1; i < end ; i++){
	if(nums[i] < v){
	pointer++;
	swap(nums,pointer,i);
	}
	}
	swap(nums,start,pointer)
	return pointer
	}
	const sortColors = (nums,start = 0,end = nums.length) => {
	if(start >= end) return
	const p = getPointer(nums,start,end)

	sortColors(nums, start, p)
	sortColors(nums, p+1, end)
	}

	const nums = [2,1,4,3,7,1,8]
	sortColors(nums)
	console.log(nums)

view raw leetCode75.js hosted with ❤ by GitHub

LeetCode 347: Top K Frequent Elements
思路：先排序再做堆
學到：善用 JS Map 型別，可以讓 code 更漂亮，以及 Object 與 Map 的差異，論 iterator 特性

	var topKFrequent = function(nums, k) {
	let hash = {}
	nums.forEach(row => {
	if(hash[row] === undefined) {
	hash[row] = 1;
	}else {
	hash[row] += 1;
	}
	})
	let res = […hash].sort((a,b) => a[1]-b[1])
	//object can't iterator directory
	console.log(res)
	};

	var topKFrequent2 = function(nums, k) {
	let hash = new Map();
	nums.forEach(row => {
	if(hash.has(row)) {
	hash.set(row,hash.get(row)+1);
	}else {
	hash.set(row,1);
	}
	})
	console.log('hash key sort:');
	for (var key of hash.keys()) {
	console.log(key);
	}
	let res = […hash].sort((a,b) => b[1]-a[1])
	res = res.map(item => item[0])
	return res.slice(0,k)
	};
	const nums = [1,1,1,2,2,4], k = 2
	console.log(topKFrequent2(nums,k))

view raw leetCode347.js hosted with ❤ by GitHub

	吳三桂在 C Language 額外的Note
	Event Loop 是什麼？淺談 J… 在資料結構- Stack & Quee
	（新手-中階）前端工程師，面試考題整理-… 在 Event Loop 是什麼？淺談 JS Engine…
	JS Array的各種常見操作分類- 來… 在 JS 20 ways to control Arr…
	Sasa 在 Mac下的Vue開發環境建置，使出連環計：Brew?! -…