第9章 排序电子课件

第9章排序本章讲解排序。要求了解排序分类；掌握各种排序算法思想；灵活应用排序。重庆是中国三大火炉之一。热！夏天爱喝稀饭、下泡菜，比其他地方好吃因为热！喝稀饭补充身体水分，吃泡菜补充流失的盐分，因此各种粥和泡菜层出不穷吃喝得精光。谁越“光盘行动”得干净，谁越爱惜粮食！来比比，来排排序。提纲9.1排序基本概念9.2插入排序9.3交换排序9.4选择排序9.5归并排序9.6分配排序9.7排序应用9.8排序学习总结9.1排序基本概念定义排序在日常应用较广，如高考排名、高矮站队、招聘择优、轻重缓急事务处理等等。它将1个无序序列按照关键字排成有序序列。9.1排序基本概念2.分类升序——降序稳定——不稳定内部排序——外部排序9.1排序基本概念顺序表元素类型类RecType描述顺序表排序类SqListSort描述9.2插入排序插入排序的基本思想是每次将1个无序区元素插入到有序区中，直到所有元素插入完。插入排序主要有直接插入排序、折半插入排序和希尔排序。9.2.1直接插入排序举例：摸扑克牌，要求最终手上的牌有序。初始：无序区是桌上1摞要摸的扑克牌，有序区为空空的手。摸了第1张牌后，以后每次摸了牌都要和手上的牌比较（从最大1张开始比较），再插入到合适的位置，直到摸完牌。这个摸牌过程就是直接插入排序。9.2.1直接插入排序设待排序表有10个元素，其关键字序列为（9，8，7，6，5，4，3，2，1，0）。说明采用直接插入排序方法进行排序的过程。9.2.1直接插入排序【算法9.1】设计1个算法，对R[0..n-1]按递增有序进行直接插入排序。思路：见前面的直接插入排序算法思路。代码见算法9.19.2.2折半插入排序折半插入排序思路是对直接插入排序思路的改进，不相同的是在将无序区某个元素插入到有序区时，不再是在有序区从右到左找到插入位置，而是通过在有序区折半查找算法找到插入位置，其他都相同。9.2.2折半插入排序【算法9.2】设计1个算法，对R[0..n-1]按递增有序进行折半插入排序。思路：见前面的折半插入排序算法思路。代码见算法9.29.2.3希尔排序

9.2.3希尔排序设待排序表有10个元素，其关键字分别为（9，8，7，6，5，4，3，2，1，0）。说明采用希尔排序方法进行排序的过程。9.2.3希尔排序【算法9.3】设计1个算法，对R[0..n-1]按递增有序进行希尔排序。思路：见前面的希尔排序算法思路。代码见算法9.39.3交换排序交换排序的基本思想是两两比较待排序元素的关键字，若为正序则继续比较，若为反序则交换之，直到没有反序的元素为止。交换排序主要有冒泡排序和快速排序。举例：有男有女请7位同学上讲台，随意站成1排，从左往右进行身高从矮到高的冒泡排序。再请1位同学当导演，指挥他们如何做。这位导演说：从左往右，第1趟两两比较经过交换之后，最高的张三站到了最右边；第2趟次高的李四站在了右边倒数第2，依此类推经过6趟后，排序完成。9.3.1冒泡排序初始：有序区为空，无序区为R[0...n-1]。无序区元素两两比较，若反序则交换；这样1趟后最大/最小元素归位（如气泡一样冒于水面）。重复（2），n-1趟后所有元素归位即完成排序。9.3.1冒泡排序设待排序的表有10个元素，其关键字分别为{9，8，7，6，5，4，3，2，1，0}。说明采用冒泡排序方法进行排序的过程。9.3.1冒泡排序【算法9.4】设计1个算法，对R[0..n-1]按递增有序进行冒泡排序。思路：见前面的冒泡排序算法思路。代码见算法9.49.3.2快速排序在排序表中取第1个元素作为基准。将基准归位到最终位置，即1次划分：所有小于基准的元素放在基准左边（构成左子表），所有大于基准的元素放在右边（构成右子表）。对左右子表重复（1）、（2），直到每个子表只有1个元素或空为止。9.3.2快速排序设待排序的表有10个元素，其关键字分别为（6，8，7，9，0，1，3，2，4，5）。说明采用快速排序方法进行排序的过程。第1趟结果：5432016978 第2趟结果：1423056879第3趟结果：0123456789第4趟结果：0123456789第5趟结果：0123456789递归树的高度决定了快速排序的趟数9.3.2快速排序【算法9.5】设计1个算法，对R[0..n-1]按递增有序进行快速排序。思路：见前面的快速排序算法思路。代码见算法9.59.4选择排序选择排序的基本思想是初始有序区为空，每1趟排序从无序区中选出最小/最大的元素放在有序区最后，从而扩大有序区直到无序区为空。选择排序主要有简单选择排序和堆排序。9.4.1简单选择排序9.4.1简单选择排序设待排序的表有10个元素，其关键字分别为（6，8，7，9，0，1，3，2，4，5）。说明采用简单选择排序方法进行排序的过程。9.4.1简单选择排序【算法9.6】设计1个算法，对R[0..n-1]按递增有序进行简单选择排序。思路：见前面的简单选择排序算法思路。代码见算法9.69.4.2堆排序堆排序是用二叉树来选出最小/最大元素，是1种树形选择排序方法。堆的定义：1个序列R[1..n]，关键字分别为k1、k2...kn，将关键字序列按层次遍历构造为1棵完全二叉树，如图9.10所示。若ki≤k2i且ki≤k2i+1，则称其为小根堆；若ki≥k2i

