选择排序

面试官: 聊聊选择排序

选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度

排序思想

一天,小一尘和师傅下山去了,在集市中路经一个水果摊,只见水果摊上摆着色泽基本相同但大小不一的苹果

师傅,我想吃苹果

一尘

慧能

那你给咱买一些去吧

师傅答应后,小一尘就去水果摊前买苹果了

他拿了一个袋子,从众多苹果中挑了一个最大的装入袋子,然后又从剩下的苹果中挑出了最大的放入口袋,就这样挑了几个苹果然后结账

小一尘买完苹果后,走到师傅面前

慧能

我看你刚才选苹果的时候每次都从苹果堆里选出最大的一个放入口袋

恩恩,是呀

一尘

慧能

这其实就是选择排序的思想,选择排序就是不断地从未排序的元素中选择最大(或最小)的元素放入已排好序的元素集合中,直到未排序中仅剩一个元素为止

买个苹果也不忘给我传授知识,一尘心里甚是感激

排序代码

哦,原来选择排序挺简单

一尘

慧能

恩恩,那你写一下代码吧

一尘眉头一紧

心中想到:

初始时肯定给我一个无序数组

我先从这些元素中选出一个最小的(或最大的),和第一个元素进行交换,这样第一个元素就是最小的,第一个元素位置就变成有序区间了

同理,在剩下的无序区间选择最小的元素,将最小元素与无序区间的第一个元素进行交换,交换后原来无序区间的第一个元素就变为有序区间的最后一个元素了,有序区间递增一

以此类推,全部元素就可以通过这样不断地选择以及交换排完序

那如何选出最小的一个元素呢?

很容易想到:先随便选一个元素假设它为最小的元素(默认为无序区间第一个元素),然后让这个元素与无序区间中的每一个元素进行比较,如果遇到比自己小的元素,那更新最小值下标,直到把无序区间遍历完,那最后的最小值就是这个无序区间的最小值

想到这里,一尘已经胸有成竹了,随手写出了如下代码

时间复杂度

慧能

恩恩,不错,那你分析一下代码的时间复杂度吧

这段代码的时间复杂度不难,和冒泡排序,插入排序的非常像,一尘心里想到

好的

一尘

设有 n 个元素(n = arr.length)

代码执行的时间都花费在内层for循环中的比较语句和外层for循环里的交换语句了

外层for循环执行 n-1 次,那么交换(swap)就执行 n-1 次,时间复杂度为O(n)

内层for循环中的比较语句执行多少次呢?

i = 0 时,比较 n - 1 次

i = 1 时,比较 n - 2 次

...

i = n-2 时,比较 1 次

则一共比较了

复杂度为O(n^2)

一尘

关于时间复杂度可看:

算法分析神器—时间复杂度

稳定性

慧能

恩恩,不错,稳定性也顺便分析一下

由于选择元素之后会发生交换操作,所以有可能把前面的元素交换到后面,所以不是稳定的排序

一尘

慧能

恩恩,分析的很对,来吃个苹果

一尘和师傅提着苹果走向了回家的路

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2018-03-07

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

我们应该如何对事物进行比较和排序?这问题听上去有点莫名其妙,但我希望你认真考虑一下。比方说,我们有一组苹果:

5810
来自专栏木制robot技术杂谈

谈一谈Python中str()和repr()的区别

前言 在学习BeautifulSoup文档的时候发现了一个以前不常见的Python内建函数repr(),带着好奇对这个内建函数进行了一番搜索和学习。 总结 s...

37640
来自专栏Android机动车

设计模式——抽象工厂模式

● 为创建一组相关或依赖的对象提供一个接口,而无需指定他们的具体类型。是工厂方法模式的升级版。

8110
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:运算符

17660
来自专栏玄魂工作室

如何学python 第十七课 类-面向对象的概念

欢迎回来。今天要说的东西将会改变我们写程序的方式。今天我们介绍‘类’(class)。 概述 什么叫‘类’?类,类型。变量类型。从日常生活的感觉来说,‘类’其实...

27740
来自专栏编程

三撩Python

我不求深刻,只求简单。 --三毛 1、起手 我呢,一个咖啡师,咖啡使我忙碌与充实。 每天端起咖啡,香气弥漫,轻轻一口,就在那一刹那,没有时间,没有空间,没有纷纷...

18890
来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

还有一个不错的视频(https://marcus-biel.com/java-comparable-interface-video-tutorial/)。

11650
来自专栏Python爬虫与数据挖掘

Python大神用一道题带你搞定Python函数中形参和实参问题

昨天在Python学习群里有位路人甲问了个Python函数中关于形参和实参一个很基础的问题,虽然很基础,但是对于很多小白来说不一定简单,反而会被...

14610
来自专栏CodingToDie

Python学习(八):类和对象 以另一种思维看待世界

第8 章 类和对象 以另一种思维看待世界 对世界万物的状态与行为进行归纳与分类,以此分析个体与个体间的相互作用与影响方法。 Table of Contents ...

38170
来自专栏玄魂工作室

Python黑帽编程2.9 面向对象编程

Python黑帽编程2.9 面向对象编程 我个人认为,计算机语言的发展,有两个方向,一个是从低到高的发展过程,在这个过程中,语言的思考和解决问题的方式是面向硬件...

30470

扫码关注云+社区

领取腾讯云代金券