选择排序详解(Selection sort)

简介: 选择排序详解

一、简单释义

1、算法概念

 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小 的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小元素,然后放到已排序的序列的末尾 。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

2、算法目的

 从要排序的序列中,按指定的规则 (文中以升序为例)选出某一元素,再依规定交换位置后达到排序 的目的。  

3、算法思想

 每一趟从待排序的数据元素中选择最小的一个元素作为首元素 ,以此类推。直到所有元素排完为止。

二、核心思想

先–在序列中找到最小元素,放到序列的起始位置作为已排序序列;

中–从剩余未排序元素中继续寻找最小元素,放到已排序序列的末尾;

后–重复上述步骤,直到所有元素均排序完成。

三、图形展示

4c92f3ba629545a386f24f8a5593acaa.png

 1、第一次排序:用第一个元素和后面的元素进行对比,2和8对比,8比2大继续向后对比,然后2和1对比,1比2小,拿1继续向后比。此时我们可以发现后面没有比1小的值了。但是根据选择排序的原则,还是需要继续和剩下的元素进行比较的指导比较到7才能确定最小值。最终第一次排序的结果是1和2交换了位置。

bc5e4a5bd8cc40f3a3176d1ccc7f4a58.png

 2、第二次排序:目前1是已经排好序的了,所以1不参与任何的对比。用第二个元素8和后面的元素进行对比,8和2对比,2比8小,拿2和后面的元素进行对比。一直对比到7,才能确定2是最小的元素。最终第二次排序的结果是8和2交换了位置。

f3c5455153314c6e99688669248af4f2.png

 3、第三次排序:用8和4进行对比,4比8小。把8放回。用4和后面的元素进行对比。4和9进行对比,4比9小,继续向后对比。4和5进行比较,4比5小,继续向后对比。4和7进行对比,4比7小,确定4是最小的元素。最终第三次排序的结果是8和4交换了位置。

eea96bd5c00a4712a07273526d805ad2.png

 4、第四次排序:用8和9进行对比,9比8大。继续向后对比。8和5进行比较,5比8小,用5和后面的元素进行对比。5和7进行对比,5比7小。确定5是最小的元素。最终第四次排序的结果是8和5交换了位置。

d7b385d45b6a4d3cbf67082337148974.png

 5、第五次排序:按照上面的步骤,以此类推。第五次排序的结果是9和7交换了位置。

65b81c91b87645f597741ab52689d12c.png

 6、第六、七次排序:第六次和第七次排序没有发生位置的交换。我们可以发现第五次的排序结果整个数组就已经是一个有序的数组的,但是选择排序算法还是进行了无用的排序错误。所以我们是可以优化算法的。

四、代码实现

1、优化之前

/**
 * @BelongsProject: demo
 * @BelongsPackage: com.wzl.Algorithm.DirectSelectionSort
 * @Author: Wuzilong
 * @Description: 选择排序
 * @CreateTime: 2023-04-28 11:25
 * @Version: 1.0
 */
public class DirectSelectionSort {
    public static void main(String[] args) {
        int[] numArray={2,8,1,4,9,5,7};
        //交换需要的中间量
        int temp;
        for (int i=0; i<numArray.length;i++){
            //定义最小值的变量
            int min=i;
            for (int j=i+1;j<numArray.length;j++){
                if (numArray[min]>numArray[j]){
                    //更新最小值的下标
                    min=j;
                }
            }
            temp=numArray[i];
            numArray[i]=numArray[min];
            numArray[min]=temp;
            System.out.println("第"+(i+1)+"轮插入"+Arrays.toString(numArray));
        }
    }
}

运行结果

39428e2adfec482784c1fa320183a83d.png

2、优化之后

/**
 * @BelongsProject: demo
 * @BelongsPackage: com.wzl.Algorithm.DirectSelectionSort
 * @Author: Wuzilong
 * @Description: 选择排序优化版
 * @CreateTime: 2023-04-28 11:25
 * @Version: 1.0
 */
public class DirectSelectionSort {
    public static void main(String[] args) {
        int[] numArray={2,8,1,4,9,5,7};
        //交换需要的中间量
        int temp;
        for (int i=0; i<numArray.length-1;i++){
            if( i == numArray.length-2){ //如果i=数组的最后两个值
                break;  //退出循环
            }
            //定义最小值的变量
            int min=i;
            for (int j=i+1;j<numArray.length;j++){
                if (numArray[min]>numArray[j]){
                    //更新最小值的下标
                    min=j;
                }
            }
            temp=numArray[i];
            numArray[i]=numArray[min];
            numArray[min]=temp;
            System.out.println("第"+(i+1)+"轮插入"+Arrays.toString(numArray));
        }
    }
}

