排序算法在前端开发中非常重要，尤其是在处理数据展示和用户交互时。掌握排序算法不仅能够帮助我们优化性能，还能提高代码的可读性和维护性。以下是五种常见的排序算法，以及它们的实现示例和分析。
1. 冒泡排序
冒泡排序是一种简单的比较排序。它重复遍历要排序的列表，比较每对相邻元素，并把顺序错误的元素交换过来。每次遍历后，最大的元素会“浮”到列表的末端。
代码示例：
function bubbleSort(arr) {
const len = arr.length;
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;
}
console.log(bubbleSort([5, 3, 8, 4, 2])); // [2, 3, 4, 5, 8]
分析： 冒泡排序的时间复杂度是O(n^2)，适合少量数据排序。
2. 选择排序
选择排序每轮从待排序序列中选择最小（或最大）元素，存放到已排序序列的末尾。简单直观，但是效率较低。
代码示例：
function selectionSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 找到最小值的位置
}
}
// 交换
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64]
分析： 选择排序的时间复杂度也是O(n^2)，适合小规模数组。
3. 插入排序
插入排序是一种简单的排序算法。它通过构建有序序列，将待插入的元素与已排序的元素逐个比较，找到合适的位置插入。
代码示例：
function insertionSort(arr) {
const len = arr.length;
for (let i = 1; i < len; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 后移
j--;
}
arr[j + 1] = key; // 插入
}
return arr;
}
console.log(insertionSort([12, 11, 13, 5, 6])); // [5, 6, 11, 12, 13]
分析： 插入排序的时间复杂度在平均情况下是O(n^2)，但在部分有序的数据上效率较高。
4. 快速排序
快速排序是分治法的一种，选一个基准元素，然后将所有比它小的元素放在左侧，比它大的放在右侧，递归对左右子数组进行排序。
代码示例：
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([10, 7, 8, 9, 1, 5])); // [1, 5, 7, 8, 9, 10]
分析： 快速排序的时间复杂度是O(n log n)，在实际应用中表现良好。
5. 归并排序
归并排序同样是分治法，首先将数组分成两半，分别排序后再合并。它相对稳定，适合大量数据排序。
代码示例：
function mergeSort(arr) {
if (arr.length < 2) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10])); // [3, 9, 10, 27, 38, 43, 82]
分析： 归并排序的时间复杂度是O(n log n)，特别适合大规模数据。
总结
这五种排序算法各有优缺点，适用情况不同。在前端开发中，我们往往要根据具体需求和数据量选择合适的排序算法，提升性能和用户体验。希望这篇文章对你有所帮助！
