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

【数据结构与算法】十大经典排序算法-选择排序

🌟个人博客:www.hellocode.top
🏰Java知识导航:Java-Navigate
🔥CSDN:HelloCode.
🌞知乎:HelloCode
🌴掘金:HelloCode
⚡如有问题,欢迎指正,一起学习~~


选择排序是一种简单但低效的排序算法,其基本思想是每次从待排序序列中选出最小(或最大)的元素,然后将其放置在已排序序列的末尾(或开头)。通过逐步选择出最小(或最大)元素,将其插入到已排序序列中,从而逐步构建有序序列。

基本思想

  1. 将数组分为已排序区和未排序区。
  2. 在未排序区中找到最小(或最大)的元素。
  3. 将找到的最小(或最大)元素与未排序区的第一个元素交换位置,将该元素放入已排序区。
  4. 重复步骤 2 和 3,直到未排序区为空。

和插入排序很像,区别就在于选择和插入,根据动画体会一下,选择排序的重点是选择出未排序中最小(大)的,不断的加入到已排序区中(选择对的元素插入已排序区末尾)

代码实现

代码和插入排序可以对比着来写,也很简单,两层for循环,外层用来控制已排序的元素个数(选择好的待排序元素该放入的位置),内层for用来遍历选择出最小(大)的元素,具体代码如下:

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月09日 21:21*/
public class SelectionSort {public static void main(String[] args) {int[] arr = {2, 12, 42, 13, 43, 85, 91, 23, 12, 4, 5, 8, 1, 9, 88, 66, 33, 123};System.out.println("排序前:"+ Arrays.toString(arr));selectionSort(arr);System.out.println("排序后:"+ Arrays.toString(arr));}public static void selectionSort(int[] arr){// 两层for循环,外层i代表已排序的元素个数for(int i = 0; i < arr.length - 1; i++){// 内层 for 进行选择,在待排序的元素中选择最小的进行排序int min = i;for(int j = i + 1; j < arr.length; j++){if(arr[j] < arr[min]){// j更小,更新minmin = j;}}// 将选择出的最小元素插入已排序元素中int temp = arr[i];arr[i] = arr[min];arr[min] = temp;}}
}

测试:

排序前:[2, 12, 42, 13, 43, 85, 91, 23, 12, 4, 5, 8, 1, 9, 88, 66, 33, 123]
排序后:[1, 2, 4, 5, 8, 9, 12, 12, 13, 23, 33, 42, 43, 66, 85, 88, 91, 123]

优化

虽然选择排序的时间复杂度不容易通过优化得到显著的提升,但一些小优化可以改善算法的实际性能。

  • 可以在内层循环中同时找到最小和最大元素,从而减少交换的次数。
  • 可以在选择最小(大)元素时采用不同的方法来代替逐个遍历,提高效率。

总结

优点

  1. 简单易懂:选择排序是一种简单直观的排序算法,易于实现。
  2. 稳定性:在相等元素的情况下,选择排序是一种稳定的排序算法。

缺点

  1. 低效性:选择排序的时间复杂度为 O(n^2),即使在最佳情况下也需要进行多次比较和交换,效率较低。
  2. 不适合大规模数据:由于时间复杂度的限制,选择排序不适合对大规模数据进行排序。

复杂度

  • 时间复杂度
    • 平均时间复杂度:O(n^2)
    • 最好情况时间复杂度:O(n^2)
    • 最坏情况时间复杂度:O(n^2)
  • 空间复杂度:原地排序,空间复杂度为 O(1)。

使用场景

由于其低效性,选择排序在实际应用中较少使用。在需要排序的数据规模较小时,选择排序可能是一个合理的选择。然而,对于大规模数据,其他高效的排序算法(如快速排序、归并排序)通常更为适用。选择排序适用于教学和学习排序算法的基本原理,但在实际应用中,通常会选择更优的排序算法。

当使用选择排序时,应特别注意其时间和空间复杂度的说明是基于固定的数据集。在实际情况中,选择排序的性能可能因为一些特定因素而有所不同,因此在特定情况下选择排序可能表现更好。

http://www.lryc.cn/news/126399.html

相关文章:

  • 【Spring专题】Spring之Bean的生命周期源码解析——阶段一(扫描生成BeanDefinition)
  • 【C#】判断打印机共享状态
  • 运维监控学习笔记7
  • 【业务功能篇64】maven加速 配置settings.xml文件 镜像
  • Spring Boot(六十四):SpringBoot集成Gzip压缩数据
  • Mac安装opencv后无法导入cv2的解决方法
  • 【题解】按之字形顺序打印二叉树
  • 后端人员如何快速上手vue
  • 基于Prometheus监控Kubernetes集群
  • 【数据分析】pandas (三)
  • nvm命令
  • 从此已是义无反顾
  • Element组件浅尝辄止2:Card卡片组件
  • “深入剖析Java多态:点燃编程世界火花“
  • golang官方限流器rate包实践
  • [windows]MAT- 下载及安装
  • 数组模拟环形队列详解
  • 《论文阅读12》RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clouds
  • elementPlus使用el-icon
  • 预测知识 | 神经网络、机器学习、深度学习
  • 【Linux】进程的基本属性|父子进程关系
  • CCF考试:201809-1 卖菜(java代码)
  • android wifi扫描 framework层修改扫描间隔
  • webstorm debug调试vue项目
  • 嵌入式linux的八股文之旅 DAY1
  • 同创永益郑阳|与数智化共舞·业务稳定性保障新动力
  • 史上最全的Qt控件
  • 星星之火:国产讯飞星火大模型的实际使用体验(与GPT对比)
  • 传输控制协议TCP
  • jmeter中用户参数和用户定义的变量的区别