Heap Sort

http://www.ntnoi.cn/FLASH/arithmetic/各种算法的动态演示
http://www.cnblogs.com/tanky_woo/算法学习的好地方

最后，给大家推荐我在网上看到的写的不错的几篇堆排序文章：
1.http://blog.csdn.net/super_chris/archive/2009/09/22/4581900.aspx
  这一篇讲得很细致。
2.http://blog.csdn.net/made_in_chn/archive/2010/04/12/5473871.aspx
  大家可以看看文章里的图，注意那是最小堆实现的图。
3.http://blog.csdn.net/midgard/archive/2009/04/14/4070074.aspx
  同样讲的很细致的一篇。
4.http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.2.htm
   这是网站很给力，有flash模拟堆排序，大家可以实际去看看。

1.原地排序 就是指不申请多余的空间来进行的排序，就是在原来的排序数据中比较和交换的排序。例如快速排序，堆排序等都是原地排序，合并排序，计数排序等不是原地排序。
排序稳定就是指：如果两个数相同，对他们进行的排序结果为他们的相对顺序不变。
2堆的定义:    　
      n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
      (1)ki<=k(2i+1)且ki<=k(2i+2)(1≤i≤ n),当然，这是小根堆，大根堆则换成>=号。 //ki相当于二叉树的非叶结点，K2i则是左孩子，k2i+1是右孩子　　
      若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
      树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
堆排序：
　　堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlogn)。
　　堆排序的特点是：在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。
堆排序基本思想：
　　1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
　　2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。重复操作，无序区在递减，有序区在递增。
完全二叉树的基本性质：
　　数组中有n个元素，i是节点,1 <= i <= n/2 就是说数组的后一半元素都是叶子节点。
     i的父节点位置：i/2
     i左子节点位置：i*2
     i右子节点位置：i*2 + 1

详细的解释 和code 来源
http://blog.csdn.net/super_chris/article/details/4581900

	#include <iostream>
	using namespace std;
	template<class T>
	void Sift(T* heap,int start,int end) //start和end标示无序区
	{
	T temp = heap[start]; //记录
	int parent = start;
	int child = 2*start+1;
	while (child<=end)
	{
	if(child<end&&heap[child]<heap[child+1])
	child++;
	if(heap[child]>temp)
	{
	heap[parent]=heap[child];
	parent = child;
	child = 2*child+1;
	continue;
	}
	else
	break;
	}
	heap[parent] = temp;
	}
	template <class T>
	void MakeHeap(T* heap,int Size)
	{
	int end;
	for(int start = Size/2-1;start>=0;start--)
	Sift(heap,start,Size-1);
	}
	template <class T>
	void HeapSort(T* heap,int Size)
	{
	MakeHeap(heap,Size);
	T temp;
	for (int i = Size-1;i >= 0;i--)
	{
	temp = heap[i];
	heap[i] = heap[0];
	heap[0] = temp;
	Sift(heap,0,i-1);
	}
	for (int i = 0;i < Size;i++)
	{
	cout<<heap[i]<<endl;
	}
	}
	int main()
	{
	int num[10] = {1,4,3,8,9,0,2,7,5,6};
	HeapSort<int>(num,10);
	}

view raw gistfile1.cpp hosted with ❤ by GitHub