本篇文章讲的是以下五种常用的排序算法：

一、冒泡排序

1、原理

每次从前往后遍历整个数组，每一项与其后一项进行对比，若符合要求（从大到小或从小到大），就交换位置。

一遍循环结束后，最大（小）的值就会被排在数组结尾，即每次循环能排好一位，所以要遍历n遍，才能把整个数组排好。

2、特点

实现简单，效率低，排序是稳定的。

3、算法复杂度

时间复杂度O(n^2)，空间复杂度O(1)

4、代码实现

function bubbleSort (array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - 1; j++) {
            if (array[j] > array[j+1]) {
                [array[j+1], array[j]] = [array[j], array[j+1]];
            }
        }
    }
    return array;
}
const arr = [3,121,453,32,7,90,18,9];
console.log(bubbleSort(arr));  
// [
//     3,  7,   9,  18,
//     32, 90, 121, 453
//   ]

 但是其实，没次遍历后，都能排好一位，n次即n位被排好序，那么排好序的位置就不需要在参与之后的遍历了，所以优化后的代码：

function bubbleSort (array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j+1]) {
                [array[j+1], array[j]] = [array[j], array[j+1]];
            }
        }
    }
    return array;
}
const arr = [3,121,453,32,7,90,18,9];
console.log(bubbleSort(arr));  
// [
//     3,  7,   9,  18,
//     32, 90, 121, 453
//   ]

二、插入排序

1、原理

从第二项开始，依次将每一项，插入到该项前边的数组（已排好序）

2、特点

实现较简单，排序稳定

3、算法复杂度

时间复杂度O(n^2)，空间复杂度O(1)

4、代码实现

function insertionSort (array) {
    for (let i = 1; i < array.length; i++) {
        let temp = array[i];
        for (let j = i - 1; j >= 0; j--) {
            if (temp < array[j]) {
              [array[j+1], array[j]] = [array[j], temp];  
            }
        }
    }
    return array;
}
const arr = [3,121,453,32,7,90,18,9];
console.log(insertionSort(arr));  
// [
//     3,  7,   9,  18,
//     32, 90, 121, 453
//   ]

 但是其实，在内层遍历插入时，其实可以选择用二分查找法，因为前边的项都是已经排好序的，优化后的时间复杂度为O(nlogn)，优化后的代码如下：

function insertionSort (array) {
    for (let i = 1; i < array.length; i++) {
        let temp = array[i];
        let low = 0, high = i - 1, mid;
        while (low <= high) {
            mid = Math.floor((low + high) / 2);
            if (temp < array[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // low为插入位置，插入位置low后的依次向后移
        for (let j = i; j > low; j--){
            array[j] = array[j - 1];
        }
        array[low] = temp;
    }
    return array;
}
const arr = [3,121,453,32,7,90,18,9];
console.log(insertionSort(arr));  
// [
//     3,  7,   9,  18,
//     32, 90, 121, 453
//   ]

三、选择排序

1、原理

每次找出最小（大）值、第二小（大）的值，依次与数组的第一位、第二位……交换位置

2、特点

排序不稳定

3、算法复杂度

时间复杂度O(n^2)，空间复杂度O(1)

4、代码实现

function selectionSort (array) {
    for (let i = 0; i < array.length; i++) {
        let min = array[i];
        for (let j = i; j < array.length; j++) {
            const element = array[j];
            if (min > element) {
                min = element;
            }
        }
        let minIndex = array.indexOf(min);
        [array[i], array[minIndex]] = [array[minIndex], array[i]];
    }
    return array;
}
const arr = [3,121,453,32,7,90,18,9];
console.log(selectionSort(arr));  
// [
//     3,  7,   9,  18,
//     32, 90, 121, 453
//   ]

四、快速排序

1、原理

随机从数组中找一个基准值，然后将比基准值小的放一边，比基准值大的放另一边，递归不断对左右两部分数组进行排序，最后排好的就是最终结果。

2、特点

快，对数据非常大的效率高，不稳定，需要额外的两个数组

3、算法复杂度

时间复杂度平均O(nlogn)，最坏O(n^2)，空间复杂度O(logn）

4、代码实现

const quickSort = function (arr) {
	if(arr.length < 2) return arr;
	// 随机选择0～arr.length之间选一个基准值
    const pivot = Math.floor(Math.random() * arr.length);
	// 声明两个数组，分别用于存放比基准值小的数据和比基准值大的数据
	let minArr = [];
	let maxArr = [];
	for(let i = 0; i < arr.length; i++){
        // 大于基准值就放maxArr里
        if(arr[i] >= arr[pivot] && i !== pivot){
            maxArr.push(arr[i]);
        }
        // 小于基准值就放minArr里
        if(arr[i] < arr[pivot] && i !== pivot){
            minArr.push(arr[i])
        }
    }
	// 分别对基准值划分出来的数组递归调用快速排序，然后合并数组
	return [...quickSort(minArr), arr[pivot], ...quickSort(maxArr)];
}
const arr = [3,121,453,32,7,90,18,9];
console.log(quickSort(arr));

五、归并排序

1、原理

百度百科是这样说的：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。但是其实这是核心思想，前边还需要做的就是"分"，将数组不断地平分，直到不能在分为止。

算法主要分成四个步骤

• 数组分成两半，left和right
• 递归处理left
• 递归处理right
• 合并二者结果

"治"的过程，就是合并，是从两个数组的第一位开始依次比较，较小的一个push到新数组中，直到结束，新数组就是排好序的结果。

2、特点

排序稳定，需要额外空间，排序比较优秀了

3、算法复杂度

时间复杂度为O(nlogn)，空间复杂度为O(n)

4、代码实现

const mergeSort = arr => {
	//递归方法
	const len = arr.length;
	if (len < 2) {
		return arr;
	}
	let middle = Math.floor(len / 2),
		left = mergeSort(arr.slice(0, middle)),
		right = mergeSort(arr.slice(middle)); // 拆分为两个子数组
	return merge(left, right);
};
const merge = (left, right) => {
	let result = [];
	while (left.length && right.length) {
		// 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
		if (left[0] <= right[0]) {
			result.push(left.shift());
		} else {
			result.push(right.shift());
		}
	}

	if (left.length) {
        result = result.concat(left);
    }

	if (right.length) {
        result = result.concat(right);
    }

	return result;
};
const arr = [3,121,453,32,7,90,18,9];
console.log(mergeSort(arr));  
// [
//     3,  7,   9,  18,
//     32, 90, 121, 453
//   ]

比较：