堆排序.txt

来自「C精彩编程百例源码」· 文本 代码 · 共 46 行

// myclass18.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;

void swap(int &a,int &b)
{
	a=a^b;
	b=a^b;
	a=a^b;
}

void Restore(int *tree, int s, int m)
{
	int j;
	int x=tree[s];
	for(j=s+s;j<=m;j+=j)
	{if(j<m&&(tree[j]<tree[j+1])) ++j;
	if(!(x<tree[j]))   break;
	tree[s]=tree[j];s=j;}
	tree[s]=x;
}

void HeapSort(int *r, int n)
{
	for(int i=n/2;i>=0;i--)
		Restore(r,i,n);
	for(i=n;i>0;i--)
	{
		swap(r[0],r[i]);
			Restore(r,0,i-1);
	}
}
int main(int argc, char* argv[])
{
	int a[15]={26,5,77,1,61,11,59,15,48,19,100,23,56,98,45};
	swap(a[0],a[1]);
	cout<<a[0]<<endl<<a[1]<<endl;
	HeapSort(a,15);
	for(int i=0;i<15;i++)
		cout<<a[i]<<endl;
	return 0;
}