专栏首页code随笔的专栏详解选择排序算法

详解选择排序算法

基本思想

选择排序的思想是: 给定一个数组arr,其长度为n; 第一次从 arr[0] 到 arr[n-1] 中选取一个最值(按照需求,可以是最大值,可以是最小值,下同)与arr[0]进行交换; 第二次从arr[1] 到 arr[n-1] 中选取一个最值与arr[1]进行交换; 以此类推,直到arr[n-2]到arr[n-1]中选出最值交换后即完成排序。(只剩下一个元素,前面的都是比它小(或者大)的)。

例子

给定数组 arr 为 [ 300, 50 , 120 , 110 ]; 则其初始状态为:

初始状态

定义两个变量minIndexmin,分别表示最小值元素的索引,和最小值元素的值。 先假定最小值元素为循环开始的第一个元素。 第一次循环将minIndexmin分别赋值为 0300。 循环变量为当前元素的下一个元素的索引。 由图来演示算法过程: 黄色表示当前循环需要遍历的元素。

第一趟排序

第一趟排序状态1

此时 50 < min当前值300,将minIndex赋值为1,将min赋值为50;

第一趟排序状态2 循环变量向后移动。

第一趟排序状态3

此时 120 > min当前值50,循环变量直接向后移动;

第一趟排序状态4

此时 110 > min当前值50,循环变量无法向后移动,当前循环结束。

minIndex不等于循环开始前的首元素的索引0,发生交换。

第一趟排序状态5

第二趟排序

第二趟排序状态1

此时 120 > min当前值100,循环变量直接向后移动;

第二趟排序状态2

此时 120 > min当前值110,循环变量向后移动则会发生越界,当前循环结束。

minIndex等于循环开始前的首元素的索引1,不发生交换。

第三趟排序

第三趟排序状态1

此时 110 < min当前值120,将minIndex赋值为3,将min赋值为110;

第三趟排序状态2

循环变量再向后移动则会发生越界,当前循环结束。

minIndex不等于循环开始前的首元素的索引2,发生交换。

第三趟排序状态3

因为前n-1个元素均排序完毕,所以原数组排序完毕。

我们由例子可知: 选择排序的趟数为数组长度-1

代码

由上面的讲解知道要写成双重循环,最终代码如下:

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int [] arr = new int[]{300,50,120,110};
        System.out.println("排序前的数组" + Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序前的数组" + Arrays.toString(arr));
    }
    public static void selectSort(int[] arr){

        int minIndex;//最小值元素索引
        int min;//最小值元素
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            //交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
}

时间复杂度

比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+…+1=

。为

稳定性

选择排序是不稳定的排序算法。 举个例子来说明: 序列 6 9 6 3 10 在第一趟排序时第一个6会和3交换位置,那么原序列中两个6的相对前后顺序就被破坏了。 所以选择排序是一个不稳定的排序算法。

欢迎关注

欢迎大家的关注

扫描下方的二维码或者微信搜一搜即可关注我的微信公众号:code随笔

微信公众号:code随笔

本文分享自微信公众号 - code随笔(yzsgxhywh),作者:灿烂星空StarrySky

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 详解快速排序算法

    本文的思路是以从小到大为例讲的。 快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个,最后一个,也可以是中间任何一个),习惯将其称为pivo...

    code随笔
  • LeetCode​20题 有效的括号(Valid Parentheses)

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    code随笔
  • 详解基数排序算法

    基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。

    code随笔
  • 快速排序

    快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

    用户2909867
  • Layui模块化,改造传统jquery扩展为layui模块

    在我使用jquery扩展,拖拽组件的时候,因为使用的布局模板有些冲突,导致无法使用扩展,所以才会解决之后写下这篇文章。

    宣言言言
  • 运维猫-面试题总结-55道

    ps -A -o stat,ppid,pid,cmd | grep -e '^[Zz]' | awk '{print $2}' | xargs kill -9

    胡齐
  • python第三课——数据类型2

    day03: 1.列表:list 特点:有序的(有索引、定义和显示顺序是一致的)、可变的(既可以改变元素内容也可以自动扩容)、可重复的、 可以存储任何的数...

    hankleo
  • 八爪鱼采集器︱加载更多、再显示20条图文教程(Xpatth、Ajax)

    由于代码布置采集器比较麻烦,又很早知道八爪鱼采集器的强大,所以把一些常规的采集内容贴成图文教程,供以后使用。

    素质
  • 【算法基础】java 排序算法

    思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大...

    用户5640963
  • Spring整合Quartz分布式调度

    为了保证应用的高可用和高并发性,一般都会部署多个节点;对于定时任务,如果每个节点都执行自己的定时任务,一方面耗费了系统资源,另一方面有些任务多次执行,可能引发应...

    吴生

扫码关注云+社区

领取腾讯云代金券