Javascript：排序算法
一、平均时间复杂度为O(n²)的排序算法
1、冒泡排序（稳定&空间复杂度O(1)）
2、插入排序（稳定&空间复杂度O(1)）
3、选择排序（不稳定&空间复杂度O(1)）
数组：let arr = [4, 9, 3, 4, 8, 3]
1、冒泡排序
还记得大学刚开始学算法时是这样写的：
for (var i = 0; i < arr.length; i++) {
for(var j = i + 1; j < arr.length; j++) {
if(arr[j] > arr[i]) {
swap(a[j], a[i]);
}
}
}
这确实是最容易理解的，但是会多出很多无用的比较和交换操作。
let flag;
for(let i = 0; i < arr.length; i++) {
flag = false;
for(let j = 0; j < arr.length - i-1; j++) {
if(arr[j] > arr[j+1]) {
let tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
flag = true;
}
}
if(!flag) break;
}
arr.length - i避免了对上一轮已经交换过的元素再次进行比较和交换，flag的出现是为了如果已经全部排序完成就不再进行多余的操作。
2、插入排序
将数组划分为已排序和未排序的俩个区间，每次从未排序区间拿出一个元素在已排序区间与其元素比较大小后插入相应的位置。（一般选择首元素作为已排序区间）
for (let i = 1; i < arr.length; i++) {
let val = arr[i],
j = i - 1;
for(; j >= 0; j--) {
if(arr[j] > arr[i]) {
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j + 1] = val;
}
注意这里的arr[j+1] = arr[j];，意思是在数组中已经找到要插入的位置，然后从已排序区间的末尾将元素向后移动，腾出一个位置。arr[j + 1] = val;此时 j在内循环结束后为-1，所以加1。
3、选择排序
选择排序的思路与插入排序类似，都是划为已排序和未排序区。不同之处在于，取出已排序区的尾元素在未排序区比较选出最小的放入已排序区的末尾。（一般选择首元素作为已排序区间）
for(let i = 0; i < arr.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if(arr[minIndex] > arr[j]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
这里需注意选择排序是不稳定的。比如：
let test = [6,5,6,3,7];
// 取首元素6为已排序区，在余下的元素中找到最小元素3，交换。
// 此时第一个6处于第二个6之后，所以选择排序并不稳定。
扩展：稳定性的常用场景有哪些？
刚开始学习算法的时候对于稳定性的了解只是停留在了解。并不知道这个东西有什么用处。看以下需求：
1、对电商交易中的订单（包含下单时间和金额）进行排序。有20万的订单数据，希望订单按照金额大小由小到大排列，金额相同的订单希望按照下单时间由小到大排列。
思路：先按照下单时间进行排序，再使用稳定算法对金额进行排序。如果先排序金额，这个时候即使金额相同的数据时间也是不定的，所以先排金额再排时间会出现不稳定的情况。
2、对10万个手机号码进行排序
思路：同上，也是从最后一位开始，进行稳定排序。只不过这里有10万条数据，数量过大，O(n²) 显然不能快速的排序，这个时候需要比n方更小的排序。线性（O(n)）排序可以满足需求。
一、平均时间复杂度为O(nlog(n))的排序算法
1、归并排序（稳定&空间复杂度O(n)）
2、快速排序（不稳定&空间复杂度O(1)）
1、归并排序
将数组分从中分为俩部分，然后对俩部分分别进行划分、排序，最终将排序好的部分合并即可。这里使用了分治的思想和递归的技巧。
首先写出递推公式：
// 递推公式
merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1 ... r))
// 终止条件
p >= r
function merge_sort(arr) {
if (arr.length <= 1) return arr
const middle = Math.floor(arr.length / 2) // 找到中间值
const left = arr.slice(0, middle)
const right = arr.slice(middle)
// 分解 合并
return merge(merge_sort(left), merge_sort(right))
}
merge的函数网上有很多，下面链接中也有大家自行参考。
2、快速排序
随机选取数组中一个元素作为分区点，递归实现将小于分区点的值放在左边，大于的放在右边。知道区间长度为1即可。
首先写出递推公式：
// 递推公式
quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1...r)
// 终止条件
p >= r
栗子1
function quickSort(array, l, h){
let pivot,
low = l,
high = h;
if(low >= high) return;
pivot = partition(array, low, high);
quickSort(array, low, pivot - 1);
quickSort(array, pivot + 1, high);
};
function partition(array, low, high) {
let pivotVal = high,
i = low;
for(let j = low; j <= high; j++) {
if(array[j] < array[pivotVal]) {
swap(array, i, j);
i++;
}
}
swap(array, i, high);
return i;
}
栗子2
function Quick(arr = []) {
let array = arr,
len = array.length - 1;
function quickSort(array, l, h){
let pivot,
low = l,
high = h;
if(low >= high) return;
pivot = partition(array, low, high);
quickSort(array, low, pivot - 1);
quickSort(array, pivot + 1, high);
};
function partition(array, low, high) {
let pivotVal = array[low],
tmp = pivotVal;
while(low < high) {
while (low < high && array[high] >= pivotVal) {
high--;
}
array[low] = array[high];
while (low < high && array[low] <= pivotVal) {
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
};
function swap(array, low, high) {
let tmp = array[low];
array[low] = array[high];
array[high] = tmp;
};
quickSort(array, 0, len);
console.log(array.join(','));
}
Quick([4,8,3,2,7]);
其实俩个例子都是用尾元素来划分数组，栗子1是从俩段开始向中间扫描所以low总会有等于high的时候；栗子2虽然都从首元素开始但是high整整扫描了数组一遍也总会扫描到尾元素停止的时候，这个时候 i 即是我们需要的索引。
扩展：如何在O(n)时间复杂度内求无序数组的第k大元素？
leetCode (js)：215. 数组中的第K个最大元素
学习地址：数据结构和算法之美
