616      阿裏雲  技術社區[雲棲]

堆排序【模板】

很認真地看完了《算導》的排序之前的所有部分，除了算法複雜度那一章的數學要求太高，難以完全駕馭以外，其他的部分還是很好理解的。。。

爭取把《算導》裏麵出現的算法都自己實現，製作自己的模板，以後好用。。。堆排序雖然在一般的時候是沒有快排好用，但是在優先隊列裏麵很好用，所以也是很有力的武器！

這個堆排序模板是我基本完全按照《算法導論》裏麵自己一個字一個字的敲上去的，調試的時候修改了幾個小地方：1.heapsize，開始我準備寫一個函數的，但是因為在sort函數裏麵要執行自減操作，所以必須要用全局變量才好處理；2.《算導》裏麵是從數組下標的1開始的，所以我在賦初值的時候將 A[0] 跳過了

#include <iostream>

//堆長度
int heapsize;

//大頂堆化
void MAX_HEAPIFY(int A[],int i)
{
	int l=2*i;		//把 i 的左兒子 下標 賦給l
	int r=2*i+1;		//把 i 的左兒子 下標 賦給r
	int largest;	//3個裏麵最大的下標

	if(l<=heapsize && A[l]>A[i])
		largest=l;
	else
		largest=i;

	if(r<=heapsize && A[r]>A[largest])
		largest=r;

	if(largest!=i)
	{
		//交換 A[largest] 和 A[i]
		int tmp=A[largest];
		A[largest]=A[i];
		A[i]=tmp;

		MAX_HEAPIFY(A,largest);
	}
}

//建堆
void BUILD_MAX_HEAP(int A[])
{
	int i;
	for(i=(int)(heapsize/2);i>=1;i--)
		MAX_HEAPIFY(A,i);
}

//堆排序
void HEAPSORT(int A[])
{
	BUILD_MAX_HEAP(A);		//ok

	int i;
	int tmp;
	for(i=heapsize;i>=2;i--)		//A[1] 必定是最大的
	{
		//交換 A[1] 和 A[i]
		tmp=A[1];
		A[1]=A[i];
		A[i]=tmp;

		heapsize--;
		MAX_HEAPIFY(A,1);
	}
}

int main()
{
	int A[6]={0,5,3,2,1,4};
	//ok
	int n=sizeof(A)/sizeof(int)-1;
	heapsize=n;

	HEAPSORT(A);

	for(int i=1;i<=n;i++)
		printf("%d ",A[i]);

	return 0;
}

1 2 3 4 5

最後更新：2017-04-03 14:53:55

  上一篇： Android 多分辨率屏顯設計及其兼容性測試

  下一篇： 技術人員談管理之整體管理案例論文