heapsort.cpp

非常全的排序算法c实现

/*算法思想简单描述：
 由堆的定义，堆顶元素必为最大项。
 初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，
 使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点
 交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点
 的堆，并对它们作交换，最后得到有n个节点的有序序列。

 堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。
 所以堆排序有两个函数组成:一是建堆的渗透函数，二是反复调用渗透函数
 实现排序的函数。*/
#include<iostream.h>
#define MAX 4
void FilterDown(int a[],int i,int N);//建堆
void HeapSort(int a[],int N);//堆排序

int main() //测试堆排序
{
   int *p,i,n,a[MAX];
   n=MAX;
   p=a;//指针指向数组
   cout<<"Input "<<n<<" number for sorting:"<<endl;//录入测试数据
   for(i=0;i<n;i++)
   {
	  cin>>a[i];
   }
   cout<<endl;
   HeapSort(p,MAX);

   cout<<"After HeapSort:"<<endl;
   for(i=0;i<n;i++)
   {
      cout<<a[i]<<" ";
   }
   cout<<endl;
   return 0;
}


 /*功能：建堆
   输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始*/
void FilterDown(int a[],int i,int N)
{
   int child =2*i+1; //右子树元素下标
   int temp=a[i];//暂存开始元素
   while(child<N)
   {
     if (child<N-1&&a[child]<a[child+1])//判断是否满足堆的条件：满足就继续下一轮比较，否则调整。
		 child++;
     if (temp<a[child])//调整
	 {
        a[i]=a[child]; 
        i=child;
	    child=2*i+1;
	 }	
	else 
	    break;//不需调整，结束调整	 
   }
  a[i]=temp;//开始元素放到它正确位置
}

 /*功能：堆排序
   输入：数组名称（也就是数组首地址）、数组中元素个数*/
void HeapSort(int a[], int N)
{
   int i; 
   for (i=(N-2)/2; i>=0;i--)
	   FilterDown(a,i,N);//初始生成最大堆
   for (i=N-1;i>0;i--)
   {
      int temp;
	  temp=a[0];
	  a[0]=a[i];
	  a[i]=temp;//堆顶元素与最后一个元素交换
    
      FilterDown(a,0,i);//剩下的数再建堆
   }
}