选择排序法
常用的选择排序方法有两种: 直接选择排序 和 堆排序 。
直接排序简单直观,但性能略差;
堆排序是一种较为高效的选择排序方法,但实现起来略微复杂。
直接选择排序的思路很简单,它需要经过n-1趟比较。
直接选择排序的优点是算法简单,容易实现。
直接选择排序的缺点是每趟只能确定一个元素,n个数组需要进行n-1趟比较。
封装的实体类
具体的算法与测试
假设有n个数据元素的序列k0,k1,…,kn-1,当且仅当满足如下关系时,可以将这组数据称为小顶堆(小根堆)。
ki <= k2i+1且ki <= k2i+2(其中i=0, 2,…,(n-1)/2)
或者,满足如下关系时,可以将这组数据称为大顶堆(大根堆)。
ki >= k2i+1且ki >=k2i+2(其中i=0, 2,…,(n-1)/2)
对于满足小顶堆的数据序列k0,k1,…,kn-1,如果将它们顺序排成一棵完全二叉树,则此树的特点是:树中所有节点的值都小于其左右子节点的值,此树的根节点的值必然最小。反之,对于满足大顶堆的数据序列k0,k1,…,kn-1,如果将它们顺序排成一棵完全二叉树,则此树的特点是:树中所有节点的值都大于其左右子节点的值,此树的根节点的值必然最大。
通过上面介绍不难发现一点,小顶堆的仁义子树也是小顶堆,大顶堆的任意子树还是大顶堆
例:判断数据序列
9,30,49,46,58,79是否为堆,将其转换为一个完全二叉树
判断数据序列:93,82,76,63,58,67,55是否为堆,将其转换为一个完全二叉树
堆排序的关键在于建堆,它按如下步骤完成排序。
通过上面介绍不难发现,堆排序的步骤就是重复执行以下2步。
(1)建堆;
(2)拿堆的根节点和最后一个节点交换。
由此可见,对于包含n个数据元素的数据组而言,堆排序需要经过n-1次建堆,每次建堆的作用就是选出该堆的最大值或最小值。因为堆排序的本质上依然是一种选择排序。
例如如下数据组:
9,79,46,30,58,49
建堆过程
具体算法