数据结构(第九章 排序).ppt
文本预览下载声明
直接选择排序 直接选择排序 ([] ) 直接选择排序(升序) { (直接选择排序(升序)); ( ; ; ) 趟排序 { ; ( ; ; ) 每趟在从[]开始的子序列中寻找最小元素 ([][]) (升序) ([][]) (降序) ; 记住本趟最小元素下标 (第()趟,下标~(),,); () 将本趟最小元素交换到前边 (, , ); (); } } 选择排序 选择排序特殊举例 选择排序 直接选择排序 算法分析 上述算法优点: 简单 稳定性: 不稳定排序 给定排序码为,,,,,排序后的结果为,,,, 直接选择排序算法不稳定。 选择排序 直接选择排序 比较: 无论状态如何,在第趟排序中选出最大关键字记录,需做次比较。因此,总的比较次数为: *() 交换: 在每一遍中只执行次交换,总的交换次数为次 算法分析 选择排序 直接选择排序 习题 直接选择排序 {, , , , , , , *, }, (升序)每趟,说明稳定性。 【答】直接选择排序算法不稳定。 第趟 ,{} * 第趟 ,{ } * 第趟 ,{ } * 第趟 ,{ } * 第趟 ,{ *} 第趟 ,{ * } 第趟 ,{ * } 第趟 ,{ * } 选择排序 直接选择排序 若有个元素的排序码,,,…,,当满足如下条件: ≤ ≥ () ≤ 或 () ≥ 其中,…,?? 则称此个元素的排序码,,,…,为一个堆。 若将此排序码按顺序组成一棵完全二叉树,则()称为小根堆(二叉树的所有根结点值小于或等于左右孩子的值),()称为大根堆(二叉树的所有根结点值大于或等于左右孩子的值)。 改进的选择排序-堆排序 选择排序 堆排序 选择排序 堆排序 习题 说明堆与二叉排序树的差别。 选择排序 堆排序 若个元素的排序码,,,…,满足堆,且让结点按、、、…、顺序编号,根据完全二叉树的性质(若为根结点,则左孩子为,右孩子为)可知,堆排序实际与一棵完全二叉树有关。若将排序码初始序列组成一棵完全二叉树,则堆排序可以包含建立初始堆(使排序码变成能符合堆的定义的完全二叉树)和利用堆进行排序两个阶段。 堆排序算法 选择排序 堆排序 堆排序的基本思想 将排序码,,,…,表示成一棵完全二叉树,然后从第?? 个排序码开始筛选,使由该结点作根结点组成的子二叉树符合堆的定义,然后从第?? 个排序码重复刚才操作,直到第一个排序码止。这时候,该二叉树符合堆的定义,初始堆已经建立。 接着,可以按如下方法进行堆排序:将堆中第一个结点(二叉树根结点)和最后一个结点的数据进行交换(与),再将重新建堆,然后和交换,再将重新建堆,然后和交换,如此重复下去,每次重新建堆的元素个数不断减,直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成,则排序码,,,…,已排成一个有序序列。 选择排序 堆排序 若排序是从小到大排列,则可以用建立大根堆实现堆排序,若排序是从大到小排列,则可以用建立小根堆实现堆排序。 例如,给定排序码,,,,,,,,建立初始堆的过程如下图所示。 堆排序举例 选择排序 堆排序 选择排序 堆排序 对排序码,,,,,,,,建成如图所示的大根堆后,堆排序过程如下图所示。 选择排序 堆排序 选择排序 堆排序 选择排序 堆排序 从上图可知,将其结果按完全二叉树形式输出,则得到结果为:,,,,,,,,即为堆排序的结果。 选择排序 堆排序 堆排序算法实现 ( []) 堆排序,降序,最小堆 (
显示全部