英文seo招聘_兰州免费网站建设_太原seo霸屏_南京seo优化公司

汇总

注：以下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)#include <iostream>
#include <vector>
using namespace std;// 值传递：quickSort通过递归拼接子数组结果，需返回新vector<int>
// 递归分治：快速排序需保留原数组不变性，避免递归时引用冲突
vector<int> quickSort(vector<int> arr)
{// 递归终止条件：数组长度 ≤1 时直接返回if (arr.size() <= 1){return arr;}vector<int> left;vector<int> right;int pivot = arr[0]; // 基准值取第一个元素// 从第二个元素开始遍历（避免越界）for (size_t i = 1; i < arr.size(); i++){if (arr[i] < pivot){// left.push_back(arr[i]);left.emplace_back(arr[i]);}else{right.emplace_back(arr[i]);}}// 递归处理左右子数组，拼接结果vector<int> sortedLeft = quickSort(left);vector<int> sortedRight = quickSort(right);sortedLeft.emplace_back(pivot);sortedLeft.insert(sortedLeft.end(), sortedRight.begin(), sortedRight.end());return sortedLeft;
}int main()
{vector<int> arr = {2, 4, 5, 3, 1};vector<int> sortedArr = quickSort(arr);cout << "Sorted array: ";for (int num : sortedArr){cout << num << " ";}cout << endl;return 0;
}

2 冒泡排序

[冒泡排序的思路]

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

[冒泡排序]
- 时间复杂度
1.两个嵌套循环
2.时间复杂度：O(n^2)--这个时间复杂度是不太好的排序时间复杂度
- 空间复杂度：O(1)
#include <iostream>
#include <vector>
using namespace std; // 全局引入std命名空间// 原地排序 -- 引用传递(&)-直接修改原数组,无需返回(void)
void bubbleSort(vector<int> &arr)
{for (int i = arr.size() - 1; i > 0; i--){for (int j = 0; j < i; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);}}}
}int main()
{vector<int> arr = {2, 4, 3, 5, 1};bubbleSort(arr);cout << "Sorted array: ";for (int num : arr){cout << num << " ";}cout << endl;return 0;
}

3 插入排序

[插入排序的思路]

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

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

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

[插入排序]
- 时间复杂度
1.两个嵌套循环。
2.时间复杂度：O(n^2)。空间复杂度：
-空间复杂度：O(1)
原因：仅需常数级别的额外空间（如临时变量temp），属于原地排序算法#include <iostream>
#include <vector>
using namespace std;// 原地排序 -- 引用传递(&)-直接修改原数组,无需返回(void)
void insertSort(vector<int> &arr)
{for (size_t i = 1; i < arr.size(); i++){int temp = arr[i]; // 待插入元素int j = i;         // 移动索引while (j > 0 && arr[j - 1] > temp){arr[j] = arr[j - 1]; // 元素后移j--;}arr[j] = temp; // 插入到正确位置}
}int main()
{vector<int> arr = {2, 4, 3, 5, 1};insertSort(arr);cout << "Sorted array: ";for (int num : arr){cout << num << " ";}cout << endl;return 0;
}// 值传递写法 -- 返回新vector<int>、不改变原来的数组
// vector<int> insertSort(vector<int> arr)
// {
//     for (size_t i = 1; i < arr.size(); i++)
//     {
//         int temp = arr[i]; // 待插入元素
//         int j = i;         // 移动索引
//         while (j > 0 && arr[j - 1] > temp)
//         {
//             arr[j] = arr[j - 1]; // 元素后移
//             j--;
//         }
//         arr[j] = temp; // 插入到正确位置
//     }
//     return arr;
// }// int main()
// {
//     vector<int> arr = {2, 4, 3, 5, 1};
//     vector<int> sortedArr = insertSort(arr);//     cout << "Original array: ";
//     for (int num : arr)
//     {
//         cout << num << " ";
//     }
//     cout << endl;
//     cout << "Sorted array: ";
//     for (int num : sortedArr)
//     {
//         cout << num << " ";
//     }
//     cout << endl;//     return 0;
// }

4 选择排序

[选择排序的思路]

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

[选择排序]
- 时间复杂度
两个嵌套循环；时间复杂度：O(n^2)。--性能不太好的排序算法- 时间复杂度：O(1) -- 原地排序
#include <iostream>
#include <vector>
using namespace std;// 原地排序 -- 引用传递(&)-直接修改原数组,无需返回(void)
void selectionSort(vector<int> &arr)
{for (int i = 0; i < arr.size() - 1; i++){int minIndex = i;// 在未排序部分中寻找最小值for (int j = i + 1; j < arr.size(); j++){if (arr[j] < arr[minIndex]){minIndex = j;}}// 将最小值交换到已排序部分的末尾if (minIndex != i){swap(arr[i], arr[minIndex]); // 使用标准库交换函数}}
}int main()
{vector<int> arr = {5, 4, 3, 2, 1};selectionSort(arr);cout << "Sorted array: ";for (int num : arr){cout << num << " ";}cout << endl;return 0;
}

---

js排序版本见：算法-- js排序