【数据结构与算法篇】 手撕八大排序算法之选择排序

简介: 【数据结构与算法篇】 手撕八大排序算法之选择排序

👻内容专栏: 《数据结构与算法篇》

🐨本文概括:选择排序包括直接选择排序与堆排序,本篇讲述直接选择排序与堆排序的思想及实现、复杂度及稳定性的分析。

🐼本文作者: 花 蝶

🐸发布时间:2023.8.27

一、直接选择排序

基本思想

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

若将以上思想拆分成若干步骤,如下:

  • 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
  • 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
  • 在剩余的array[i]–array[n-2](array[i+1]–array[n-1])集合中,重复上述步骤,直到集合剩余1个元素

动图演示

👇小的优化

🔗:动图中,利用一趟中找出最小的放到序列的起始位置,直到数据排列完,其实,我们不妨想想可以一趟找出最小的数据和待排序中最左边的数据进行交换,找出最大的数据和待排序中最后边的数据进行交换!

首先,确定起始位置和末端位置的下标,我们可以用beginend表示,在beginend区间内,遍历一遍,找出最大元素下标maxii和最小元素下标mini,小的元素换到左边,大的元素换到右边,之后我们需要begin++end--,依次缩小区间,直到走到 begin 大于或等于 end结束

⚠️需要注意一个特殊的情况

观察下图,maxi在最左边的位置,当找到mini(元素0)之后需要换到左边时,将原本maxi的位置(元素9)给换走了,这就导致最大值与end位置的数据交换时,不是maxi为下标的元素了,所以针对begin等于maxi的情况,我们需要在把最大值换到右边之前进行修正一下。

代码实现

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
//直接选择排序
void SelectSort(int* a, int n)
{
  int begin = 0, end = n - 1;
  while (begin < end)
  {
    int maxi = begin, mini = begin;
    for (int i = begin; i <= end; i++)
    {
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
      if (a[i] < a[mini])
      {
        mini = i;
      }
    }
    //小的换到左边
    Swap(&a[begin], &a[mini]);
    //如果maxi与begin重叠,需要进行修正
    if (maxi == begin) maxi = mini;
    //大的换到右边
    Swap(&a[end], &a[maxi]);
    begin++;
    end--;
  }
}

直接选择排序特性

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

二、堆排序

走到这里,大家需要首先要弄明白什么是堆?

详解具体堆的概念,堆的实现、向上向下调整算法,可以点击这篇文章 【传送门】深入浅出——二叉树

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆

基本思想

1.建堆(Heapify): 首先将待排序的数据构建成一个堆。可以通过从最后一个非叶子节点开始,逐步向前调整节点的位置,(这个称为向下调整算法建堆(倒着调整),具体时间复杂度分析可以看上面标题下给出的文章。)使得每个子树都满足堆的性质。这个过程称为“堆化”。

2.排序: 一旦建立了堆,最大(或最小)元素就位于堆的根节点。将根节点与堆的最后一个元素交换位置,然后将堆的大小减一,使得最大元素“沉”到数组末尾。接着重新堆化剩余的堆,使得次大的元素浮到根节点。

3.重复: 重复上述步骤,直到堆的大小减为1,此时整个数组已经有序。

建堆

例如,以下图中为一个完全二叉数,但还不具有堆的性质,这里我们以排升序为例,所以我们需要将它构建为大堆,需要从最后一个非叶子节点开始倒着往下调整(为什么不直接使用向上调整?具体可看上面给出的文章,因为经过对比计算,向上调整的时间复杂度高于向下调整的时间复杂度),也就是最后一个叶子节点的父节点((n - 1 - 1) / 2),根据父节点parent的下标位置,求出左孩子节点child,公式:child = parent * 2 + 1,为什么只求出左孩子节点?我们只需要把左孩子与右孩子进行比较,child + 1就能得到右孩子,右孩子存在的情况下,且右孩子大于左孩子,那么就child++,将左孩子节点更新为右孩子节点。然后再去父亲节点进行比较,如果孩子节点大于父亲节点,那么就与父亲交换。需要注意的是,交换之后,一定需要往下继续调整,继续迭代走,即:parent = child ; child = parent * 2 + 1;

