【数据结构和算法】八大排序(三)
目录
- 说明
- 计数排序
- 堆排序
说明
排序算法,来到最后一章了,快来看看该学完有什么启发吧。
计数排序
顾名思义:排序需要计算待排序数据的数量。
过程:(1)我们需要事先知道这个待排序序列的数值范围,然后创建一个等长度的数组
(2)数值从头到位遍历一次,,如果遇见,就a[x]++;
(3)最后从数组依次输出
由此可见,计数排序的时间复杂度为O(n);
但是需要创建一个变化的数组,可大可小完全由数据分身来定。和之前学习的排序不太一样。
难度不大,了解即可
如图:
代码实现
#include #include using namespace std;int main(){ int a[] = {1,5,6,3,4,5,2,44,56,7,5,44,5,1,12,5,4,12,45};int t = sizeof(a)/sizeof(int); //根据观察(最小值为1,最大值为56) int count[57] = {0}; //加入 for(int i = 0; i < t; i++){ count[a[i]]++; } //输出 for(int i = 0; i < 57; i++){ while(count[i] > 0){ cout<<i<<" "; count[i]--; } }}
可以看到,这里我创建了一个长度为57的数组,实际过程无法预测。虽然速度很快,但同时也有牺牲空间的风险。但是随着时代的发展,这点内存相比O(n)的复杂度而言,往往不是很重要。
堆排序
堆排序是利用了数据结构堆得特性来进行排序的,在掌握了之前那么多的排序方法之后,对于新手来说,这种看起来也就不是那么好接受了。等你学完二叉树,在来看这个排序的时候,相信也会变得相对来说简单很多。
问:什么是堆?
堆是一种特殊的数据结构,堆通常是一个可以被看做一棵完全二叉树的数组对象。
问:堆有什么用?
(1)模拟实现优先队列(这个以后再看吧)
(2)排序(大顶堆,小顶堆)
(3)合并多个有序队列
等。
问:什么是大顶堆,什么是小顶堆?
大顶堆,每个结点的值都大于或等于其左右孩子结点的值(升序)
小顶堆反之。
lefrtson = 2dad + 1;
rightson = 2dad + 1 + 1;
a[dad] >= a[2dad + 1] && a[dad] >= a[2dad + 1 + 1] (大顶堆)
如图
实现过程:
大致:先建立一个大顶堆,然后用最后一个结点和根节点,交换位置。
在去掉最后一个位置不看,再次建立大顶堆。
这就会导致从后往前排列
具体看代码
代码实现
#include #include #include using namespace std;void max_heapify(int arr[], int start, int end) { //建立好子父结点的关系 int dad = start; int son = dad * 2 + 1; while (son <= end) { //不能越界 if (son + 1 <= end && arr[son] < arr[son + 1])//比较两个子节点的大小,选择较大的 son++; //判断是否满足大顶堆要求,不满足则改正 if (arr[dad] > arr[son]) return; else { swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } }}void heap_sort(int arr[], int len) { //获取大顶堆 for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); // 有了大顶堆后直接和最后一个数换个位置,然后以len-1为边界重新建立一个大顶堆,循环往复 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); }}int main(){ int a[] = {1,5,6,3,4,5,2,44,56,7,5,44,5,1,12,5,4,12,45};int t = sizeof(a)/sizeof(int); heap_sort(a,t); for(int i =0 ;i < t; i++){ cout<<a[i]<<" "; }}
summary:
堆排序的结构比较复杂,不建议这里主要传递的是一个思想。实际应用,在我看来,前面七个完全可以成为他的替代品。
排序到这里就暂告一段落了。
下期预告:二分查找。
学好数据结构与算法,真的走遍天下都不怕!