当前位置: 首页> 游戏> 单机 > 堆排、快速排序、归并排序等总结

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

时间:2025/7/11 15:32:54来源:https://blog.csdn.net/gma999/article/details/141718743 浏览次数:0次

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

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

关键字:堆排、快速排序、归并排序等总结

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: