十大经典排序算法大梳理 (动图+代码)(动态图参考)
排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
---|---|---|---|---|
冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 |
选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 |
插入排序 | O(n2) | O(n2) | O(1) | 稳定 |
快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
归并排序 | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
希尔排序 | O(n*log2n) | O(n2) | O(1) | 不稳定 |
计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
桶排序 | O(n) | O(n) | O(m) | 稳定 |
基数排序 | O(k*n) | O(n2) | 稳定 |
堆排序
基本概念总结
堆的性质
- 堆中的某个节点一定是不大于或者不小于其父节点的
- 堆总是一个完全二叉树
排序实现
向下调整(从父亲到儿子)
// 堆的向下调整(建立大根堆)
void AdjustDown(vector<int>& arr, int parent)
{int n = arr.size() - 1;int child = parent * 2 + 1;//正常父节点即是下标为0的节点while (child < n){//找到数值最大的孩子if (child + 1 < n && arr[child + 1] > arr[child]) {++child;}if (arr[child] > arr[parent]) {swap(arr[child], arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}
向上调整(从儿子到父亲)
//堆的向上调整
void AdjustUp(vector<int>& arr, int child)
{int parent = (child - 1) / 2;while (child > 0) {if (arr[child] > arr[parent]) {swap(arr[child], arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
使用STL实现大根堆和小根堆的方法
void head()
{//默认大根堆priority_queue<int> heap_max;//小根堆priority_queue<int, vector<int>, greater<int>> heap_min;
}
STL优先级队列实现堆
priority_queue
- 默认是大堆,每次top()方法的时候,都会返回当前队列中最高优先级元素
- 可以通过自定义排序,实现小堆,或者按照自己的需求进行排序
大堆使用演示
#include <iostream>
#include <queue>
#include <vector>int main() {// 定义一个最大堆优先队列(默认情况下)std::priority_queue<int> maxHeap;// 定义一个最小堆优先队列std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;// 插入元素maxHeap.push(10);maxHeap.push(20);maxHeap.push(15);// 获取并移除最大元素std::cout << "Max element: " << maxHeap.top() << std::endl; // 输出 20maxHeap.pop();std::cout << "Max element after pop: " << maxHeap.top() << std::endl; // 输出 15return 0;
}
自定义小根堆的方法
- 通过函数重载,重写函数对象
- lambda表达式实现
- 函数指针实现自定义排序
- 复杂对象中可以自定义排序规则
#include <iostream>
#include <queue>
#include <vector>// 自定义比较器函数对象
struct Compare {bool operator()(int a, int b) {return a > b; // 实现小顶堆,即a<b时返回false,表示a优先级更高}
};int main() {// 使用自定义比较器创建小顶堆std::priority_queue<int, std::vector<int>, Compare> minHeap;// 插入元素minHeap.push(30);minHeap.push(10);minHeap.push(20);// 获取并移除优先级最高(值最小)的元素std::cout << "Min element: " << minHeap.top() << std::endl; // 输出 10minHeap.pop();std::cout << "Next min element: " << minHeap.top() << std::endl; // 输出 20return 0;
}
#include <iostream>
#include <queue>
#include <vector>int main() {// 使用lambda表达式作为比较器auto compare = [](int a, int b) {return a > b; // 实现小顶堆};// 使用自定义比较器创建小顶堆std::priority_queue<int, std::vector<int>, decltype(compare)> minHeap(compare);// 插入元素minHeap.push(40);minHeap.push(15);minHeap.push(25);// 获取并移除优先级最高(值最小)的元素std::cout << "Min element: " << minHeap.top() << std::endl; // 输出 15minHeap.pop();std::cout << "Next min element: " << minHeap.top() << std::endl; // 输出 25return 0;
}
#include <iostream>
#include <queue>
#include <vector>// 自定义比较函数
bool compare(int a, int b) {return a > b; // 实现小顶堆
}int main() {// 使用函数指针作为比较器std::priority_queue<int, std::vector<int>, bool(*)(int, int)> minHeap(compare);// 插入元素minHeap.push(50);minHeap.push(20);minHeap.push(30);// 获取并移除优先级最高(值最小)的元素std::cout << "Min element: " << minHeap.top() << std::endl; // 输出 20minHeap.pop();std::cout << "Next min element: " << minHeap.top() << std::endl; // 输出 30return 0;
}
#include <iostream>
#include <queue>
#include <vector>// 定义一个结构体
struct Person {std::string name;int age;Person(std::string n, int a) : name(n), age(a) {}
};// 自定义比较器,按年龄排序
struct Compare {bool operator()(const Person& p1, const Person& p2) {return p1.age > p2.age; // 按年龄升序排序}
};int main() {// 使用自定义比较器std::priority_queue<Person, std::vector<Person>, Compare> pq;// 插入元素pq.emplace("Alice", 30);pq.emplace("Bob", 25);pq.emplace("Charlie", 35);// 获取并移除优先级最高(年龄最小)的元素std::cout << "Youngest person: " << pq.top().name << " (" << pq.top().age << ")" << std::endl;pq.pop();std::cout << "Next youngest person: " << pq.top().name << " (" << pq.top().age << ")" << std::endl;return 0;
}
快速排序
时间复杂度
- 平均时间复杂度: O(n log n)
- 最坏时间复杂度: O(n^2) (当数组已经是有序的,或者所有元素相等时)
- 空间复杂度: O(log n) (主要是递归栈的深度)
int getRandom(vector<int>&nums , int left , int right){int r = rand();return nums[r%(right-left+1)+left];}vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}void qsort(vector<int>&nums,int l, int r){if(l>=r) return;//1. 处理该区间内的三块数组int key = getRandom(nums,l,r);int i = l,left = l-1,right = r+1;//初始位置很重要while(i<right){//left和right指针的移动需要着重注意if(nums[i]<key){swap(nums[++left],nums[i++]);}else if(nums[i]==key){i++;}else{//i不++的原因:因为换过来的right位置还没有进行判断过swap(nums[--right],nums[i]);}}//2. 继续处理以key为基准的其他两区间的数组qsort(nums,l,left);qsort(nums,right,r);}
完整代码
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib> // 包含rand和srand函数using namespace std;// 获取区间内的随机元素
int getRandom(vector<int>& nums, int left, int right) {int r = rand();return nums[r % (right - left + 1) + left];
}// 快速排序的辅助函数
void qsort(vector<int>& nums, int l, int r) {if (l >= r) return;// 处理该区间内的三块数组int key = getRandom(nums, l, r);int i = l, left = l - 1, right = r + 1; // 初始位置while (i < right) {if (nums[i] < key) {swap(nums[++left], nums[i++]);} else if (nums[i] == key) {i++;} else {swap(nums[--right], nums[i]);}}// 继续处理以key为基准的其他两区间的数组qsort(nums, l, left);qsort(nums, right, r);
}// 快速排序的主函数
vector<int> sortArray(vector<int>& nums) {srand(time(NULL)); // 设置随机数种子qsort(nums, 0, nums.size() - 1);return nums;
}// 测试函数
int main() {vector<int> nums = {3, 6, 8, 10, 1, 2, 1, 5, 7, 9};cout << "Original array: ";for (int num : nums) {cout << num << " ";}cout << endl;nums = sortArray(nums);cout << "Sorted array: ";for (int num : nums) {cout << num << " ";}cout << endl;return 0;
}
归并排序
实现逻辑
归并排序,可以简单理解为将大数组拆分成小数组,然后小数组有序后合并成大数组
- 具体实现是借助递归,递归最终实现有序数组
- 注意,下图在代码执行层面,都是在原数组上直接进行变动数据,而不是另外使用数组存储对应数据
代码实现
//归并排序(稳定,最好O(n*log2n),最差O(n*log2n))
void mergeSort(vector<int>& arr, vector<int>& tmp, int left, int right)
{if (left >= right) return;//2.1 选择中间点,利用位运算判断中间点int mid = (left + right) >> 1;//2.2 将分好的左右区间,递归向下进行排序mergeSort(arr,tmp, left, mid);mergeSort(arr, tmp,mid + 1, right);//2.3 合并两个有序数组int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right) {tmp[i++] = arr[cur1] <= arr[cur2] ? arr[cur1++] : arr[cur2++];}//处理其中可能没有处理到的数组while (cur1 <= mid) tmp[i++] = arr[cur1++];while (cur2 <= right) tmp[i++] = arr[cur2++];//2.4 还原:将排序的数字放回到arr中for (int i = left; i <= right; ++i) {arr[i] = tmp[i - left];}
}
冒泡排序
#include <iostream>
#include <vector>void bubbleSort(std::vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {for (int j = 0; j < n - i - 1; ++j) {if (arr[j] > arr[j + 1]) {std::swap(arr[j], arr[j + 1]);}}}
}int main() {std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);for (int i : arr) std::cout << i << " ";return 0;
}
选择排序
#include <iostream>
#include <vector>void selectionSort(std::vector<int>& arr) {int n = arr.size();for (int i = 0; i < n - 1; ++i) {int minIdx = i;for (int j = i + 1; j < n; ++j) {if (arr[j] < arr[minIdx]) {minIdx = j;}}std::swap(arr[i], arr[minIdx]);}
}int main() {std::vector<int> arr = {64, 25, 12, 22, 11};selectionSort(arr);for (int i : arr) std::cout << i << " ";return 0;
}
插入排序
#include <iostream>
#include <vector>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;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];--j;}arr[j + 1] = key;}
}int main() {std::vector<int> arr = {12, 11, 13, 5, 6};insertionSort(arr);for (int i : arr) std::cout << i << " ";return 0;
}