js 冒泡排序 选择排序 快速排序：js冒泡排序选择排序快速排序，3种算法对比与代码
JavaScript 排序算法对比：冒泡排序、选择排序与快速排序
排序算法是计算机科学中的基础算法之一，广泛应用于数据处理和优化问题中。在 JavaScript 中，常见的排序算法包括冒泡排序、选择排序和快速排序。这三种算法各有优缺点，适用于不同的场景。本文将对这三种算法进行详细对比，并提供相应的代码实现。
1. 冒泡排序
冒泡排序是一种简单的排序算法，通过重复遍历待排序的数组，比较相邻元素的值，如果它们的顺序错误就把它们交换过来。遍历数组的工作重复进行，直到没有再需要交换的元素，这意味着数组已经排序完成。
冒泡排序的特点：
- 简单易懂： 代码实现简单，容易理解。
- 时间复杂度： 平均和最坏情况时间复杂度为 O(n²)，最好情况为 O(n)（当数组已经排序时）。
- 空间复杂度： O(1)，因为它是原地排序算法。
- 稳定性： 稳定排序，相同元素的相对顺序不会改变。
冒泡排序的代码实现：
javascript
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
// 示例
const array = [64, 34, 25, 12, 22, 11, 90];
console.log("Original array:", array);
console.log("Sorted array:", bubbleSort(array));
2. 选择排序
选择排序是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的特点：
- 简单易懂： 代码实现简单，容易理解。
- 时间复杂度： 平均和最坏情况时间复杂度为 O(n²)，最好情况也是 O(n²)。
- 空间复杂度： O(1)，因为它是原地排序算法。
- 稳定性： 不稳定排序，相同元素的相对顺序可能会改变。
选择排序的代码实现：
javascript
function selectionSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
// 交换 arr[i] 和 arr[minIndex]
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return arr;
}
// 示例
const array = [64, 34, 25, 12, 22, 11, 90];
console.log("Original array:", array);
console.log("Sorted array:", selectionSort(array));
3. 快速排序
快速排序是一种高效的排序算法，采用分治策略来对一个数组进行排序。快速排序的基本思想是：选择一个基准元素，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分的所有记录都比另一部分的所有记录小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序的特点：
- 高效性： 平均时间复杂度为 O(n log n)，最坏情况为 O(n²)（当数组已经排序或逆序时）。
- 空间复杂度： O(log n)，因为它是递归算法，需要额外的栈空间。
- 稳定性： 不稳定排序，相同元素的相对顺序可能会改变。
- 适用性： 适用于大数据量排序，效率高。
快速排序的代码实现：
javascript
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivot = arr[arr.length - 1];
let left = [];
let 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).concat(pivot, quickSort(right));
}
// 示例
const array = [64, 34, 25, 12, 22, 11, 90];
console.log("Original array:", array);
console.log("Sorted array:", quickSort(array));
对比
1. 时间复杂度：
- 冒泡排序和选择排序： 平均和最坏情况时间复杂度为 O(n²)，适用于小数据量排序。
- 快速排序： 平均时间复杂度为 O(n log n)，最坏情况为 O(n²)，适用于大数据量排序。
2. 空间复杂度：
- 冒泡排序和选择排序： O(1)，原地排序。
- 快速排序： O(log n)，需要额外的栈空间。
3. 稳定性：
- 冒泡排序： 稳定排序。
- 选择排序： 不稳定排序。
- 快速排序： 不稳定排序。
4. 适用性：
- 冒泡排序： 适用于小数据量，简单易懂。
- 选择排序： 适用于小数据量，简单易懂。
- 快速
