排序算法二:选择排序

马谦马谦马谦 2018年3月3日20:57:55 发表评论
文章最后编辑于:2020-2-7 16:38:45

一、原理

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

选择排序无论在最坏或是最好的情况,时间复杂度都是O(\(n^2\))

排序逻辑:

图解

以序列[3, 1, 5, 4, 7]为例,执行第一趟排序时,找到的最小元素是1,把它放到最前面和3对换:

排序算法二:选择排序

第二趟排序,未排序数组为[3, 5, 4, 7],此时数组内最小的元素是3,刚好就是当前数组最开头的位置,因此无需替换,继续下一趟排序。

排序算法二:选择排序

第三趟排序,未排序数组为[5, 4, 7],此时数组内最小的元素是4,放到最前面和5对换:

排序算法二:选择排序

执行完第三趟排序后,数组就已经有序了。但是对计算机而言却并不知情,它还会继续判断后面的[5, 7],但是刚好每次排序的时候,他们就处于应该在的位置。

二、代码实现

2.1 C++实现

2.2 python实现

2.3 c语言实现

本文共执行62次查询,耗时0.368秒!
历史上的今天
三月
3
马谦马谦马谦

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: