- 说明
- 计数排序
- 堆排序
排序算法,来到最后一章了,快来看看该学完有什么启发吧。
计数排序顾名思义:排序需要计算待排序数据的数量。
过程:(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:
堆排序的结构比较复杂,不建议这里主要传递的是一个思想。实际应用,在我看来,前面七个完全可以成为他的替代品。
排序到这里就暂告一段落了。
下期预告:二分查找。
学好数据结构与算法,真的走遍天下都不怕!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)