对于前端来说，排序算法是面试经常问到的问题~长期的业务工作，往往让本扎实的算法基础忘的一干二净。
- 基础排序算法
- 冒泡排序
- 插入排序
- 选择排序
- 进阶排序算法
- 归并排序
- 快速排序
冒泡排序 （时间复杂度O(n^2)）
过程： 从第一个元素开始，重复比较相邻的两个项，若第一个项比第二个项更大，则交换两者的位置；反之不动。
每一次循环都把最大的元素放到末尾。假如数组的长度为n,那么当我们重复完成n轮的时候，整个数组就有序了。
function bubbleSort(arr){
const len = arr.length ;
// 外层循环用于控制从头到尾的比较
for(var i = 0 ; i < len ; i ++){
// 内层循环用于完成每一轮遍历过程中重复比较，交换
for(var j = 0 ; j < len- 1 - i ; j ++){
if(arr[j] > arr[j + 1]){
[arr[j],arr[j + 1]] = [arr[j+1], arr[j]]
}
}
}
}
插入排序
选择排序
过程： 关键词‘最小值’：每次循环都遍历数组，每次都能找出当前范围内的最小值，把它放在当前范围的头部，然后缩小排序范围，继续重复以上操作，直至数组完全有序为止。
function selectSort(arr) {
// 缓存数组长度
const len = arr.length
// 定义 minIndex，缓存当前区间最小值的索引，注意是索引
let minIndex
// i 是当前排序区间的起点
for(let i = 0; i < len - 1; i++) {
// 初始化 minIndex 为当前区间第一个元素
minIndex = i
// i、j分别定义当前区间的上下界，i是左边界，j是右边界
for(let j = i; j < len; j++) {
// 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
if(arr[j] < arr[minIndex]) {
minIndex = j
}
}
// 如果 minIndex 对应元素不是目前的头部元素，则交换两者
if(minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
}
return arr
}
快速排序
过程： 分割数组取基准值
// 快速排序入口
function quickSort(arr, left = 0, right = arr.length - 1) {
// 定义递归边界，若数组只有一个元素，则没有排序必要
if(arr.length > 1) {
// lineIndex表示下一次划分左右子数组的索引位
const lineIndex = partition(arr, left, right)
// 如果左边子数组的长度不小于1，则递归快排这个子数组
if(left < lineIndex-1) {
// 左子数组以 lineIndex-1 为右边界
quickSort(arr, left, lineIndex-1)
}
// 如果右边子数组的长度不小于1，则递归快排这个子数组
if(lineIndex<right) {
// 右子数组以 lineIndex 为左边界
quickSort(arr, lineIndex, right)
}
}
return arr
}
// 以基准值为轴心，划分左右子数组的过程
function partition(arr, left, right) {
// 基准值默认取中间位置的元素
let pivotValue = arr[Math.floor(left + (right-left)/2)]
// 初始化左右指针
let i = left
let j = right
// 当左右指针不越界时，循环执行以下逻辑
while(i<=j) {
// 左指针所指元素若小于基准值，则右移左指针
while(arr[i] < pivotValue) {
i++
}
// 右指针所指元素大于基准值，则左移右指针
while(arr[j] > pivotValue) {
j--
}
// 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
if(i<=j) {
swap(arr, i, j)
i++
j--
}
}
// 返回左指针索引作为下一次划分左右子数组的依据
return i
}
// 快速排序中使用 swap 的地方比较多，我们提取成一个独立的函数
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
