选择排序算法,只需这篇文章就够了

一、说在前面

一直想写一些简单易懂的文章,因为平时看的很多的书籍或者文章都是看着很难受的感觉,当然,这并不是说书籍写的不好,只是说对于一些没有太多基础或者基础不是很好的来说,相对来说还是比较难以理解的。

这个系列主要是写一些简单易懂的数据结构与算法的文章,同时也是帮助自己再理解理解这方面的知识。

作为数据结构与算法的开篇,还是以排序算法作为第一部分的内容,需要注意的是,这一系列的文章并不是涉及到很多理论性质的知识,因为前面说了,主要还是希望文章是简单易懂的,希望能达到读故事的感觉。如果需要去学习理论性质的知识,可以去查看相关的数据结构与算法的书籍。

二、选择排序算法

今天早上,老师又叫我们去操场上做早操,做早操之前呢,今天也需要排队,到操场的同学有5个人,今天的排序方法还是按照身高由低到高排列

图片.png

但是,今天老师说换一种方法排队,我来给你们排队,昨天你们排队太慢了。

于是,老师说:第一个同学站在原地不要动。

图片.png

然后,我从后面4个同学当中挑一个最矮的同学,这个同学站在第一个同学后面,你们两个站在原地不要动。

图片.png

图片.png

之后,老师再从后面3个同学里面挑一个最矮的同学,然后让他站在前面两个排好的同学后面,这样这三个同学就排好了,你们站着不要动。

图片.png

图片.png

老师又从最后两个同学中挑一个最矮的同学,让他站在前面三个已经排好的队伍后面,这样,这四个同学就排好队列,这四个同学站着不要动。

图片.png

四个同学排好了,只有最后一个同学了,然后,这个同学自己站到前面四个已经排好队的队伍的最后,这样5个同学的位置就排好了。

图片.png

图片.png

老师看到排好了队,非常开心,对同学们说:“我排队是不是比你们自己排队快啊!”

然后,这位程序员老师说,哪位同学懂了刚刚我给你们排队的思想,能不能叙述一下,这时候,小明说:我会!,于是,小明说了一下思想

初始时在队伍中找到最小(大)元素,放到队伍的起始位置作为已排好队伍;然后,再从剩余未排序队伍中继续寻找最小(大)元素,放到已排序队伍的末尾。以此类推,直到所有元素均排序完毕。

老师说,队列都给你们排好了,小明同学也又很好的阐述了思想,你们把代码实现以下吧(哈哈哈!)。

于是,小海同学就去按照老师的排队方法,实现了选择排序算法

public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                //在待排序区选择最小的元素
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }

            swap(arr, i, minIndex);// 放到已排序序列的末尾,该操作很有可能把稳定性打乱,所以选择排序是不稳定的排序算法
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
性能分析

最差时间复杂度:O(n^2) 最优时间复杂度:O(n^2) 平均时间复杂度: O(n^2) 所需辅助空间:O(1) 稳定性:不稳定

原文发布于微信公众号 - 好好学java(SIHAIloveJAVA)

原文发表时间:2018-11-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

英语不好,能看懂编程吗?

学会编程不需要多高深的英语水平,想要学会编程,简单的英语水平足够了,现在的程序开发环境又很友好,基本上打开之后不需要怎么配置,直接写代码就行,程序语言无外乎顺序...

2140
来自专栏非著名程序员

如何评价一段代码

经常有人微信问我,什么样的代码才算是好代码。这个问题其实见仁见智,业内也没有统一的标准可以使用。我仔细梳理了一下自己评价代码的方法,总结了五个评价指标。 1、规...

1799
来自专栏日常学python

一行Python代码能干嘛?

python有很多优雅有趣的代码写法,同时还很简短,以至于当我刚开始接触这个编程语言的时候,就爱不释手。而前几天的编程语言榜单中python也超越了java成为...

1160
来自专栏Pythonista

day24,python习题

有两个列表,分别存放来老男孩报名学习linux和python课程的学生名字 linux=['钢弹','小壁虎','小虎比','alex','wupeiqi'...

1552
来自专栏逸鹏说道

重温数据结构系列随笔:数据结构的基本概念

现在项目已经踏上正轨,有不少时间可以用来学习,昨晚发现柜子里那本大学时候啃过无数遍的(数据结构 C语言版),那真的无限感叹啊,初恋女友啊,大学回忆啊都涌上心头。...

2884
来自专栏顶级程序员

如何掌握所有的程序语言

对的,我这里要讲的不是如何掌握一种程序语言,而是所有的…… 很多编程初学者至今还在给我写信请教,问我该学习什么程序语言,怎么学习。由于我知道如何掌握“所有”...

3639
来自专栏老九学堂

技术大咖分享:如何评价一段代码?

经常有人微信问老九君,什么样的代码才算是好代码。这个问题其实见仁见智,业内也没有统一的标准可以使用。我仔细梳理了一下自己评价代码的方法,总结了五个评价指标。 规...

3666
来自专栏诸葛青云的专栏

利用c语言制作简易计算器

学了c语言之后,总想着能用c语言能制作一些简单的小工具来。而利用c语言来制作一款简易的计算器是一个不错的选择,用这款计算器可以计算的加、减、乘、除。

6511
来自专栏佳爷的后花媛

Java编程思想之每天两小时(一)

之前也学过Java,但是因为很少用,所以一直没有当回事,现在想想,那时真是太年轻啊。后来朋友推荐这本Java编程思想给我,刚拿到这本书,被这厚厚的一本惊呆了,里...

1102
来自专栏Debian社区

王垠:如何掌握所有的程序语言

很多编程初学者至今还在给我写信请教,问我该学习什么程序语言,怎么学习。由于我知道如何掌握“所有”的程序语言,总是感觉这种该学“一种”什么语言的问题比较低级,所以...

1423

扫码关注云+社区

领取腾讯云代金券