计算机编程语⾔排序，计算机⼊门必备算法——选择排序法引⾔
昨天我们学习了⼆分查法，但是⼆分查法使⽤的前提必须是有序的数组或者列表，(当然很多的算法都是仅在数据有序的前提下才能使⽤)
但是在实际⼯作中，我们接收到的数组不可能都是有序的，那怎么办呢？于是乎我们就应该先对接收到的数组或者列表进⾏排序。今天先来介绍第⼀种排序⽅法————选择排序。在要理解选择排序的内容，我们还必须具备关于数组、链表和⼤O表⽰法(专业术语：时间复杂度)的知识储备。
2、知识准备
我们都知道不管是数组还是链表，它们都是操作系统为我们开辟的⼀系列空间，但两者不同的是数组是⼀段连续的内存空间，⽽链表不连续。这两种内存空间都各有利弊，我们要视实际情况选择数组还是链表解决问题。⾸先，我们应对内存有⼀个直观的了解。
2.1.1 内存
我们都去超市买过东西，但是进⼊超市并不能携带我们的包或者其他物品，超市便提供了储物柜让我们存放物品，这个储物柜⼜分了很多⼩的储物箱。每个储物箱都只能放⼀件合适的东西，但你有两件东西，那怎么办呢？那我们就得向储物柜请求两个储物箱的位置。等到储物柜给你开好两个箱门时，你便可将东西
存放起来。
储物柜
这⼤致上就是计算机内存的⼯作原理，当我们需要将数据存储到内存时，我们需要向操作系统请求存储空间，计算机会在内存空间允许的情况下，便会分配给你⼀个内存地址。同理当我们需要存储多项数据
时，编程语⾔向我们提供了两种基本⽅式————数组和链表，正如上⾯所说，两者有不同之处且各有利弊。下⾯介绍数组和链表的相关知识。
2.1.2 数组
上⾯介绍到，当我们需要存储多项数据，便需要向操作系统请求⼀段内存空间。编程语⾔向我们提供了数组和链表两种⽅式，那么我们应该选择数组还是链表呢？上⾯介绍到数组是⼀段连续的内存空间，链表是不需要连续的，只需要每块内存中保留下⼀块内存的地址，于是乎这些地址块串联在⼀起，便形成了⼀段内存空间。但我们这节介绍数组，我们就举⼀个例⼦去讲解数组的存储⽅式。
数组
⽐如说你和室友去⽼⾷堂吃饭，现在只值军训期间，吃饭的⼈会⾮常多，你们转完了整个⼀层⼆层之后发现有⼀个桌⼦只坐了对⾯两⼈，于是乎你去问⼈家你们旁边还有⼈吗？⼈家要说没有你们就赶紧放下
具有你们标志的东西就跑去买饭。买好之后正吃着饭⼜来了⼀个刚上完课的室友，于是乎你们得三⼈坐在⼀起，本来等旁边两⼈吃完了室友就可以坐下了，但是旁边的⼀直就吃个没停，那么我们就要重新寻⼀个可以容纳三⼈的桌⼦，等到之后你们就可以愉快的吃饭了！但如果再来⼀个和对象刚刚分开的室友，那你们就得炮轰他之后再次转移，真是吃饭都吃不安宁。
同样的，在数组中添加新的元素也很⿇烦，数组必须保证是⼀段连续的内存空间，如果这个空间不够⽤，那么就得需要重新申请，这样就很⿇烦。有没有解决办法呢？是有的！如果你有能⼒承包整个餐厅的话，那么整个餐厅的桌⼦都是你的，你可以带上你的室友，你的对象，你对象的对象，你对象的对象……按顺序就座。当然坐不满的话显然浪费了公共资源，如果不够坐的话你还得去承包新⾷堂⽤视频连线吃饭。如果你不想这样，那么就得请链表出⼭了！
2.1.3 链表
链表这个⽼⼤哥的话，它允许你把数组存储到内存的任何地⽅(可不连续)。但是如何到下⼀个数据呢，那么就需要上⼀个数据携带下⼀个内存的地址，从⽽使得随机的内存串联在了⼀起。所以在链表上加⼊元素很容易，只需将其放⼊内存中，然后把地址存储到上⼀个元素中去。使⽤链表时，不需要去移动数据。
链表
举个简单例⼦在接⼒赛跑中，400⽶并没有1000⼈(假设1000⼈的队伍有400⽶)去排队，然后到达终点。⽽现实并不是这样，如果是双⼈接⼒的话，那么安排两⼈(⼀个在起点，⼀个在跑道中央)，那么就需要告诉起点的⼈，你的接⼒的⼈在哪⾥，才能将接⼒棒传给下⼀个⼈，但如果是四⼈接⼒，那么我们就得分别告诉每⼀个接⼒的⼈，它的下⼀个位置应在哪⾥。这个例⼦应该能够理解链表的存储⽅式，只要有⾜够的内存空间，就能为链表分配内存。
2.1.4 优缺点
数组的优点很明显就是读取数据，在于它天然的连续性，如果我们已知了数组存储的⾸地址，那么我们任何⼀个数据都是很容易(数组是定长的)，⽤⼤O表⽰法为O(1)。但我们需要注意的是数组中元素的索引是从0开始的，⽽不是1。从0开始让基于数组的代码编写起来很容易，因此程序员始终坚持这么做。
链表在读取数据时就显得有点吃不消，因为⾃⼰的地址不连续，那么就需要从第⼀个元素开始第⼆个
元素，然后根据第⼆个元素存的地址到下⼀个元素，以此类推，到我们需要到的元素，如果我们所要寻的元素是第⼀个时，真⾹！⽤⼤O表⽰法为O(n)。
但数组的缺点就很明显，就是上⾯所说的不好插⼊新元素，要么得等，要么就得重新申请。很⿇烦，⼤O表⽰法为O(n)。链表这块就⾮常的容易，只需要保存到前⼀个元素中，就把新元素插⼊到了链表中。⼤O表⽰法为O(1)。
删除元素时，应选择哪个⽅式更好呢？这个问题留给你们思考。(留⾔哦~)
2.2 选择排序
对数组和链表有了整体的了解之后，就可以了解选择排序算法了。
2.2.1 选择排序的原理
还是⽤⽣活中的例⼦来解释选择排序的原理。我们都是⽼⽹抑云了，当我们听每⾸歌时，⽹易云后台都会收集每⾸歌的播放次数(当然我没有在⽹易云⼯作，纯属猜测，只是想举个栗⼦)。于是乎程序员需要对每⼀个⽤户喜爱播放的歌曲次数由多到少的进⾏排列，很容易想到的就是我再弄⼀个列表过来，每⼀次遍历这个次数列表，出第⼀多的，放到我的新列表中去，然后在遍历次数列表，出第⼆多，然后保存在新列表，循环往复，最后，我们得到了⼀个有序列表(⽹易云员⼯应该不会这么排序，应该够程序
员辞职好⼏回了)。
播放列表
数组和链表
2.2.2 代码实现
废话不多说，直接上代码。(代码都是编译通过且得出正确结果的，如果什么更好的写法的话，可以给我留⾔哦~)选择排序顺序结构
2.2.3 运⾏时间
我们来分析⼀下这个排序算法的运⾏时间，我们⾸先需要对列表进⾏⼀次简单查(上⼀节的傻)，它的运⾏时间为O(n)。你要完列表
的所有⼤，那么你需要执⾏n次。需要的总时间就很容易得到为O(n x n) = O(n)。这样的算法有点简单粗暴，当然这能说明问题。具体怎么得出我也
不会，留给你们吧~你们⼀定⽐我聪明！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。