排序问题与算法的多样性

《排序问题与算法的多样性》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、排序问题与算法的多样性在日常生活中，人们经常要查询信息。例如1）在词典中查找某个词的读音和含义；2）在图书馆里根据作者或者书名查找书目；3）在电话簿中查找某单位或某人的电话号码等。为了便于查询信息，我们常常根据某种要求把被查询的对象用数字或符号表示出来，并把数字按大小排列是信息处理中的一项基本工作，这个工作通常称为排序。排序的算法很多，本节课给大家介绍一些常用的排序算法。先给出一个概念：有序列有序列：按一定的顺序排列的数据叫作有序列。把一个新数据插入到有序列中，则形成一个新的有序列。规定：只有一个数据的序列也是有序列。本节课，我们重点研究两种插入排序的算法：1）有序列直接插入排序的算法；2）

2、有序列折半插入排序的算法。1、有序列直接插入排序的算法：例1：设有一个有序列为{13、27、51、57、82}，现在要将数据52插入到数据列中，请设计一个算法确定数据52在序列中的位置，并用自然语言表述出来。分析：我们可以将52从右向左逐个与有序列中的数据进行比较，以确定52在序列中的位置，然后将其插入并构成一个新有序列。解：设计算法如下：比较52与82的大小，因为52<82比较52与57的大小，因为52<57比较52与51的大小，因为52>51将52插入51与57中间得到一个新的有序列13、27、51、52、57、82评注：我们也可以将52从左向右逐个与有序列中的数据进行比较，来确定52在

3、序列中的位置。大家试用自然语言表述这个算法。如果新数据小于原有序列中的所有数据，则将新数据插入到原有序列的最左边。上面这种插入排序的算法就叫作有序列直接插入排序算法。思考：通过上例请同学们总结一下有序列直接插入排序算法的步骤。2、有序列折半插入排序算法：再研究上例先将有序列“中间位置”的数据与52进行比较，以确定52应排在这个数据的左边还是右边。再将这一边的数据列的“中间位置”的数据与52进行比较，以确定52应排在这个数据的左边还是右边。如此往复，直到确定出52在原有序列中的确切位置。解：设计算法如下：比较52与51，因为52>51比较52与57，因为52<57所以将52插入到51与57中间

4、得到新的有序列为：13、27、51、52、57、82思考：通过上例请同学们总结一下有序列折半插入排序算法的步骤。3、数据排序：我们已经会设计在有序列中插入新数据的排序算法，那么，对于一组无序的数据列，如何完成排序工作呢？例2、将无序列{16、21、9、16、11}按从小到大的顺序排列。解：设计算法如下：1、将21插入到有序列{16}中，得到有序列{16、21}；2、将9插入到有序列{16、21}中，得到有序列{9、16、21}；3、将16插入{9、16、21}中，得到有序列{9、16、16、21}；4、将11插入{9、16、16、21}中，得到有序列{9、11、16、16、21}。通过分析上

5、例，我们发现：有序列插入排序算法是“数据排序”的基础。1、作业：2、预习：