H5W3
当前位置:H5W3 > 其他技术问题 > 正文

选择排序算法是如何选择的?

简单介绍

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

基本概念

  1. 选择排序是一种简单直观的排序算法。
  2. 它先从未排序的序列中找到最小的元素,放在序列的起始位置,然后再从剩余未排序元素中继续寻找最小的元素并放在已排序序列的末尾。以此类推,直到全部待排序数据元素排完。

原理讲解

  • 以41 34 19 17 2这个序列为例说明选择排序的实现原理
  1. 未开始遍历时,效果如下图
    在这里插入图片描述
  2. 第一次遍历
    从该序列中找到最小元素2,将元素2和序列起始位置的数据41交换位置,效果如下图

    在这里插入图片描述

    此时元素2已排序,序列中34 19 17 41未排序,效果如下图

    在这里插入图片描述
  3. 第二次遍历
    从序列中未排序的元素中找到最小元素17,将元素17和已排序序列末尾元素34交换位置,效果如下图

    在这里插入图片描述

    此时元素2 17已排序,序列中19 34 41未排序,效果如下图

    在这里插入图片描述
  4. 第三次遍历
    从序列中未排序的元素中找到最小元素19,此时元素19比已排序序列末尾元素17大且元素19的位置已比元素17的位置靠后,故元素19和元素17不需要移动位置,效果如下图

    在这里插入图片描述
  5. 第四次遍历
    从序列中未排序的元素中找到最小元素34,此时元素34比已排序序列末尾元素19小且元素34的位置已比元素19的位置靠后,故元素34和元素19不需要移动位置,效果如下图

    在这里插入图片描述
  6. 第五次遍历
    从序列中未排序的元素中找到最小元素41,此时元素41已未序列最后一个元素,故不需要比较,最终效果如下图

    在这里插入图片描述

时间复杂度

排序算法的时间复杂度是和算法中相邻两个数据的比较次数移动次数成正比的。具体如下:

数据个数 比较次数 最大移动次数 最小移动次数
1 0 0 0
2 1 1 0
3 3 2 0
4 6 3 0
5 10 4 0
10 45 5 0
N 1/2N(N-1) (N-1) 0

所以根据时间复杂度的概念,冒泡算法的时间复杂度为O(N^2)

效果展示

在这里插入图片描述

源码下载

  • 请在公众号中回复“算法源码”即可获得十大经典排序算法源码

更多算法学习请关注我的公众号

在这里插入图片描述

本文地址:H5W3 » 选择排序算法是如何选择的?

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址