# 👉 排序（从小到大）
# 基础排序算法
# 冒泡排序
冒泡排序的基本思想：每次都从第一个元素开始，重复比较相邻的两个项，如果第一项比第二项大，则交换两者位置，否则就不动，一直都遍历完元素为一轮。每一轮操作，都会将当前这一轮中的最大值推至末尾。
// 外层，首元素开始遍历多少轮
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]) {
const temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
const array = [3, 5, 10, 2, 1, 6];
console.log(bubbleSort(array));
以上代码，在乱序或者完全倒序的正常情况下，时间复杂度：O(n^2)，空间复杂度 O(1)。
但如果是完全是正序的情况下，冒泡排序的时间复杂度可以被优化成 O(n)，改进优化版本：
function betterBubbleSort(array) {
for (let i = 0; i < array.length; i++) {
// 添加一个标志位
let flag = false;
for (let j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
const temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
// 如果发生了置换，flag变为true
flag = true;
}
}
// 如果一轮下来，都没进行交换，证明已经是正序了
if (!flag) {
console.log(flag);
return array;
}
}
}
标志位可以帮助我们在第一次冒泡的时候就定位到数组是否完全有序，进而节省掉不必要的判断逻辑，将最好情况下的时间复杂度定向优化为 O(n)。
# 选择排序
选择排序的基本思想：从数组的开头开始，将第一个元素和其他元素进行比较，检查完所有元素后最小的元素会被放到数组的第一个位置；然后缩小范围，从第二个元素开始继续。这个过程一直进行到数组的倒数第二个位置，直到范围不可再缩小，数组有序为止。
function selectionSort(array) {
const len = array.length;
let minNumIndex;
for (let i = 0; i < len; i++) {
minNumIndex = i;
// 找出起始范围内最小元素的index
for (let j = i + 1; j < len; j++) {
if (array[minNumIndex] > array[j]) {
minNumIndex = j;
}
}
const temp = array[i];
array[i] = array[minNumIndex];
array[minNumIndex] = temp;
}
}
选择排序都要走内层循环，因此时间复杂度为：O(n^2)，空间复杂度 O(1)
# 插入排序
插入排序的基本思想：在当前元素的前面是一个有序序列的前提下，从这个有序序列的后往前，找到当前元素适合插入的位置。一般数组的第一个元素自成有序序列，因此都是从第二个元素开始。
function insertionSort(array) {
const len = array.length;
// 从数组的第二个元素开始
for (let i = 1; i < len; i++) {
// 获取当前元素（待排序元素）
const cur = array[i];
// j负责帮助遍历前面的有序序列，找到当前元素合适的插入位置（j从前面的有序序列的尾部往前走）
let j = i;
// array[j-1] < cur，证明是有序了，可以不用动
// 否则需要移动并插入合适位置
while (j > 0 && array[j - 1] > cur) {
array[j] = array[j - 1];
j--;
}
// 跳出了wile证明j就是合适的位置了(循环里面已经j--)
array[j] = cur;
}
}
最好时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)。
最坏时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O(n^2)
平均时间复杂度：O(n^2)
因为不需要额外空间，空间复杂度为 O(1)
直接插入排序在记录基本有序的时候和元素较少时效率是很高的，基本有序时，只需执行少量的插入操作，就可以完成整个记录的排序工作。当元素较少时，效率也很高，就比如我们经常用的 Arrays.sort (),当元素个数少于 10 时，使用的排序算法就是直接插入排序。
# 进阶排序算法
归并排序和快排排序主要用到了“分治”的思想。
“分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。
利用分治思想解决问题，我们一般分三步走：
分解子问题
求解每个子问题
合并子问题的解，得出大问题的解
# 归并排序
归并排序的实现核心思想：
- 分解子问题：对数组进行对半分割，然后再将分割出来的每个子数组继续递归分割，直至分割子数组只有一个元素为止。
- 求解子问题：从粒度最小的子数组开始，两两合并成一个有序的数组。
- 合并子问题得解：两两合并的数组最终会被合并至原始大小的整个有序数组。
写法一：
function mergeSort(array) {
const len = array.length;
// 递归边界
if (len <= 1) return array;
const mid = Math.floor(len / 2);
const left = mergeSort(array.slice(0, mid));
const right = mergeSort(array.slice(mid, len));
array = mergeArray(left, right);
return array;
}
function mergeArray(arr1, arr2) {
const len1 = arr1.length;
const len2 = arr2.length;
let i = 0; //指向arr1
let j = 0; //指向arr2
const result = [];
while (i < len1 && j < len2) {
if (arr1[i] < arr2[j]) {
result.push(arr1[i]);
i++;
} else {
result.push(arr2[j]);
j++;
}
}
// 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
if (i < len1) {
return result.concat(arr1.slice(i));
} else {
return result.concat(arr2.slice(j));
}
}
const array = [3, 5, 10, 2, 1, 6];
console.log(mergeSort(array));
写法二：
const mergeSort = (nums, start, end) => {
if (start >= end) return nums;
const mid = Math.floor((start + end) / 2);
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
return mergeArr(nums, start, mid, end);
};
const mergeArr = (nums, start, mid, end) => {
const result = [];
let i = start,
j = mid + 1;
while (i <= mid && j <= end) {
if (nums[i] < nums[j]) {
result.push(nums[i]);
i++;
} else {
result.push(nums[j]);
j++;
}
}
// 对剩余的合并
while (i <= mid) {
result.push(nums[i++]);
}
while (j <= end) {
result.push(nums[j++]);
}
for (let i = 0; i < result.length; i++) {
nums[i + start] = result[i];
}
return nums;
};
const array = [3, 5, 10, 2, 1, 6];
console.log(mergeSort(array));
归并排序所创建的临时结合都会在方法结束时释放，单次归并排序的最大空间是 n ,所以归并排序的空间复杂度为 O(n)。
归并排序的时间复杂度是 O(nlog(n))
我们一趟归并，需要将两个小集合的长度放到大集合中，则需要将待排序序列中的所有记录扫描一遍所以时间复杂度为 O(n)。
归并排序把集合一层一层的折半分组，则由完全二叉树的深度可知，整个排序过程需要进行 logn（向上取整）次。
我们把每一次切分+归并看做是一轮。对于规模为 n 的数组来说，需要切分 log(n) 次，因此就有 log(n) 轮，则总的时间复杂度为 O(nlogn)。
另外归并排序的执行效率与要排序的原始数组的有序程度无关，所以在最好，最坏，平均情况下时间复杂度均为 O(nlogn) 。
# 快速排序
快速排序仍然坚持“分而治之”的原则不动摇,归并排序和快速排序都用到了分治思想，但还是有所区别：
归并排序是自下而上的，先处理子问题，然后再合并，将小集合合成大集合，最后实现排序。而快速排序是由上到下的，先分区，然后再处理子问题。
快速排序一般用来处理大数据集，速度比较快。快速排序通过递归的方式，将数据依次分为包含较小元素和较大元素的不同子序列。
实现思路：选一个基准值，基于这个基准值，将所有比基准值小的元素摆放在左边，而大于基准值的摆放在右边，然后也对左边和右边分别进行同样的方式递归排序，然后将基准值放在中间进行合并。
实现方式一：
function quickSort(array) {
const len = array.length;
if (len <= 1) return array;
// 基准值可取中间位置值/第一个值/最后一个值
const pivot = Math.floor(len / 2);
const pivotValue = array.splice(pivot, 1);
const left = [];
const right = [];
for (let i = 0; i < len - 1; i++) {
if (array[i] < pivotValue) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left)
.concat(pivotValue)
.concat(quickSort(right));
}
这种实现方式比较直观且容易理解，但因构建新的数组所以会耗费一定的空间复杂度。
实现方式二：
这种实现方式并不会把真的数组分割开来再合并到一个新数组中去，而是直接在原有的数组内部进行排序。
function quickSort(array, low = 0, high = array.length - 1) {
// 递归边界
if (low >= high) return array;
// 基准值位置，这里会先进行第一次分区
const index = partion(array, low, high);
// 对左右分别继续进行递归分区
quickSort(array, low, index - 1);
quickSort(array, index + 1, high);
return array;
}
function partion(array, low, high) {
// 取中间数字作为基准值，并将其交换至首位
const pivot = Math.floor((low + high) / 2);
const pivotVal = array[pivot];
[array[low], array[pivot]] = [array[pivot], array[low]];
// 左右指针
let i = low + 1;
let j = high;
// 移动左右指针，基于基准值分区
// 从左右两边向中间推进的时候，遇到不符合的数就两边交换值。
while (i <= j) {
// 左指针值小于基准值，继续往后移
while (i <= j && array[i] < pivotVal) {
i++;
}
// 右指针值大于基准值，继续往前移
while (i <= j && array[j] > pivotVal) {
j--;
}
// 交换位置，并且指针继续往中间收缩
if (i <= j) {
[array[i], array[j]] = [array[j], array[i]];
i++;
j--;
}
}
// 将基准值放入合适位置(比j小，i大)
[array[low], array[j]] = [array[j], array[low]];
// 返回基准值位置
return j;
}
快速排序的时间复杂度的好坏，是由基准值来决定的。
最好时间复杂度：它对应的是这种情况——我们每次选择基准值，都刚好是当前子数组的中间数。这时，可以确保每一次分割都能将数组分为两半，进而只需要递归 log(n) 次。这时，快速排序的时间复杂度分析思路和归并排序相似，最后结果也是 O(nlog(n))。
最坏时间复杂度：每次划分取到的都是当前数组中的最大值/最小值。大家可以尝试把这种情况代入快排的思路中，你会发现此时快排已经退化为了冒泡排序，对应的时间复杂度是 O(n^2)。平均时间复杂度： O(nlog(n))
快速排序主要时递归造成的栈空间的使用，最好情况时其空间复杂度为 O (logn)，对应递归树的深度。最坏情况时则需要 n-1 次递归调用，此时空间复杂度为 O(n)。
# 计数排序
以数组元素值为键，出现次数为值存进一个临时数组，最后再遍历这个临时数组还原回原数组。
因为 JavaScript 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但不可以排列小数。
常规：
function countingSort(nums) {
let max = Math.max(...nums);
let min = Math.min(...nums);
let arr = new Array();
for (let i = 0; i < nums.length; i++) {
const val = nums[i];
arr[val] = arr[val] ? arr[val] + 1 : 1;
}
// 还原数组
let index = 0;
for (let i = min; i <= max; i++) {
while (arr[i] > 0) {
nums[index] = i;
arr[i]--;
index++;
}
}
return nums;
}
最好时间复杂度：
最好：O(n + k)，k 是最大值和最小值的差。
最坏：O(n + k)
平均：O(n + k)
# 希尔排序
希尔排序是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序的变形。
通过某个增量 gap，将整个序列分给若干组，从后往前进行组内成员的比较和交换，随后逐步缩小增量至 1。希尔排序类似于插入排序，只是一开始向前移动的步数从 1 变成了 gap。
# 堆排序
参考文章： https://www.cnblogs.com/chengxiao/p/6129630.html
# 桶排序
# 排序相关
# JS 自带的排序实现
对于 JS 来说，数组长度大于 10 采用快速排序，否则使用插入排序。
原因在于插入排序是因为时间复杂度比较差，但是在数据量较小的情况下相差无几，而且插入排序的常数时间很小，所以相对别的排序来说会更快。
# 排序稳定性
稳定性的意思就是对于相同值，相对顺序不能改变。
通俗的讲有两个相同的数 A 和 B，在排序之前 A 在 B 前面，而经过排序之后 B 跑到 A 前面了，对于这种情况的发生我们成为排序的不稳定性。