JavaScript常用的5种排序算法,你都掌握了吗?
今天给大家带来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种排序算法都有其特点和适用场景。根据具体情况选择合适的算法哟。