今天给大家带来5种最常见的前端排序算法，注释非常详细，欢迎讨论~
1. 冒泡排序（Bubble Sort）
定义：冒泡排序是一种简单的比较排序算法。它重复地比较相邻的元素，并将顺序错误的相邻元素交换位置，直到整个序列排序完成。
代码示例：
function bubbleSort(arr) {
const len = arr.length
// 每一次外循环固定一个最大值在最后（因为是作比较，次数是数组长度-1）
for(let i = 0; i < len - 1; i++) {
// 每一次内循环两两比较
for(let j = 0; j < len -1 - i; j++) {
if(arr[j] > arr[j + 1]) {
// 交换元素,大的放后面
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr
}
const nums = [4, 5, 2, 7, 8]
console.log(bubbleSort(nums)) // [2, 4, 5, 7, 8]
优点：实现简单，易于理解。稳定。
缺点：时间复杂度为 O(n^2)，在大规模数据排序中性能较差。
2. 选择排序（Selection Sort）
定义：选择排序是一种简单的排序算法，每次从未排序部分找到最小（或最大）的元素，然后放到已排序部分的末尾。
代码示例：
function selectionSort(arr) {
const len = arr.length
// 每一次外循环确定一个最小值（因为是作比较，次数是数组长度-1）
for(let i = 0; i < len - 1; i++) {
// 假设当前索引为 i 的元素是最小的
let minIndex = i
// 每一次内循环两两比较(因为要比完数组剩下所有数，所以 j < 数组长度len)
for(let j = i + 1; j < len; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j
}
}
// 将最小元素与当前索引的元素进行交换
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
return arr
}
const nums = [4, 5, 2, 7, 8]
console.log(selectionSort(nums)) // [2, 4, 5, 7, 8]
优点：实现简单，对于小规模数据排序效果较好。
缺点：时间复杂度为 O(n^2)，不稳定（可能改变相等元素的顺序）。
3. 插入排序（Insertion Sort）
定义：插入排序是一种简单且直观的排序算法。它的思想是将数组分为已排序和未排序两部分，初始时已排序部分只有一个元素，然后逐步将未排序部分中的元素插入到已排序部分的正确位置上。通过重复这个过程，最终使得整个数组有序。
代码示例：
function insertionSort(arr) {
const len = arr.length
for (let i = 1; i < len; i++) {
let current = arr[i] // 当前要插入的元素
let j = i - 1; // 已排序部分的最后一个元素的索引（当前元素的上一个）
// 如果上一个元素比当前元素大，就将上一个元素放到当前元素的位置（即后移）
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]
j-- // 继续往前比
}
// 将当前元素插入（赋值）到正确的位置（因为j--了，所以j + 1是正确位置）
arr[j + 1] = current
}
return arr
}
const nums = [4, 5, 2, 7, 8]
console.log(insertionSort(nums)) // [2, 4, 5, 7, 8]
优点：对于基本有序的数组或较小规模的数组排序效果好。稳定。
缺点：时间复杂度为 O(n^2)，在大规模数据排序中性能较差。
4. 快速排序（Quick Sort）
定义：快速排序是一种高效的排序算法，采用分治的策略。它选择一个基准元素，将数组分成两个子数组，使得左边的元素都小于基准，右边的元素都大于基准，然后递归地对子数组进行排序。
代码示例：
function quickSort(arr) {
if (arr.length <= 1) {
return arr // 基线条件：当数组长度小于等于 1 时，直接返回该数组
}
const pivot = arr[0] // 选择第一个元素作为基准
const left = [] // 存放小于基准的元素
const right = [] // 存放大于基准的元素
for (let i = 1; i < arr.length; i++) {
// 小的放左边，大的放右边
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return [...quickSort(left), pivot, ...quickSort(right)] // 递归地对左右两部分进行快速排序，并将结果拼接起来
}
const nums = [4, 5, 2, 7, 8]
console.log(quickSort(nums)) // [2, 4, 5, 7, 8]
优点：平均情况下时间复杂度为 O(n log n)，性能较好。
缺点：在最坏情况下，时间复杂度为 O(n^2)，不稳定（可能改变相等元素的顺序）。
5. 归并排序（Merge Sort）
定义：归并排序是一种高效的排序算法，采用分治的策略。它将待排序的数组递归地划分为较小的子数组，然后将这些子数组逐一合并，直到整个数组排序完成。
代码示例：
function mergeSort(arr) {
// 基线条件：当数组长度小于等于 1 时，直接返回该数组
if (arr.length <= 1) {
return arr
}
const mid = Math.floor(arr.length / 2) // 计算数组的中间位置
const left = arr.slice(0, mid) // 将数组分为左右两部分
const right = arr.slice(mid)
// 递归地对左右两部分进行归并排序，并将结果合并
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
const result = []
let i = 0
let j = 0
// 比较左右两个子数组的元素，并按顺序加入结果数组
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i])
i++
} else {
result.push(right[j])
j++
}
}
// 处理剩余元素（如果有）
while (i < left.length) {
result.push(left[i])
i++
}
while (j < right.length) {
result.push(right[j])
j++
}
return result
}
const nums = [4, 5, 2, 7, 8]
console.log(mergeSort(nums)) // [2, 4, 5, 7, 8]
优点：时间复杂度为 O(nlogn)，稳定（保持相等元素的顺序）。
缺点：需要额外的空间来存储临时数组，增加了空间复杂度。
以上5种排序算法都有其特点和适用场景。根据具体情况选择合适的算法哟。
