算法笔记（第一部分）-- 排序之白话堆排序

堆排序是一种基于比较的排序算法，它比实现的较好的快速排序慢一些，但是它的平均时间复杂度为O(nlogn)，空间复杂度为О(n)，它是一种in-place的算法，但是却是不稳定的排序算法。

最大堆与最小堆的定义：
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为最小堆.

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者的堆称为最大堆.

P.S：

堆中任一子树亦是堆。本文讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

堆排序的过程：
1. 根据输入的数据集建立一个最大堆（最小堆）
2. 进行堆排序，将Root（最大值）与堆的最后一个元素交换
3. 堆调整，继续维护成为最大堆
4. 进行步骤2和3，直至排序完成

堆排序动画：


堆排序代码－siftDown:

public void siftDown(int[] data,int start, int end) {
          int root = start;
          while((2*root + 1)<=end){
                int child = root*2+1;
                if (child < end && data[child]<data[child+1]){
                      child++;
                }
                if (data[root]<data[child]){
                      swap(data,root,child);
                      root = child;
                }else
                      break;
          }
    }

这段代码是堆排序的核心，对堆中的元素进行调整。简单来说做的工作就是，针对一个堆点，将其与它孩子中较大的那个进行比较，若大不变，若小与该孩子交换位置，若交换后该堆点（处于原先它孩子的位置）仍有孩子则继续与孩子中较大的那个进行比较，若大不变，若小与该孩子交换位置，调整直至该堆点没有孩子结束。

heapify:

public void heapify(int[] data, int count){
          int start = (count-1)/2;
          while(start>=0){
                siftDown(data,start,count-1);
                start = start-1;
          }
    }

这段代码是建堆的过程，找到最后一个有孩子的堆点，对该堆点进行调整，直至调整到Root。

heapsort:

public void heapsort(int[] data, int count){
           heapify(data, count);
           int end = count - 1;
           while (end>0){
               swap(data, 0, end);
               siftDown(data, 0, --end);
           }
    }

这段代码解释了堆排序的过程，首先建堆，然后将Root与堆底元素交换，继而调整现有堆中Root（交换后的Root）的位置，不断的调整直至遍历完整个堆。

堆排序讲的比较乱，如有不能理解或我讲错的地方，希望大家能够指出。

评论

1 楼 lenky0401 2008-09-07  

马马虎虎的看完了
给LZ推荐两个网页

http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html
http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html