常见排序算法汇总
排序算法汇总
这篇文章说明下排序算法，直接开始。
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;// 在已排序部分中找到合适的位置插入 keywhile (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)。