排序

建出大堆之后,数组中的首尾数据进行交换,最小的数据(堆顶)放到了最后的位置,除去最后一个数据,对堆进行向下调整,再把堆顶(此时是次小的数据),与倒数第二个位置的数据交换……以此类推,整个调整完后,数组中的数据依次排列就是一个升序序列。

代码实现

void AdjustDown(int* a, int n, int parent)
{
  int child = parent * 2 + 1;
  while (child < n)
  {
    //假设左孩子小于父亲
    //如果右孩子还小于左孩子,则child ++
    if (child + 1 < n && a[child + 1] > a[child]) child++;
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
//堆排序 时间复杂度为:O(N*logN)
void HeapSort(int* a, int n)
{
  //建大堆(升序)
  //O(N)
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  //堆顶元素和最后一个交换
  //再向下调整
  //O(N*logN)
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    end--;
  }
}

堆排序特性

  • 时间复杂度: 堆排序的平均时间复杂度为 O(N*log N),其中 N 是待排序数组的长度。构建堆的时间复杂度为O(N),从堆顶调整堆的操作需要O(log n)的时间,而总共需要执行交换操作 n 次,即 O(N + N*logN)O(N*log N)
  • 空间复杂度: 堆排序的空间复杂度为 O(1),即排序过程中只需要很少的额外空间来存储临时变量.
  • 稳定性: 堆排序是不稳定的排序算法,即在排序过程中,相等元素的相对顺序可能会发生改变。这是因为堆排序涉及到元素交换的操作,可能会导致相同值的元素交换位置。

更多数据结构与算法系列文章👉😉==> 【传送门】

目录
相关文章
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
74 1
|
3月前
|
搜索推荐
选择排序与其它排序算法比较
选择排序与冒泡排序同属O(n²)排序算法,但选择排序不稳定。相比堆排序,虽每轮均选最大元素,但选择排序基于线性结构,效率较低,而堆排序利用大顶堆结构提升了选择效率。
38 0
|
3月前
|
存储 搜索推荐 算法
加密算法、排序算法、字符串处理及搜索算法详解
本文涵盖四大类核心技术知识。加密算法部分介绍了对称加密(如 AES)、非对称加密(如 RSA)、哈希摘要(如 SHA-2)、签名算法的特点及密码存储方案(加盐、BCrypt 等)。 排序算法部分分类讲解了比较排序(冒泡、选择、插入、归并、快排、堆排序)和非比较排序(计数、桶、基数排序)的时间复杂度、适用场景及实现思路,强调混合排序的工业应用。 字符串处理部分包括字符串反转的双指针法,及项目中用正则进行表单校验、网页爬取、日志处理的实例。 搜索算法部分详解了二分查找的实现(双指针与中间索引计算)和回溯算法的概念(递归 + 剪枝),以 N 皇后问题为例说明回溯应用。内容全面覆盖算法原理与实践
131 0
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
84 0
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
194 10
 算法系列之数据结构-二叉树
|
8月前
|
存储 搜索推荐 算法
算法系列之排序算法-堆排序
堆排序(Heap Sort)是一种基于堆数据结构的比较排序算法。它的时间复杂度为 $O(nlogn)$,并且是一种原地排序算法(即不需要额外的存储空间)。堆排序的核心思想是利用堆的性质来维护一个最大堆或最小堆,然后逐步将堆顶元素(最大值或最小值)取出,放到数组的末尾,最终得到一个有序的数组。
185 8
算法系列之排序算法-堆排序
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
159 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
201 22
|
7月前
|
JavaScript 前端开发 算法
JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
Array.sort() 是一个功能强大的方法,通过自定义的比较函数,可以处理各种复杂的排序逻辑。无论是简单的数字排序,还是多字段、嵌套对象、分组排序等高级应用,Array.sort() 都能胜任。同时,通过性能优化技巧(如映射排序)和结合其他数组方法(如 reduce),Array.sort() 可以用来实现高效的数据处理逻辑。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
202 30

热门文章

最新文章