1. 陆角网Home
  2. 百问百答

大话数据结构 怎么样，计算机中的选择排序

• 百问百答

1选择排序的逻辑

我们刚刚看完了冒泡排序，今天再学习一下选择排序，依然是用之前的题目, 这样排列的6个数字。

白话计算机排序算法之选择排序

通过选择排序，把这6个数字按照从左到右从小到大的顺序排列好，也就是目标是这样的：

白话计算机排序算法之选择排序

选择排序的逻辑就是每次假定一个最小的数字，用它和其他数字比较，如果其他数字小，就把最小的数字设定为其他数字，最后把经过比较后最小的数字移到左边。

下图是进行了一轮全部元素比较之后，

白话计算机排序算法之选择排序

这个数字被选择出来的过程。

白话计算机排序算法之选择排序

我们详细分解一下这个过程：

首先把最小的数设置为左边第一个数，也就是8（当前认定为最小的数字上方有一个红色三角形）, 用最小的数和它右边所有的数字进行比较。

第一步，8和5比较，8比5大，所以把最小的数设置为5。

第二步，用最小的数5和它右边数字3比较，5比3大，所以把最小的数设置为3。

第三，四，五步，都是用3和后面数字比较，因为后面数都比它大，所以经过这一轮比较后3是最小数字。

第六步，把3和第一位数字8进行交换，3被”选择“了出来。

白话计算机排序算法之选择排序

第一轮过后的结果是这样的：

白话计算机排序算法之选择排序

第二轮，先用左边第二个数字5作为最小的数字与后面的所有数字进行比较，比较过程和第一轮类似，经过这一轮

白话计算机排序算法之选择排序

被选择了出来。

白话计算机排序算法之选择排序

第三轮，先用第三个数字8作为最小的数字，经过这一轮

白话计算机排序算法之选择排序

被选择了出来。

白话计算机排序算法之选择排序

第四轮，先用第四个数字6作为最小的数字，经过这一轮

白话计算机排序算法之选择排序

被选择了出来, 其实它本来就在这。

白话计算机排序算法之选择排序

第五轮，先用第五个数字8作为最小的数字，经过这一轮

白话计算机排序算法之选择排序

被选择了出来。

白话计算机排序算法之选择排序

第六轮，只剩最大的数字8在最右侧，可以省略。

下面的选择排序视频同样供大家参考。

2 编程实现

下面又到了上代码时间了

白话计算机排序算法之选择排序

交换元素这个子代码已经在之前冒泡排序中讲过，这次就不再讲了，大家可以点蓝字”冒泡排序“回看。

下面再拆解下主代码是如何做出来的，我们可以按照之前的步骤进行拆解：

1. 如果只做一轮的选择排序，代码是这样的，执行这段代码

白话计算机排序算法之选择排序

这个最小数字交换到最左边。

白话计算机排序算法之选择排序

2. 然后再给它套上一层循环，让它按照列表数量循环，把所有数字都按照顺序交换过去。

白话计算机排序算法之选择排序

注意：

在这个过程中内部循环每次j要从i+1开始，避免把之前已经归位的数字重新”选择“一遍。交换元素时是用最小项和当前的i进行交换内部循环是j>列表项目数，而外部循环是i=列表项目数，这样在每次设定最小项的时候能够把最后一项考虑进去，而最后一轮可以忽略掉对最后一项的处理。

如果这个列表基本有序，也就是每次选出来的最小项都恰好在i的位置上，为了减少交换的次数，可以加上这样一个比较逻辑，可以减少与列表的数量成正比次操作；但是如果列表无序的情况，这种则会增加与列表的数量成正比次操作。所以大家视情况，一般可以不加。

白话计算机排序算法之选择排序

3 对比冒泡排序

那么到底冒泡排序好，还是选择排序好呢？针对这个序列

白话计算机排序算法之选择排序

每种排序都进行了5轮（第6轮省略），每一轮都进行了n-i次比较，n是列表的数量，i是第几轮。两种排序总的比较次数都是n(n-1)/2。

而交换次数上，每一轮，选择排序最多交换1次，最少不需要交换；冒泡排序最多需要交换n-i次，所以如果是基本无序的数据，因为交换次数少，选择排序要优于冒泡排序。

而在有序的数据上冒泡排序则要优秀得多，冒泡排序与n成正比，而选择排序与n的平方成正比。

所以不能一概而论，大家需要视情况选择不同的算法。

参考书籍：

《Scratch趣味编程进阶》 清华大学出版社

《大话数据结构》清华大学出版社

《信息学奥赛一本通（C++版）》科学技术文献出版社

Previous 2023-08-09 02:27:27
Next 2023-08-09 02:27:39

相关推荐

本站部分内容由互联网用户自发贡献，该文观点仅代表作者本人，本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如发现本站有涉嫌抄袭侵权/违法违规等内容，请联系我们举报！一经查实，本站将立刻删除。