当前位置: 首页 > article >正文

[数据结构]排序之 直接选择排序

1 基本思想:
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的
数据元素排完 。
2 直接选择排序 :
在元素集合 array[i]--array[n-1] 中选择关键码最大 ( ) 的数据元素
若它不是这组元素中的最后一个 ( 第一个 ) 元素,则将它与这组元素中的最后一个(第一个)元素交换
在剩余的 array[i]--array[n-2] array[i+1]--array[n-1] )集合中,重复上述步骤,直到集合剩余 1 个元素
// 选择排序
void SelectSort(int* a, int n)
{
       int left = 0;
       int right = n - 1;
       while (left < right)
       {
              int mini = left, maxi = left;//记录下标
              for (int i = left+1; i <= right; i++)
              {
                      if (a[i] < a[mini])
                      {
                             mini = i;
                      }
                      if (a[i] > a[maxi])
                      {
                             maxi = i;
                      }
              }
              Swap(&a[left], &a[mini]);
              // 检查最大值位置是否被改变
              if (maxi == left) {
                      maxi = mini;
              }
              Swap(&a[right], &a[maxi]);
              ++left;
              --right;
       }
}
为什么要在两个Swap之间写一个if?
考虑这样一种情况:当  left  位置的元素就是当前未排序部分的最大值时,在第一次交换  a[left]    a[mini]  之后,原本  maxi  指向的最大值元素已经被交换到了  mini  位置,而时  maxi  仍然指向原来的  left  位置,所以在进行第二次交换  a[right]    a[maxi]  时,实际上交换的并不是最大值,从而导致排序结果出错。
直接选择排序的特性总结:
1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
2. 时间复杂度: O(N^2)  最坏情况和最好情况都是 O(N^2),之前的序列对排序没有影响,所以直接选择排序很烂,基本不会用
3. 空间复杂度: O(1)
4. 稳定性:不稳定
原文地址:https://blog.csdn.net/m0_74978334/article/details/146273824
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586542.html

相关文章:

  • pytest快速入门 - 目录:半天掌握pytest
  • 数据结构(泛型)
  • OracleCdc和MysqlCdc区别详解
  • 【一句话经验】ubuntu vi/vim 模式自动设置为paste
  • VBA+FreePic2Pdf 找出没有放入PDF组合的单个PDF工艺文件
  • 【CF】Day7——Codeforces Round 919 (Div. 2) BC
  • 表单 schema 配置化
  • L3-1 夺宝大赛
  • Manus 一码难求,MetaGPT、OpenManus、Camel AI 会是替代方案吗?
  • MESH网络技术解析
  • Ant Design Vue UI框架快速打造后台管理管理案例
  • K8S学习之基础三十:k8s中RBAC 的核心概念
  • 华为OD机考真题 Linux 发行版的数量(Java)
  • Android UI 组件系列(一):TextView 使用详解与常见属性
  • Fast dds 内存调优
  • 【前端实战】一文掌握响应式布局 - 多设备完美适配方案详解
  • 【DeepSeek】蓝耘智算 | 中国AI新范式:蓝耘智算云+DeepSeek R1部署实战教程
  • Spring @Bean注解使用场景二
  • 【PHP】获取PHP-FPM的状态信息
  • Python JSON模块详解:从入门到高级应用