选择法排序
选择法排序:
1、在实际工作中,我们接收到的数组不可能都是有序的,那怎么办呢?于是乎我们就应该先对接收到的数组或者列表进行排序。今天先来介绍第一种排序方法————选择排序。
2、知识准备
我们都知道不管是数组还是链表,它们都是操作系统为我们开辟的一系列空间,但两者不同的是数组是一段连续的内存空间,而链表不连续。这两种内存空间都各有利弊,我们要视实际情况选择数组还是链表解决问题。首先,我们应对内存有一个直观的了解。
2.1.1 内存
我们都去超市买过东西,但是进入超市并不能携带我们的包或者其他物品,超市便提供了储物柜让我们存放物品,这个储物柜又分了很多小的储物箱。
每个储物箱都只能放一件合适的东西,但你有两件东西,那怎么办呢?那我们就得向储物柜请求两个储物箱的位置。等到储物柜给你开好两个箱门时,你便可将东西存放起来。这大致上就是计算机内存的工作原理。
当我们需要将数据存储到内存时,我们需要向操作系统请求存储空间,计算机会在内存空间允许的情况下,便会分配给你一个内存地址。同理当我们需要存储多项数据时,编程语言向我们提供了两种基本方式————数组和链表,正如上面所说,两者有不同之处且各有利弊。下面介绍数组和链表的相关知识。
2.1.2 数组
上面介绍到,当我们需要存储多项数据,便需要向操作系统请求一段内存空间。编程语言向我们提供了数组和链表两种方式,那么我们应该选择数组还是链表呢?上面介绍到数组是一段连续的内存空间,链表是不需要连续的,只需要每块内存中保留下一块内存的地址,于是乎这些地址块串联在一起,便形成了一段内存空间。
2.1.3 链表
链表这个老大哥的话,它允许你把数组存储到内存的任何地方(可不连续)。但是如何找到下一个数据呢,那么就需要上一个数据携带下一个内存的地址,从而使得随机的内存串联在了一起。所以在链表上加入元素很容易,只需将其放入内存中,然后把地址存储到上一个元素中去。使用链表时,不需要去移动数据。
2.1.4 优缺点
数组的优点很明显就是读取数据,在于它天然的连续性,如果我们已知了数组存储的首地址,那么我们找任何一个数据都是很容易(数组是定长的),用大O表示法为O(1)。但我们需要注意的是数组中元素的索引是从0开始的,而不是1。从0开始让基于数组的代码编写起来很容易,因此程序员始终坚持这么做。
选择排序的原理:
第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
还是用生活中的例子来解释选择排序的原理。我们都是老网抑云了,当我们听每首歌时,网易云后台都会收集每首歌的播放次数。
于是乎程序员需要对每一个用户喜爱播放的歌曲次数由多到少的进行排列,很容易想到的就是我再弄一个列表过来,每一次遍历这个次数列表,找出第一多的,放到我的新列表中去,然后在遍历次数列表,找出第二多,然后保存在新列表,循环往复。