排序算法汇总
这篇文章说明下排序算法，直接开始。
1.冒泡排序
最简单直观的排序算法了，新手入门的第一个排序算法，也非常直观，最大的数字像泡泡一样一个个的“冒”到数组的最后面。
算法思想：反复遍历要排序的序列，每次比较相邻的两个元素，如果顺序不正确就交换它们。这样每次遍历都会将最大的元素放到末尾。
排序的时间复杂度O(n²)，如果设置标志为（如果发生数据交换flag=1，默认为0）复杂度为O(n)，，因为是原地排序，基本不用。
void bubble_sort(vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (nums[j] > nums[j+1]) {
swap(nums[j], nums[j+1]);
}
}
}
}
2.选择排序
算法思想：每次从未排序的部分选择最小的元素，放到已排序部分的末尾，重复这个过程。时间复杂度：O(n²)，无论怎样都是O(n²)，空间复杂度O(1)，基本不用。
void selectionSort(std::vector<int> &arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIndex = i; // 假设当前元素为最小值的索引
for (int j = i + 1; j < n; ++j) { // 在未排序部分查找最小值
if (arr[j] < arr[minIndex]) {
minIndex = j; // 更新最小值索引
}
}
// 将找到的最小值与当前元素交换
if (minIndex != i) {
std::swap(arr[i], arr[minIndex]);
}
}
}
3.插入排序
算法思想：将数组分为已排序和未排序部分，从未排序部分取元素，在已排序部分找到合适的位置插入。时间复杂度O(n²)，空间复杂度O(1)。
void insertionSort(std::vector<int>& arr) {
int n = arr.size(); // 获取数组的大小
for (int i = 1; i < n; i++) { // 从第二个元素开始
int key = arr[i]; // 当前待插入的元素
int j = i - 1;
// 在已排序部分中找到合适的位置插入 key
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 向后移动元素
j--; // 移动到前一个元素
}
arr[j + 1] = key; // 插入 key
}
}
4.快速排序
算法思想：选择一个基准元素，将数组划分为比基准小的部分和比基准大的部分，递归地对这两个部分排序。时间复杂度O(n log n)，空间复杂度O(log n) 。
void fastSort(vector<int> &nums, int low, int high) {
if (low >= high)
return;
int pivot = nums[high], i = low;
for (int j = low; j < high; j++) {
if (nums[j] < pivot) {
if (i != j)
swap(nums[i], nums[j]);
i++;
}
}
swap(nums[i], nums[high]);
fastSort(nums, low, i - 1);
fastSort(nums, i + 1, high);
}
5.归并排序
算法思想：采用分治法，将数组分成两个子数组分别排序，再将它们合并成一个有序数组。时间复杂度O(n log n)，空间复杂度O(n) 。
//递归版本
void mergeSort(vector<int> &nums, int left, int right) {
if (left >= right)
return;
int mid = left + (right - left)/2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
vector<int> tmp(right - left + 1);
int count = 0;
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (nums[i] < nums[j]) {
tmp[count++] = nums[i++];
} else {
tmp[count++] = nums[j++];
}
}
while (i <= mid) {
tmp[count++] = nums[i++];
}
while (j <= right) {
tmp[count++] = nums[j++];
}
for (int p = 0; p < tmp.size(); p++) {
nums[left + p] = tmp[p];
}
}
//迭代版本
void mergeSortIterative(std::vector<int> &nums) {
int n = nums.size();
for (int currentsize = 1; currentsize < n - 1; currentsize *= 2)
for (int left = 0; left < n - 1; left += 2 * currentsize) {
int mid = min(left + currentsize - 1, n - 1);
int right = min(left + 2 * currentsize - 1, n - 1);
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> leftArr(n1), rightArr(n2);
for (int i = 0; i < n1; i++)
leftArr[i] = nums[left + i];
for (int i = 0; i < n2; i++)
rightArr[i] = nums[mid + i + 1];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] < rightArr[j]) {
nums[k] = leftArr[i++];
} else {
nums[k] = rightArr[j++];
}
k++;
}
while (i < n1) {
nums[k++] = leftArr[i++];
}
while (j < n2) {
nums[k++] = rightArr[j++];
}
}
}
6.堆排序
算法思想：使用二叉堆这种数据结构，先构建最大堆（或最小堆），然后依次将堆顶元素移除，重新调整堆。时间复杂度O(n log n)，空间复杂度O(1)（不用递归的话）
void heapify(vector<int> &nums, int n, int i) {
if(i>n)
return;
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < n && nums[left] > nums[largest])
largest = left;
if (right < n && nums[right] > nums[largest])
largest = right;
if (largest != i) {
swap(nums[i], nums[largest]);
heapify(nums, n, largest);
}
}
void heapSort(vector<int> &nums) {
int n = nums.size();
for(int i=n/2-1;i>=0;i--) {
heapify(nums,n,i);
}
for(int i=n-1;i>0;i--) {
swap(nums[0],nums[i]);
heapify(nums,i,0);
}
}
排序算法的总结表格：
| 排序算法 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
7.文末解释一下算法时间复杂中的log n，有些人不理解
快速排序的平均时间复杂度为 O(n log n)，是因为它在理想情况下可以将问题规模递归减半，而每次递归的划分过程需要 O(n) 的操作。通过递归树的结构，我们可以直观理解为什么时间复杂度为 O(n log n)。
1. 每一层的操作需要 O(n) 的时间
在快速排序的每一层递归中，主要的开销来自于划分（partition）操作。这个操作的过程是选取一个基准元素（pivot），然后从两边扫描数组，交换元素，使得基准元素的左边都比它小，右边都比它大。
无论基准元素选得如何，每次划分需要遍历整个数组。因此，在每一层递归中，划分操作的时间复杂度是 O(n)，其中 n 是当前数组的长度。
2. 递归的层数为 log n
在理想情况下，快速排序的每次递归都能将数组大致划分为相等的两部分，即每次递归之后，数组的规模缩小为原来的 1/2。这个过程相当于将问题规模递归地减半，直到数组大小缩减到 1。
因此，总共需要递归 log n 层（递归树的高度），这里的 log n 表示递归树的层数，也就是快速排序的递归深度。
3. 总时间复杂度为 O(n log n)
- 每层的时间复杂度：在递归树的每一层，需要
O(n)的时间来对数组进行划分。 - 递归树的层数：递归树的高度为
log n，表示总共要递归log n层。
因此，整个快速排序的总时间复杂度就是：
总时间=每层所需的时间×递归的层数=O(n)×O(logn)=O(nlogn)
递归树示意：
可以将快速排序的递归过程看作是一个递归树，每一层是对整个数组的遍历，每一层都需要 O(n) 的时间来进行划分。递归树的层数是 log n，总共 log n 层。
举例说明递归树结构：
O(n)
----------------
| |
O(n/2) O(n/2)
------- -------
| | | |
O(n/4) O(n/4) O(n/4) O(n/4)
----------------------------
... (共 log n 层)
4. 平均时间复杂度为 O(n log n) 的解释
在理想情况下，每次划分都能把数组平分成两半，快速排序的递归树的高度为 log n。每一层递归处理的元素总数为 n（即整个数组的长度），由于有 log n 层，所以整个快速排序的总时间复杂度为 O(n log n)。
5. 总结：
- 每一层快速排序的递归操作需要
O(n)的时间来进行划分。 - 总共有
log n层递归，即递归树的高度为log n。 - 因此，快速排序的平均时间复杂度是
O(n log n)。
不过需要注意，在最坏情况下（当每次划分都极不平衡，如数组是完全有序的），递归树的高度会退化为 n，此时时间复杂度为 O(n^2)。通过随机化选择基准元素，可以有效避免这种最坏情况的发生，从而保证平均时间复杂度为 O(n log n)。