冒泡排序
基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
每一趟遍历，将一个最大的数移到序列末尾（比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换）。
function bubbleSort(arr) {
if (!arr || !arr.length) {
return []
}
// 外部的循环控制所有回合
for (let i = 0; i < arr.length - 1; i++) {
// 内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j+1]) {
const temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
}
}
优化版本：
/*
* 如果有 100 个数的数组，仅前面 10 个无序，后面 90 个都已排好序且都大于前面 10 个数字，那么在第一趟遍历后，
* 最后发生交换的位置必定小于 10，且这个位置之后的数据必定已经有序了，
* 记录下这个位置，第二次只要从数组头部遍历到这个位置就可以了
*/
function bubbleSort(arr) {
if (!arr || !arr.length) {
return []
}
let flag = arr.length
while(flag) {
let n = flag
flag = 0
for (let i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
let temp = arr[i]
arr[i] = arr[i - 1]
arr[i - 1] = temp
flag = i
}
}
}
}
插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
function insertSort(arr) {
// let len = arr.length;
for (let i = 1; i < arr.length; i++) {
// 将 arr[i] 插入到有序队列（arr[0] —— arr[i-1]）中
for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
let temp = arr[j + 1]
arr[j + 1] = arr[j]
arr[j] = temp
}
}
return arr;
}
快速排序
快速排序每一趟排序，都会寻找一个基准元素，有的采用第一个元素，有的会随机生成一个，但是基本思想是不变的，一趟排序结束，会形成以基准元素为分界点的两部分，其中左边比基准元素小（假设从小到大排序），右边比基准元素大。然后再以相同的方法处理左边和右边两部分，即递归。
function quickSort(arr, left, right) {
left = typeof left === 'number' ? left : 0
right = typeof right === 'number' ? right : arr.length - 1
if (left < right) {
const partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex - 1)
quickSort(arr, partitionIndex + 1, right)
}
return arr
}
// 分区操作，设定基准值（pivot）
function partition(arr, left, right) {
let pivot = left
let index = pivot + 1
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
[ arr[i], arr[index] ] = [ arr[index], arr[i] ]
index++
}
}
[ arr[pivot], arr[index - 1] ] = [ arr[index - 1], arr[pivot] ]
return index - 1
}
归并排序（Merge Sort）
分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
function mergeSort(arr) {
const len = arr.length;
if (len < 2) {
return arr;
}
const middle = Math.floor(len / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return mergeArr(mergeSort(left), mergeSort(right));
}
function mergeArr(left, right) {
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
} return result;
}
