各种排序算法

选择排序(selection sort)

符合直觉的简单的排序算法, 每遍历一次挑选出一个最大(最小)的数，直到最后一个。

function selectionSort(arr){
	for(let i = 0; i < arr.length - 1; i++){
        let min = i
        for(let j = i + 1; j < arr.length; j++){
					min = arr[j] < arr[min] : j : min
        }
				swap(arr, i, min);
	}
	function swap(arr, i, min){
		let temp;
		arr[i] = temp;
		arr[i] = arr[min];
		arr[min] = temp;
	}
}

冒泡排序的时间复杂度为 O(n²) 额外空间复杂度 O(1)
是稳定的排序算法

冒泡排序(bubble sort)

比较两个相邻的元素A、B（假设 A 在 B 前面）, 如果A > B(A < B)则交换 A 与 B 的顺序。
每一轮结束后，最后一个元素为最大（最小）的值。每一轮可以选出一个最大(最小值)。选出后在再其他元素中继续选。直到只剩一个元素排列完毕。
代码如下：

function bubbleSort(arr){
	for(let i = 0; i < arr.length - 1; i ++){
		for(let j = 0; j < arr.length - 1 - i; j ++){
			if(arr[j] > arr[j + 1]){
               const temp = arr[j] 
               arr[j] = arr[j + 1]
               arr[j + 1] = temp
			}
		}
	}
}

冒泡排序的时间复杂度为 O(n²) 额外空间复杂度 O(1)
是稳定的排序算法

插入排序

将第一个元素视为已排序，从未排序数组中插入已排序数组。依次比较找到合适的位置后插入。
较前两个算法，这个算法的时间复杂度好了很多。不过最坏时间复杂度仍然是 O(n²), 额外空间复杂度 O(1),是稳定的排序算法
示例代码如下：

function insertionSort(arr){
	for(let i = 0;i < arr.length; i++){
		const item = arr.splice(i, 1)
		for(let j = 0; j < i; j++){
			if(arr[j] > item){
				arr.splice(j,0,item)
			}
		}
	}	
}

希尔排序

希尔排序是插入排序的改进版本，本质上是将一个大数组分成几个小数组分别进行插入排序,这样来减少需要的所需的移动，间隔序列可以是一个数列。最优间隔序列未知。
下面是代码示例;

shellSort(arr){
    // gap:4-->2-->1
	for(let gap = Math.floor(arr.length / 2); gap > 0; i = Math.floor(gap / 2))){
        for(let th = 0; th < Math.floor(arr.length / gap); th++){
            insertSort(arr[gap * th, gap * (th + 1)])
        }
	}
}

最坏时间复杂度：O(n²)
平均时间复杂度：O(n^4/3)~O(n^3/2)
和间隔序列和数组本身有关

归并排序（merge sort）

终于到了常用的排序算法了。排序思路很简单。对两个排序好的数组进行合并在排序。那如果这两个排序好的数组是怎么来的呢? 细分，将数组一分为二不断细分直到粒度为 1，那么久可以开始合并了。代码如下：

funciton mergeSort(arr){
	if (arr.length < 2) return arr;
	let mid = arr.length >> 1
	let left = arr.slice(0, half);
	let right = arr.slice(half);

	function merge(l, r){
		const res = [];
		let i=0, j=0;
		while(1){
			if(i >= l.length){
				res = [...res,...r];	
				return res;
			}
			if(j >= r.length){
				res = [...res,...l]	
				return res;
			}
			if(l[i] > r[j]){
				res.push(r[j]);
				j++;	
			}else{
				res.push(l[i]);
				i++;	
			}	
		}	
	}

	return merge (mergeSort(left), mergeSort(right));
}

归并排序时间复杂度为 O(nlgn) 之所以有如此大的进步是因为前面的比较信息通过归并的形式保留了下来。