2021年福建教师招聘考试图书教材

当前位置:

教招信息知识点:选择排序法

发布时间: 2017-11-05 10:44:34

修改时间: 2017-11-05 10:44:34

阅读量: 1740

作者:

选择排序法 是对 定位比较交换法(也就是冒泡排序法) 的一种改进。选择排序的基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。以下是福建教师招聘网小编整理的教招美术知识点--选择排序法:

一、基本思想

选择排序的基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

简单选择排序的基本思想:第1趟,在待排序记录r[1]~r[n]中选出最小的记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

以下为简单选择排序的存储状态,其中大括号内为无序区,大括号外为有序序列:

初始序列:{49 27 65 97 76 12 38}

第1趟:12与49交换:12{27 65 97 76 49 38}

第2趟:27不动 :12 27{65 97 76 49 38}

第3趟:65与38交换:12 27 38{97 76 49 65}

第4趟:97与49交换:12 27 38 49{76 97 65}

第5趟:76与65交换:12 27 38 49 65{97 76}

第6趟:97与76交换:12 27 38 49 65 76 97 完成

二、算法

简单选择排序算法分析:在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,需要移动记录的次数最多为3(n-1)(此情况中待排序记录并非完全逆序,给完全逆序记录排序的移动次数应为(n/2)*3,其中n/2向下取整)。

简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为O(n2)。

最后,福建教师招聘网小编提醒大家注意:基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

 

推荐阅读:

2018年福建教师招考信息技术学科更多相关文章

2018年福建教师招考信息技术学科教材教法相关文章

文章内图.jpg

购物车

全选

0件商品

共计:0