1.2排序问题与算法的多样性.课件.ppt

1.2排序问题与算法的多样性,江西省吉安市第一中学刘冬发,前言,在日常生活中，人们经常要查询信息。例如，在词典里查找某个词的读音和含义，在图书馆里根据作者或者书名查找书目，在电话簿中查找某单位或某人的电话号码等。为了便于查询和检索，我们常常根据某种要求把被查询的对象用数字（或者符号）表示出来，并把数字按大小排列，是信息处理中一项基本的工作，通常称为排序。排序的算法很多，这里给大家介绍一些经常使用的排序方法。,问题提出,给定一组按从小到大的顺序排好的数据列，例如：,13，27，51，57，82,通常称这样按顺序排列的数据列为有序列。把一个新数据52插入到上述有序列中，形成一个新的有序列。,试给出一种算法，完成上述工作。,例7对于上述有序列13，27，51，57，82，现在要将数据52插入到数据列中。请设计算法确定数据52在序列中的位置，并用自然语言表述算法：,例题解析,解求解这个问题的基本思路是：将52从右向左逐个与有序列中的数据进行比较，确定52在序列中的位置，将其插入构成一个新的序列.这个过程可以用下图描述.,比较52与a5因为52a5=82,比较52与a4因为52a4=57,比较52与a3因为5251,因此将52插入a3和a4中间,得到一个新的有序列13，27，51，52，57，82,思考交流,在上述做法中，我们是将52从最右边的书开始一次比较，来确定52的位置的。我们也可以将52从左向右逐个与有序列中的数据进行比较，确定52在序列中的位置，将其插入构成一个新的序列。试用自然语言表述这个算法。,比较52与a1因为52a1=13,比较52与a2因为52a2=27,比较52与a3因为52a3=51,因此将52插入a3和a4中间,得到一个新的有序列13，27，51，52，57，82,比较52与a4因为52a4=57,抽象概括,对于一个有序列：a1a2a3an，欲将新数据A插入到有序列中，形成新的有序列，其做法是：将数据A与原有序列中的数据从右到左依次进行比较，直到发现某一数据ai，使得aiA，把A插入到ai的右边；如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边.,上面的排序算法通常称为有序列直接插入排序的算法.,折半插入排序方法,这种算法的基本思想是：,先将新数据与有序列中“中间位置”的数据进行比较.,若有序列有2n+1个数据则“中间位置”的数据指的是第n+1个数，,若有序列有2n个数据则“中间位置”的数据指的是第n个数。,如果新数据小于“中间位置”的数据，则新数据插入的位置应该在靠左边的一半；,如果新数据等于“中间位置”的数据，则将新数据插入到“中间位置”的数据的右边；,如果新数据大于“中间位置”的数据，则新数据插入的位置应该在靠右边这一半.,也就是说，一次比较就排除了数据列中一半的位置。反复进行这种比较直到确定新数据的位置，像这样的插入排序方法我们称之为折半插入排序方法。,抽象概括,我们以例7中的问题来说明这种插入排序方法,要将52插入有序列13，27，51，57，82，构成一个新的有序列.,首先选择有序列的“中间位置”的数据a3=51,将52与a3进行比较，显然52a3,所以52应该排在a3的右边.,再取余下数据列a4,a5的“中间位置”的数据a4=57,与52比较，52a4因此52应插到a4的左边,所以，52应插在a3和a4中间,这种排序方法的基本思想与二分法的思想是一致的，是算法中经常要用到的思想,思考交流,对于一组无序的数据列，例如49，38，65，97，76，13，27，49如何完成排序工作呢？,算法的基本思想也很简单。首先，只有一个数的序列49是有序列，,我们将38插入到有序列49中，得到有两个数据的有序列：38，49.,然后，将第三个数据65插入到上述有序列中，得到有序列：38，49，65.,按照这种方法，直到将最后一个数据49插入到有序列中.,得到13,27,38,49,49,65,76,97,这样，我们就完成了整个数据列的排序工作.,从上面的做法中我们可以看出，有序列插入排序算法是解决这个问题的关键,前面，我们介绍有序列插入