运行结果

5967c631fedb427dbe4aa2ff3c81aac4.png

五、算法描述

1、问题描述

 给定一个 n 个元素的数组,数组下标从 0 开始,采用 选择排序 将数组按照 升序排列。

2、算法过程

整个算法过程分为以下几步:

 1)循环迭代变量 i = 0 → n − 1 i = 0 \to n-1i=0→n−1;

 2)每次迭代,令 m i n = i min = imin=i,j = i + 1 j = i+1j=i+1;

 3)循环执行比较 a [ j ]和 a [ m i n ] ,如果产生 a [ j ] < a [ m i n ] 则执行 m i n = j 执行 j = j + 1,继续执行这一步,直到 j = = n;

 4)交换 a [ i ] a[i]a[i] 和 a [ m i n ] a[min]a[min],回到 1)。

六、算法分析

1、时间复杂度

 最好的情况全部元素已经有序,则 交换次数为0;最差的情况,全部元素逆序,就要交换 n-1 次;所以最优的时间复杂度和最差的时间复杂度和平均时间复杂度 都为 :O(n^2)

2、空间复杂度

 最优的情况下(已经有顺序)复杂度为:O(0) ;

 最差的情况下(全部元素都要重新排序)复杂度为:O(n );

 那么选择排序算法平均的时间复杂度为:O(1)

3、算法稳定性

 选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。所以选择排序是不稳定的。


相关文章
|
存储 缓存 算法
【计算机网络】数据链路层
【计算机网络】数据链路层
680 0
【计算机网络】数据链路层
|
11月前
|
存储 Web App开发 安全
如何防范 CSRF 攻击
CSRF(跨站请求伪造)攻击是一种常见的安全威胁。防范措施包括:使用Anti-CSRF Token、检查HTTP Referer、限制Cookie作用域、采用双重提交Cookie机制等,确保请求的合法性与安全性。
|
11月前
|
消息中间件 存储 Kafka
RocketMQ 工作原理图解,看这篇就够了!
本文详细解析了 RocketMQ 的核心架构、消息领域模型、关键特性和应用场景,帮助深入理解消息中间件的工作原理。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
RocketMQ 工作原理图解,看这篇就够了!
|
监控 Java 关系型数据库
JVM工作原理与实战(十三):打破双亲委派机制-线程上下文类加载器
JVM作为Java程序的运行环境,其负责解释和执行字节码,管理内存,确保安全,支持多线程和提供性能监控工具,以及确保程序的跨平台运行。本文主要介绍了打破双亲委派机制的方法、线程上下文类加载器等内容。
1208 2
|
11月前
|
JSON 搜索推荐 C++
vscode如何更改背景颜色主题,黑色或白色?
【11月更文挑战第16天】在 VS Code 中更改背景颜色主题,可通过三种方式实现:1) 使用快捷键 Ctrl+K 和 Ctrl+T(Mac 上为 Command+K 和 Command+T)选择主题;2) 通过菜单中的“管理”-&gt;“颜色主题”选项选择;3) 修改 settings.json 文件中的 &quot;workbench.colorTheme&quot; 属性。此外,用户还可从扩展市场安装更多主题以满足个性化需求。
22754 6
|
12月前
|
SQL 存储 关系型数据库
SQL判断CHAR类型字段不为空的方法与技巧
在SQL查询中,判断一个CHAR类型字段是否不为空是一个常见的需求
|
12月前
|
搜索推荐
冒泡排序(Bubble Sort)以及选择排序(Selection Sort)和快速排序(Quick Sort)详细解析
冒泡排序(Bubble Sort)以及选择排序(Selection Sort)和快速排序(Quick Sort)详细解析
182 1
|
12月前
|
存储 C++ 容器
C++入门8——vector的使用
C++入门8——vector的使用
855 0
|
机器学习/深度学习 开发工具 git
matplotlib各种案例总结(python经典编程案例)
该文章汇总了使用matplotlib绘制不同类型图表的方法和案例,包括条形图、折线图等,并展示了如何调整颜色和线条样式等属性。
246 0
3个常用的Python性能分析工具及其使用方法
以下是几个常用的性能分析工具及其使用方法和常用命令: