第9章 排序教学课件.pptx

第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 希尔排序?希尔排序是一种分组插入排序，思路如下：设有n个元素，取；将排序序列分为d个组，相距d个位置的元素分为1组；在各组内进行直接插入排序；递减，重复（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趟结果：5 4 3 2 0 1 6 9 7 8 第2趟结果：1 4 2 3 0 5 6 8 7 9第3趟结果：0 1 2 3 4 5 6 7 8 9第4趟结果：0 1 2 3 4 5 6 7 8 9第5趟结果：0 1 2 3 4 5 6 7 8 9递归树的高度决定了快速排序的趟数9.3.2 快速排序【算法9.5】设计1个算法，对R[0..n-1]按递增有序进行快速排序。思路：见前面的快速排序算法思路。代码见算法9.59.4 选择排序选择排序的基本思想是初始有序区为空，每1趟