堆排、快速排序、归并排序等总结

十大经典排序算法大梳理 (动图+代码)（动态图参考）

排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	数据对象稳定性
冒泡排序	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;
}