算法-- js排序

汇总

注：以下log n 是 O(log2n)
注：快速排序实际应用中通常最优，但需避免最坏情况。

1 快速排序

[快速排序的思路]

• 分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面。
• 递归：递归地对基准前后的子数组进行分区。

[快速排序]
- 时间复杂度：
时间复杂度：​最优/平均情况O(n*logN), 最坏情况O(n^2)。
n*logN: 当每次划分能大致将数组分为两部分时（如基准值选择接近中位数），递归深度为 logn，每层处理 n 个元素
n^2: 当数组已有序或基准值总是极值（如第一个或最后一个元素），导致每次划分仅减少一个元素，递归深度为 nPS:递归的时间复杂度是O(logN)。(劈成两半，递归前left后right，基本劈成两半递归的操作都是logN）
分区操作的时间复杂度是O(n)。- 空间复杂度：O(logN)（递归造成的栈空间的使用）//没明白为什么递归深度是 logn?--简单来说是："拆分两半"这个动作log2 n次
答：快速排序的递归深度为logn是因为在理想情况下​（每次划分都能将数组均匀分成两部分），递归树的深度与二分查找类似。以下是具体解释：
​均匀划分的数学原理每次划分后，数组被分成两个子数组，长度约为2n​。递归调用会持续将子数组对半分割，直到子数组长度为1。此时递归深度d满足：
n/(2^d)​=1 ⟹ d=log2 n
因此深度为O(logn)function quickSort(arr) {// 递归终止条件：数组长度 ≤1 时直接返回/* 这里也说明一下 为啥要 小于等于1 , 因为有可能 出现左边数组为空的情况 ,不能是 ==1 那样就会出现 程序崩溃的情况 , 这样==0时没有return值也就是递归不会结束所以报错Maximum call stack size exceeded */if (arr.length <= 1) {return arr;}const left = [];const right = [];const pivot = arr[0]; // 基准值取第一个元素// 从第二个元素开始遍历（避免越界）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 arr = [2, 4, 5, 3, 1];
const sortedArr = quickSort(arr);
console.log(sortedArr); // 输出: [1, 2, 3, 4, 5]

2 冒泡排序

[冒泡排序的思路]

• 比较所有的相邻元素，如果第一个比第二个大，则交换它们。
• 一轮下来，可以保证最后一个数是最大的。
• 执行n-1轮，就可以完成排序。

[冒泡排序]
- 时间复杂度
1.两个嵌套循环
2.时间复杂度：O(n^2)--这个时间复杂度是不太好的排序时间复杂度
- 空间复杂度：O(1)
function bubbleSort(arr) {// 先写第一轮冒泡；// 另外注意：arr.length-1// for (let j = 0; j < arr.length-1; j++) {//     if (arr[j] > arr[j + 1]) {//         let temp = arr[j]//         arr[j] = arr[j + 1]//         arr[j + 1] = temp//     }// }// 多轮冒泡for (let i = arr.length - 1; i > 0; i--) {for (let j = 0; j < i; j++) {if (arr[j] > arr[j + 1]) {let temp = arr[j]arr[j] = arr[j + 1]arr[j + 1] = temp}}}return arr
}
let arr = [2, 4, 3, 5, 1]
let res = bubbleSort(arr)
console.log('res:', res)

3 插入排序

[插入排序的思路]

1. 初始化：将第一个元素视为已排序序列。
2. 插入过程

• 待插入元素暂存temp=arr[i]：从第二个元素（ax）开始，暂存其值为temp。
• 大数后移：向前扫描：从 ax 的前一个元素开始反向遍历，将所有大于 temp 的元素后移一位。
• 插入位置：当遇到第一个小于等于 temp 的元素 ay 时，将 temp 插入到 ay 的后面。

3. 重复：对后续所有未排序元素执行上述操作。

[插入排序]
- 时间复杂度
1.两个嵌套循环。
2.时间复杂度：O(n^2)。空间复杂度：
-空间复杂度：O(1)
原因：仅需常数级别的额外空间（如临时变量temp），属于原地排序算法function insertSort(arr) {for (let i = 1; i < arr.length; i++) {const temp = arr[i] // 待插入元素let j = i // 移动索引while (j > 0) {if (arr[j - 1] > temp) {arr[j] = arr[j - 1] // 元素后移j--} else {break;}}arr[j] = temp // 待插入元素-插入到正确位置}return arr
}
let arr = [2, 4, 3, 5, 1]
let res = insertSort(arr)
console.log('res:', res)// ！[注意]：这样写会报错，因为j = i + 1、arr[j]会超出范围
// function insertSort(arr) {
//     for (let i = 0; i < arr.length; i++) {
//         let j = i + 1
//         const temp = arr[i]
//         while (j > 0) {
//             if (arr[j] < temp) {
//                 arr[j - 1] = arr[j]
//                 j--
//             } else {
//                 break;
//             }
//         }
//         arr[j] = temp
//     }
//     return arr
// }

4 选择排序

[选择排序的思路]

• 找到数组中的最小值，选中它并将其放置在第一位。
• 接着找到第二小的值，选中它并将其放置在第二位。
• 以此类推，执行n-1轮。

[选择排序]
- 时间复杂度
两个嵌套循环；时间复杂度：O(n^2)。--性能不太好的排序算法- 时间复杂度：O(1) -- 原地排序
function selectionSort(arr) {for (let i = 0; i < arr.length - 1; i++) {let minIndex = i;// 在未排序部分中寻找最小值for (let j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 将最小值交换到已排序部分的末尾if (minIndex !== i) {[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // ES6解构赋值交换}}return arr; // 返回排序后的数组（可选）
}// 使用示例
const arr = [5, 4, 3, 2, 1];
const sortedArr = selectionSort(arr);
console.log(sortedArr); // 输出: [1, 2, 3, 4, 5]

---

C++排序版本见：算法-- C++排序