首页 > 代码库 > 排序算法(五)

排序算法(五)

2. 选择排序—堆排序(Heap Sort)

堆排序是一种树形选择排序,是对直接选择排序的有效改进。

基本思想:

堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)为最小项(小顶堆)。

若以一维数组存储一个堆,则堆对应一颗完全二叉树,且所有非叶节点的值均不大于(或不小于)其子女的值,根节点的值(堆顶元素)的值是最小(或最大)的。如:

(a)大堆顶序列(96,83,27,38,11,09)

(b)小堆顶序列(12,36,24,85,47,30,53,91)

初始时把要排列的的n个数的序列看做是一颗顺序存储的二叉树(一维数组存储二叉树),调整他们的存储序,使之成为一个堆。将堆顶元素输出,得到n个元素中最小(或最大)的元素,这时堆的根节点的数最小(或最大)。然后对前面的n-1个元素重新调整使之成为堆,输出堆顶元素,得到n个元素中次小(或次大)的元素。依此类推,知道只有俩个节点的堆,并对他们做交换,最后得到n个节点的有序序列,称这个过程为堆排序。

 因此,实现堆排序需要解决俩个问题:

1、如何将n个待排序的数建成堆。

2、输出堆顶元素后,怎样调整剩余n-1个元素,使其成为堆。

 

首先,我们讨论第二个问题:输出堆顶元素后,对剩余的n-1个元素重新建成堆的调整过程。

调整小堆顶的方法(大堆顶也是一样的道理):

1、设有m个元素的堆,输出堆顶元素后,剩下m-1个元素。将堆底元素送入堆顶(最后一个元素与堆顶元素进行交换),堆被破坏,其原因仅是根节点不满足堆的性质。

2、将目前最新的根节点与左、右子数中较小元素进行交换。

3、若与左子数交换:如果左子数堆被破坏,即左子数的根节点不满足堆的性质,则重复方法(2)。

4、若与右子数交换,如果右子数堆被破坏,即右子数的根节点不满足堆的性质。则重复方法(2)。

5、继续对不满足堆性质的子数进行上述交换操作,知道叶子节点,堆被建成。

称这个字根节点到叶子节点的调整过程称为筛选。如图:

 

再讨论对n个元素初始建堆的过程。

建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

1、n个节点的完全二叉树,则最后一个节点是n/2个节点的子数。

2、筛选从第n/2个节点为根的子数开始,该子数成为堆。

3、之后向前一次对各节点为根的子数进行筛选,使之成为堆,直到根节点。

如图建堆的初始过程:无序序列:(49,38,65,97,76,13,27,49) 

算法的实现:

从算法的描述来看,堆排序需要俩个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以,堆排序有俩个函数组成,一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

public class HeapSort {    public static void main(String[] args) {        int[] a = {12,54,76,23,435,98,21,1,2,23,54,76,34,2,78,243};        heapSort(a, a.length);                for(int i=0; i<a.length; i++){            System.out.print(a[i]+" ");        }    }    /**     * 堆排序算法     * */    public static void heapSort(int[] a,int length){        buildingHeap(a, a.length);    //初始堆                for(int i=length-1; i>0; --i){            int temp = a[i];            a[i] = a[0];            a[0] = temp;            heapAdjust(a, 0, i);        }    }    /**     * 初始堆进行调整     * 将a[0..length-1]建成堆     * 调整完之后第一个元素师序列的最小元素     * */    public static void buildingHeap(int[] a,int length){        //最后一个有孩子的节点的位置i = length/2 - 1        for(int i=(length/2)-1; i>=0; --i){            heapAdjust(a, i, length);        }    }    /**     * 已知a[a...m]除了a[s]外均满足堆的定义     * 调整a[s],使其成为大顶堆,即将对第s个节点为根的子数帅选     *      * @param a是待调整的数组     * @param s是待调整的数组元素的位置     * @param length是数组的长度     * */    public static void heapAdjust(int[] a,int s,int length){        int temp = a[s];        int child = 2*s+1;    //左孩子节点的位置。        while(child < length){            if(child+1 < length && a[child] <a[child+1] ){//如果右孩子大于左孩子(找到比当前待调整节点大的孩子)                ++ child;            }            if(a[s]<a[child]){//如果较大的子节点大于父节点                a[s] = a[child];//那么把较大的子节点往上移动,替换他的父节点                s = child;    //重新设置s,即待调整的下一个节点的位置                child = 2*s+1;            }else{    //如果当前待调整节点大于他的左右孩子,则不需要调整,直接退出                break;            }            a[s] = temp;//当前待调整的节点放到比其大的孩子的节点的位置上        }    }}

算法分析:

设数深度为k,k=log2n+1。从根到叶的筛选,元素比较次数之多2(k-1)次,交换记录之多k次。所以,在建好堆后,排序过程中的次数不超过下式:

而建堆的比较次数不超过4n次,因此堆排序最坏情况下,时间复杂度也为:O(nlogn)。

排序算法(五)