• 售前

  • 售后

热门帖子
入门百科

选择排序+堆排序

[复制链接]
东阿制造 显示全部楼层 发表于 2022-1-16 10:41:13 |阅读模式 打印 上一主题 下一主题
目次
选择排序
根本头脑
图解
 代码
复杂度与稳固性
堆排序
根本头脑
图解
 代码
复杂度与稳固性

选择排序

根本头脑

  每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。  图解

   给定如下数组,排成升序:     1.从五个数值中选定最大的数字5,与末了一个数值1举行交换:

 2.从剩下四个数值中选定一个最大的,与末了一个数值3举行交换:

3.从剩下的三个数值中选定一个最大的,与末了的数值1举行交换:

 4.从剩下两个数值中选定一个最大的,与末了的数值1举行交换,完成排序:

 代码

  1. void SelectSort(int* arr,int size){//选择排序
  2.         for (int i = 0; i < size - 1; i++){
  3.                 int pos = 0;//每次从第一个值开始选
  4.                 for (int j = 1; j < size-i; j++){
  5.                         if (arr[j]>arr[pos]){
  6.                                 pos=j;//记录最大值的位置
  7.                         }
  8.                 }
  9.                 Swap(&arr[pos],&arr[size-1-i]);
  10.         }
  11. }
复制代码
 代码中,pos纪录数组中最大值的位置,每一轮比力都会把最大值放置在:size-i的位置,从而实现了选择排序。
复杂度与稳固性

时间复杂度:n个元素,举行n-1轮选则,每轮举行比力的次数从n-1递减到1。以是根本语句的实行次数满足等差序列,举行盘算去掉系数后复杂度为:O(N^2)
空间复杂度:没有利用额外空间,复杂度为O(1)
稳固性:有跨区间交换,不稳固
堆排序

根本头脑

  堆排序 (Heapsort) 是指利用堆积树(堆)这种数据结构所操持的一种排序算法,它是选择排序的一种。它是 通过堆来举行选择数据。必要留意的是排升序要建大堆,排降序建小堆。  图解

  在之前的文章中已经具体报告了建堆的过程 (3条消息) 堆的实现(C语言)_Enthusiastic_boy的博客-CSDN博客_c语言堆的实现 ,那么接下来就来直接利用堆来举行排序,如下图中有一大堆:    1.利用堆删除的头脑,起首交换堆顶元素和堆末了一个元素:

 2.撤消堆末了一个元素的剩余部门,从堆顶开始举行建堆:

 3.交换上图赤色部门的堆顶元素4和末了元素1:

 4.对上图赤色圈起来部门举行建堆:

 5.交换上图赤色圈起来部门的堆顶元素和末了元素:

 6.对上图赤色圈起来的部门举行建堆:

 7.交换上图中赤色圈起来部门的堆顶元素和末了元素,完成排序:

 代码

  1. void HeapAdjust(int* arr,int size,int parent){//向下调整
  2.         int child = parent * 2 + 1;
  3.         while (child<size){
  4.                 if (child + 1 < size&&arr[child + 1] > arr[child]){
  5.                         child = child + 1;
  6.                 }
  7.                 if (arr[child] > arr[parent]){
  8.                         Swap(&arr[child],&arr[parent]);
  9.                         parent = child;
  10.                         child = child * 2 + 1;
  11.                 }
  12.                 else{
  13.                         return;
  14.                 }
  15.         }
  16. }
  17. void HeapSort(int* arr,int size){//堆排序
  18.         int parent = (size - 2) / 2;
  19.         for (; parent >= 0; parent--){//建堆
  20.                 HeapAdjust(arr,size,parent);
  21.         }
  22.         for (; size>1; size--){//利用堆删除的思想进行堆排序
  23.                 Swap(&arr[0],&arr[size-1]);
  24.                 HeapAdjust(arr, size-1, 0);
  25.         }
  26. }
复制代码
留意:建堆时,可以以为数组中元素总数稳定,parent的值在不绝变革。举行堆排序时可以以为parent的值稳定,不停是0,而数组元素个数在变革。这两个过程刚好相反。
复杂度与稳固性

时间复杂度:排序时每次都是从堆顶开始建堆,以是建堆的时间复杂度为O(logN),而要举行N次建堆,以是总的堆排序时间复杂度为:O(NlogN)。
空间复杂度:没有借助辅助空间,以是复杂度为:O(1)
稳固性:举行了跨区间交换,不稳固

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作