且ki≥k2i+1，则称其为大根堆，其中1≤i≤n/2。9.4.2堆排序设待排序的表有10个记录，其关键字分别为{6，8，7，9，0，1，3，2，4，5}。说明采用堆排序方法进行排序的过程。9.4.2堆排序

9.5归并排序归并排序的基本思路是将2个或2个以上的相邻有序子表合并为1个有序表，经过多趟排序而完成整个序列有序。根据归并路数分为2路归并、3路归并、多路归并。9.5归并排序设排序序列有10个元素，其关键字分别为（18，2，20，34，12，32，6，16，1，15）。说明采用自顶向下2路归并排序方法进行排序的过程。9.5归并排序【算法9.8】设计1个算法，对R[0..n-1]按递增进行二路归并排序。思路：见前面的2路归并排序算法思路。代码见算法9.89.6分配排序分配排序的基本思想是不比较关键字大小，根据关键字各位上的值，进行若干趟“分配”和“收集”而完成排序。举例：4个同学，2男2女。按照性别和高矮排序，要求女同学先出列，个子矮的先出列。如图9.15所示，从右到左是出列顺序。在这个例子中，可将关键看作2位组成的，1位是性别，1位是高矮。9.6.1桶排序桶排序将待排序序列划分成若干个区间，每个区间可形象地看作一个桶，如果桶中的记录多于一个则使用较快的排序方法进行排序，把每个桶中的记录依次收集起来，得到有序序列。9.6.1桶排序有10个学生的成绩（68,75,54,70,83,48,80,12,75,92），对该成绩序列进行桶排序。学生成绩在0～100，可以划分为10个桶，即0～9，10～19，20～39，…，90～100。将学生成绩依次放入桶中；对桶内数据进行排序；依次收集桶中数据得有序序列（12，48，54，68，70，75，75，80，83，92）。9.6.1桶排序【算法9.9】设计1个算法，对R[0..n-1]按递增有序进行桶排序。思路：（1）按照数值区间划分桶，即初始化桶。（2）遍历无序表，根据元素值将其分配到对应桶中。（3）对每个桶中的元素进行排序。（4）收集每个桶中的元素，并将其输出为有序序列。代码见算法9.99.6.2基数排序基数排序是桶排序的扩展，它是1种多关键字排序算法。举例：扑克牌排序，扑克牌由数字和花色2个关键字组成。假设先按花色（♣,♦,♥,♠）顺序排序，再按面值（2,3,…,10,J,Q,K,A）顺序排序，则排序结果为2♣，...，A♣，2♦，...，A♦，2♥，...，A♥，2♠，...，A♠。假设2个关键字排序优先级交换，则排序结果为2♣，2♦，2♥，2♠，...，3♣，3♦，3♥，3♠，...，A♣，A♦，A♥，A♠。9.6.2基数排序设待排序表有8个元素，其序列为(369，367，167，239，237，138，230，139)。说明采用基数排序方法进行排序的过程。9.6.2基数排序【算法9.10】设计1个算法，按照最低位优先进行基数排序。思路：见前面的基数排序算法思路。代码见算法9.109.7排序应用【例9.1】小蓝老师教的编程课有N名学生，编号依次是1...N。第i号学生这学期刷题的数量是Ai。对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。（蓝桥杯竞赛真题）思路：（1）先对输入的数排序，如升序。（2）找到中间数（偏大）。（3）用中间数减比它小的那些数再加1。（4）输出中间数之前的值，和后面的若干个0。代码见应用9.19.7排序应用【进一步思考】例9.1算法不采用排序，能否实现？答：可以实现。只不过查找中间数不如折半查找效率高。9.7排序应用【例9.2】设a[0...n-1]表示n个学生的分数，每个分数在0到100之间，大于等于90为等级A，大于等于80小于90为B，大于等于70小于80为C，大于等于60小于70为D，其他为E。设计1个算法将