算法笔记（第一部分）-
堆排序是一种基于比较的排序算法，它比实现的较好的快速排序慢一些，但是它的平均时间复杂度为O(nlogn)，空间复杂度为О(n)，它是一种in-place的算法，但是却是不稳定的排序算法。最大堆与最小堆的定义：
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为最小堆.
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者的堆称为最大堆.
P.S：
堆中任一子树亦是堆。本文讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
堆排序的过程：
1. 根据输入的数据集建立一个最大堆（最小堆）
2. 进行堆排序，将Root（最大值）与堆的最后一个元素交换
3. 堆调整，继续维护成为最大堆
4. 进行步骤2和3，直至排序完成
堆排序动画：
http://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif
堆排序代码－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<data){ child++; } if (data<data){ 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]