选择排序与堆排序

简介: 选择排序与堆排序



1.选择排序

1.1选择排序的基本思想

基本思想:

遍历一遍待排数据,将最大值与最小值的下标记录,然后把最小值与数组最前面的数据交换,将最大值与数组最后一个数据交换,这样遍历一遍,就将最大值和最小值放到了正确的位置;

将除了上面已经在正确位置的数据,将剩下的数据看成待排数组,然后重复上述操作,这样,遍历2/n次,就可以将所有数据排好序;

图解:

1.2代码实现
void SelectSort(int* a, int n)
{
  for (int j = 0; j < n/2; j++)
  {
     //假设数组中最大最小值的下标是j
    int maxi = j;
    int mini = j;
    for (int i = j; i < n -j; i++)
    {
    //有比max大的,就改变下标
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    //有比min小的,就改变下标
      if (a[i] < a[mini])
      {
        mini = i;
      }
    }
   //将找到的最小值放到待排数组最前面
    Swap(&a[mini], &a[j]);
   //如果最大值在待排数组最前面,在把最小值换到前面的时候,会将最大值的下标改变
   //所以这里需要更新最大值的下标,如上图第三步中8的交换
    if (maxi == j)
    {
      maxi = mini;
    }
   //将最大值放到待排数组的后面
    Swap(&a[maxi], &a[n - 1-j]);
  }
}
1.3性能分析

最坏情况:逆序

时间复杂度:O(N^2)

空间复杂度:O(1)

2.堆排序

要了解堆排序要先了解堆,堆的相关知识http://t.csdnimg.cn/GoxJO

2.1堆排序的基本思想

利用大堆的特点,父亲都大于孩子,所以堆的根结点是整个二叉树中的最大数;

先将根结点与树中最后一个节点交换(对应在数组中,就是将数组中第一个数据与最后一个数字交换),这样,最大的数就在数组最后,在正确的位置上了,交换过后,(树的左右子树都是大堆)这样再利用向下调整建堆,将剩下的数据变成大堆,这样最大的数据又在根结点了,重复上面操作就可以将所有数据变成有序;

图解:

2.2代码实现
void Adjustdown(int* a, int parent, int n)
{
  assert(a);
  int child = parent * 2 + 1;
  while (child < n)
  {
    //假设左孩子大
    if (child + 1 < n && a[child] < a[child + 1])
    {
        //假设不成立,调整
      child = child + 1;
    }
    if (a[child] > a[parent])
    {
      Swap(&a[parent], &a[child]);
      parent = child;
      child = child * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void HeapSort(int* a, int n)
{
  assert(a);
  //从最后一个非叶子节点向下调整
  //n-1是最后一个结点,(n-1-1)/2是它父亲
  for (int i = (n-1-1) / 2; i >= 0; i--)
  {
    Adjustdown(a, i, n);
  }
  int end = n-1;
  while (end > 0)
  {
    Swap(&a[0],&a[end]);
    Adjustdown(a,0, end);
    end--;
  }
}
2.3性能分析

数据个数为N,则高度为:logN

N个数据,每个数据向下调整,时间复杂度需要logN

时间复杂度:O(N*logN)

空间复杂度为:O(N)


目录
相关文章
|
11天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1244 5
|
10天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1225 87
|
11天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1804 13
|
20天前
|
人工智能 运维 安全
|
4天前
|
资源调度
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
236 127
|
4天前
|
前端开发
Promise的then方法返回的新Promise对象有什么特点?
Promise的then方法返回的新Promise对象有什么特点?
181 2