JS 算法>排序算法详解
算法>排序算法是计算机科学中的基础，用于将一组数据按照某种顺序重新排列。JavaScript中常见的算法>排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。以下是这些算法的详细介绍和代码示例。
冒泡排序（Bubble Sort）
冒泡排序是一种简单的算法>排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止，这时数列就完全排序好了。
代码示例：
javascript">function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len; 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;
}
快速排序（Quick Sort Pivot）
快速排序的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码示例：
javascript">function quickSort(arr) {
if (arr.length <= 1) return arr;
let pivot = arr[Math.floor(arr.length / 2)];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (i === Math.floor(arr.length / 2)) continue;
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
选择排序（Selection Sort）
选择排序的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
代码示例：
javascript">function selectionSort(arr) {
let 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;
}
}
// 交换元素
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
插入排序（Insertion Sort）
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
代码示例：
javascript">function insertionSort(arr) {
let len = arr.length;
for (let i = 1; i < len; i++) {
let key = arr[i];
let j = i - 1;
// 将大于key的元素向后移动一位
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
希尔排序（Shell Sort）详解
希尔排序是插入排序的高效改进版，通过分组插入和逐步缩小增量的策略减少元素移动次数，提升排序效率。
核心思想
- 增量分组：将数组按一定间隔（增量）划分为多个子序列，对每个子序列进行插入排序。
- 逐步缩小增量：随着增量逐渐减小，子序列逐渐变长，最终增量为1时，整个数组变为一个序列，完成排序。
实现步骤
- 选择增量序列：常见方法为初始增量取数组长度的一半，之后每次减半，直到增量为1。
- 分组插入排序：对每个增量下的子序列进行插入排序。
- 重复缩小增量：直到增量为1时，最后一次全数组插入排序。
JavaScript代码实现
javascript">function shellSort(arr) {
const length = arr.length;
let gap = Math.floor(length / 2); // 初始增量
// 逐步缩小增量
while (gap > 0) {
// 对每个子序列进行插入排序
for (let i = gap; i < length; i++) {
const temp = arr[i];
let j = i;
// 插入排序逻辑
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2); // 增量减半
}
return arr;
}
// 示例
const array = [9, 7, 6, 15, 3, 2, 8, 5];
console.log(shellSort(array)); // 输出：[2, 3, 5, 6, 7, 8, 9, 15]
关键点解析
-
时间复杂度
- 平均：O(n log n) ~ O(n²)，取决于增量序列的选择。
- 最优：O(n log n)（如使用Hibbard增量序列）。
- 最差：O(n²)（当增量序列不合理时）。
-
空间复杂度：O(1)，原地排序无需额外空间。
-
稳定性：不稳定排序，相同元素可能在分组插入时改变顺序。
增量序列的影响
- 常见增量序列：
- Shell增量：gap = n/2, gap /= 2（简单但效率一般）。
- Hibbard增量：gap = 2^k -1（时间复杂度优化至O(n^{3/2})）。
- Sedgewick增量：结合数学优化，性能更优（时间复杂度O(n^{4/3})）。
应用场景
- 中小规模数据：在数据量不大时，希尔排序比传统O(n log n)算法（如快速排序）更快。
- 内存敏感场景：原地排序特性适合内存受限环境。
与插入排序对比
| 特性 | 插入排序 | 希尔排序 |
|---|---|---|
| 时间复杂度 | O(n²) | O(n log n) ~ O(n²) |
| 数据移动次数 | 高（逐元素移动） | 低（分组跳跃式移动） |
| 适用场景 | 小规模或基本有序数据 | 中等规模无序数据 |
通过分组插入优化，希尔排序在减少元素移动次数和提升效率之间找到了平衡，是经典算法>排序算法中的实用选择。
归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的算法>排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
代码示例：
javascript">function mergeSort(arr) {
if (arr.length <= 1) 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) {
let result = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left, right);
}
堆排序
JavaScript中的堆排序是一种基于堆数据结构的算法>排序算法，主要利用最大堆（升序）或最小堆（降序）的性质进行高效排序。以下是详细解析：
堆排序原理
-
堆的定义
堆是一种完全二叉树，分为最大堆和最小堆：- 最大堆：每个父节点的值都大于或等于其子节点的值，根节点为最大值。
- 最小堆：每个父节点的值都小于或等于其子节点的值，根节点为最小值。
-
核心步骤
- 构建初始堆：将无序数组调整为一个最大堆（升序）或最小堆（降序）。
- 交换与调整：将堆顶元素（最大值或最小值）与末尾元素交换，缩小堆的范围，重新调整剩余元素为堆。重复此过程直到整个数组有序。
具体实现步骤
-
构建最大堆（以升序为例）
- 从最后一个非叶子节点开始：最后一个非叶子节点的索引为
Math.floor(array.length / 2 - 1)。从该节点向上遍历，调整每个子树使其满足最大堆性质。 - 调整方法（Heapify） ：比较父节点与左右子节点的值，若子节点更大则交换，并递归调整受影响的子树。
- 从最后一个非叶子节点开始：最后一个非叶子节点的索引为
-
交换堆顶与末尾元素
- 将堆顶元素（当前最大值）与堆末尾元素交换，此时末尾元素已排序。
- 缩小堆范围：排除已排序的末尾元素，对剩余元素重新调整堆。
-
重复调整与交换
直到堆中仅剩一个元素，此时数组完全有序。
JavaScript代码实现
javascript">// 调整最大堆
function heapify(arr, length, i) {
let largest = i; // 当前根节点
let left = 2 * i + 1; // 左子节点索引
let right = 2 * i + 2; // 右子节点索引
// 比较左子节点与根节点
if (left < length && arr[left] > arr[largest]) {
largest = left;
}
// 比较右子节点与当前最大值
if (right < length && arr[right] > arr[largest]) {
largest = right;
}
// 若最大值不是根节点，交换并递归调整
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, length, largest); // 调整受影响的子树[[5, 12]]
}
}
// 堆排序主函数
function heapSort(arr) {
const length = arr.length;
// 构建初始最大堆（从最后一个非叶子节点开始）
for (let i = Math.floor(length / 2 - 1); i >= 0; i--) {
heapify(arr, length, i); // [[9, 12]]
}
// 逐个交换堆顶与末尾元素，并调整堆
for (let i = length - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // 交换堆顶和末尾元素[[4, 7]]
heapify(arr, i, 0); // 调整剩余元素为堆[[5, 13]]
}
return arr;
}
// 示例
const array = [3, 1, 5, 7, 2, 4, 9, 6];
console.log(heapSort(array)); // 输出：[1, 2, 3, 4, 5, 6, 7, 9]
关键点解析
- 时间复杂度：构建堆的时间为O(n)，每次调整堆为O(log n)，总时间复杂度为O(n log n)。
- 空间复杂度：原地排序，仅需常数级额外空间，空间复杂度O(1)。
- 稳定性：堆排序是不稳定的算法，相同值的元素在排序后可能改变相对位置。
应用场景
- 大规模数据排序：时间复杂度为O(n log n)，适合处理大数据集。
- 优先队列：堆结构常用于实现
优先队列，快速获取最大/最小值。
通过上述步骤和代码，可以清晰地理解堆排序在JavaScript中的实现逻辑及其高效性。
常见算法>排序算法题目和代码
- 题目：对一个数组进行排序，要求时间复杂度尽可能低。
解答：可以使用快速排序或归并排序，因为它们的平均时间复杂度都是O(n log n)。
javascript">// 使用快速排序
let arr = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(arr));
// 或者使用归并排序
let arr2 = [3, 6, 8, 10, 1, 2, 1];
console.log(mergeSort(arr2));
解答：归并排序是稳定的算法>排序算法，因为它在合并两个有序子序列时，如果两个元素相等，它会保持它们在原数组中的相对顺序。
javascript">let arr = [3, 3, 2, 1];
console.log(mergeSort(arr)); // 输出 [1, 2, 3, 3]
- 题目：对一个几乎已经有序的数组进行排序，要求时间复杂度尽可能低。
解答：对于几乎已经有序的数组，插入排序的时间复杂度可以接近O(n)，因为它在每次插入时只需要移动少量的元素。
javascript">let arr = [1, 2, 3, 4, 5, 6, 8, 7];
console.log(insertionSort(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8]
- 题目：找出数组中的第k小的元素。
解答：可以使用快速选择算法（Quickselect），它是快速排序的一种变体，用于在未排序的数组中找到第k小的元素。
javascript">function quickSelect(arr, k) {
if (arr.length === 1) return arr[0];
let pivot = arr[Math.floor(Math.random() * arr.length)];
let lows = [];
let highs = [];
let pivots = [];
for (let num of arr) {
if (num < pivot) lows.push(num);
else if (num > pivot) highs.push(num);
else pivots.push(num);
}
if (k < lows.length) return quickSelect(lows, k);
else if (k < lows.length + pivots.length) return pivots[0];
else return quickSelect(highs, k - lows.length - pivots.length);
}
let arr = [3, 2, 1, 5, 6, 4];
console.log(quickSelect(arr, 2)); // 输出 2
![[实现Rpc] 服务端 | RpcRouter实现 | Builder模式](https://i-blog.csdnimg.cn/img_convert/b310cdcebdee1cee2ff29c6a79b50de0.png)
