出处：本文由 小茗同学 发表于 2018-06-13

概述

常见排序算法：

傻瓜排序

这个傻瓜排序是我自己给起的名字，就是按照人的常规思维进行排序，不考虑任何时间复杂度和空间复杂度。话说如果给你一个数组让你手工排序，你的思路会是什么样的呢？我想你肯定是这样的：

整体用肉眼扫描一遍，找到最小的，插入结果里面，然后再扫描剩下的数字，找到最小的，再次插入结果里面，直至原始数组变空，是的，没错，这里说的傻瓜排序就是这个思路。

/**
 * 傻瓜排序
 */
function foolSort(arr) {
	var result = [];
	while(arr.length) {
		var min = arr[0], minIdx = 0; // 先假设第一个数是最小的
		// 遍历找到最小的数字
		for(var i = 1; i< arr.length; i++) {
			if(arr[i] < min) {
				min = arr[i];
				minIdx = idx;
			}
		}
		result.push(min); // 将当前最小数放入结果数组中
		arr.splice(idx, 1); // 从原始数组删除这个数
	}
	return result;
}

冒泡排序

这是最笨也是最容易想到的排序方法：

/**
 * 冒泡排序
 * @param arr 要排序的数组
 */
function bubbleSort(arr) {
	for(let i=0, len=arr.length; i<len-1; i++) {
		for(let j=0; j<len-1-i; j++) {
			if(arr[j] > arr[j+1]) {
				arr[j] = [arr[j+1], arr[j+1] = arr[j]][0];
			}
		}
	}
	return arr;
}

很多时候面试经常需要当面写排序，是个人憋一会儿都能写出来，但是如果能从头到尾一气呵成写完那定是最好的，如何记忆呢？这样记忆，n个数，需要n-1次循环，每次循环从0到n-1-i处为止，最大或最小的数永远在最后面。

快速排序

快速排序使用了一种叫分而治之的思想，它在冒泡排序基础上实现的递归分治法。优点就是快，大多数情况下表现较好，但缺点是不稳定，最坏运行情况是O(n²)。

标准版实现（只是说是标准的快速排序，并不是说代码是标准版，代码没有标准）：

function quickSort(arr, left, right) {
	left = left === undefined ? 0 : left;
	right = right === undefined ? arr.length : right;
	if (left < right - 1) {
		var splitIndex = split(arr, left, right);
		quickSort(arr, left, splitIndex);
		quickSort(arr, splitIndex+1, right);
	}
	function split(arr, left, right) {
		var i = left, j = right, c = left;
		while(true) {
			while(arr[++i] < arr[c]) {if(i >= right -1) break;}
			while(arr[--j] > arr[c]) {if(j <= left) break;}
			if(i>=j) break;
			swap(arr, i, j);
		}
		swap(arr, c, j);
		return j;
	}
	function swap(arr, a, b) {var temp = arr[a]; arr[a] = arr[b]; arr[b] = temp;}
	return arr;
}
console.log(quickSort([1,5,3,4,8,0,9,4,2,12,6,8,3,2,6,7,8,9,4,32,7,9]));

4.1. 分割原理

首先，设定一个参考数，我们这里用第一个参数做参考数，然后用两个变量 i 和 j 从数组两边开始向中间扫描，i 向右走，j 往左走：

i往右走，直到遇见比中轴元素大的（或等于）元素停止移动，j 向左走，直到遇到比中轴元素小的（或等于）的元素停止移动：

此时，如果 i < j 则交换 i、j 所指向的元素：

然后继续向右向左走，直到 i >= j 整个扫描停止：

此时 i 对应元素的左边（不包含arr[i]）必定小于或等于5,j 对应元素的右边（不包含arr[j]）必定大于或等于5

至此，分隔完成。

本段主要参考这里（图片也是来自这里）：https://www.itcodemonkey.com/article/3287.html

4.2. 阮一峰版

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [], right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) left.push(arr[i]);
		else right.push(arr[i]);
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};
复制运行

从代码长度以及理解难易程度上阮一峰版是最佳的，因为即便是从未了解过快速排序的人基本上一看就能懂，但是有2个大问题：

• 每次都创建新数组，无形中大大增加了空间复杂度；
• 使用splice不合理。

本文有待完善