> 文档中心 > 【数据结构和算法】八大排序(三)

【数据结构和算法】八大排序(三)

目录

  • 说明
  • 计数排序
  • 堆排序

说明

排序算法,来到最后一章了,快来看看该学完有什么启发吧。

计数排序

顾名思义:排序需要计算待排序数据的数量。
过程:(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 = 2
dad + 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:
堆排序的结构比较复杂,不建议这里主要传递的是一个思想。实际应用,在我看来,前面七个完全可以成为他的替代品。
排序到这里就暂告一段落了。
下期预告:二分查找。

学好数据结构与算法,真的走遍天下都不怕!