简单选择排序算法

来自计算思维百科
跳转至: 导航搜索
简单选择排序.jpg

在日常生活和工作中,我们常常要进行排序。简单选择排序(Selection Sort)顾名思义是一种排序算法,属于蛮力法,但是它以一种更加清晰的方式实现了蛮力法。

基本概念

选择排序流程:

假设一个序列具有n个元素,第一趟扫描序列中所有元素,找出最小(最大)元素与第一个元素进行交换,第二趟从序列的第二个元素扫描,找出最小(最大)元素与第二个元素进行交换,依此进行,直到序列前n-1个位置都放好,这时原始序列已经排好序。容易看出,第i(i=1,2…,n)趟扫描交换完毕就相当于实现了最终序列的前i个元素。


选择排序运用举例:

利用选择排序对初始序列21  49  16  25  10进行升序排序(从小到大排序)。

第一趟扫描整个序列,找出最小元素为10,将其与第一个元素21交换得到序列(注:红色表示每趟扫描后找到的最小元素,下划线表示每趟交换元素):

10  49  16  25  21

第二趟从第二个元素49开始往后扫描,找到最小元素16,将其与第二个元素49交换,得到序列:

10  16  49  25  21

第三趟从第三个元素49开始往后扫描,找到最小元素21,将其与第三个元素49交换,得到序列:

10  16  21  25  49

第四趟从第四个元素25开始往后扫描,找到最小元素25,将其与第四个元素25交换,得到序列:

10  16  21  25  49

至此,具有五个元素的无序序列经过四趟扫描已经按照从小到大的顺序排序完毕。

应用范围

作为最基本常见的算法,不论是在各个学术领域还是实际生活中,排序算法的应用都极其广泛。例如生活中对摆放物品的排序,excel中对记录的排序,数据库中对数据的排序,甚至很多经典算法都是基于排序算法实现的。但是排序算法各有千秋,不同的场合需要考虑各排序算法不同的因素。

应用1-成绩排序

根据期末考试的成绩单信息,把所有的学生按总分从高到低的顺序排序。相信这个问题对于学生来说再熟悉不过了,这就是最典型的一个排序问题,对于数据量小的序列,采用选择排序即可解决。

可以运用的计算思维

选择排序算法体现的是蛮力法的思想。蛮力法也成穷举法,是一种简单、直接地解决问题的方法,是指在问题解空间的范围内逐一测试,找出问题的解。蛮力法是一种比较耗时的算法,但是计算机的出现使得蛮力法有了用武之地。如果待解决的问题实例不多,而蛮力法可用一种可接受的速度对问题求解,那么花时间去设计一个更高效的算法是得不偿失的。选择排序算法体现了计算思维的机械化特点。