首页 > C++编程 > C++堆排序类

C++堆排序类

恩,自己写的一个堆排序,顺便写成了一个类。不过没有写注释~~:)直接贴代码吧,准备搞一下软件设计师,所以看点东西补补身子。

//By 代码疯子
//Blog http://www.programlife.net/
//Date 2010-09-26
#include <iostream>
#include <cstdio>
using namespace std;

#define MAX_HEAP_NUM 1024
#define PARENT(i) (i>>1)
#define LEFT(i) (i<<1)
#define RIGHT(i) ((i<<1)+1)

class HeapSort
{
private:
	int a[MAX_HEAP_NUM];
	int heapSize;
	int elemSize;
	
private:
	void maxHeapify(int i);
	void buildMaxHeap();
	
public:
	HeapSort();
	HeapSort(int num[], int n);
	
public:
	void init(int num[], int n);
	void sort();
	void print();
};

HeapSort::HeapSort()
{
	heapSize = elemSize = 0;
}

HeapSort::HeapSort(int num[], int n)
{
	int i;
	elemSize = n;
	
	for(i = 1; i <= n; ++i)
	{
		a[i] = num[i - 1];
	}
}

void HeapSort::init(int num[], int n)
{
	int i;
	elemSize = n;
	
	for(i = 1; i <= n; ++i)
	{
		a[i] = num[i - 1];
	}
}

void HeapSort::maxHeapify(int i)
{
	int l = LEFT(i);
	int r = RIGHT(i);
	int largest;
	
	if(l <= heapSize && a[l] > a[i])
	{
		largest = l;
	}
	else
	{
		largest = i;
	}
	
	if(r <= heapSize && a[r] > a[largest])
	{
		largest = r;
	}
	
	if(largest != i)
	{
		swap(a[largest], a[i]);
		maxHeapify(largest);
	}
}

void HeapSort::buildMaxHeap()
{
	int i;
	heapSize = elemSize;
	
	for(i = (elemSize>>1); i >= 1; --i)
	{
		maxHeapify(i);
	}
}

void HeapSort::sort()
{
	int i;
	buildMaxHeap();
	
	for(i = elemSize; i >= 2; --i)
	{
		swap(a[i], a[1]);
		--heapSize;
		maxHeapify(1);
	}
}

void HeapSort::print()
{
	int i;
	for(i = 1; i <= elemSize; ++i)
	{
		printf("%5d", a[i]);
	}
	printf("\n");
}

int main()
{
	int num[100], i, n;
	
	scanf("%d", &n);
	for(i = 0; i < n; ++i)
	{
		scanf("%d", &num[i]);
	}
	
	HeapSort heapSort(num, n);
	heapSort.sort();
	heapSort.print();
	
	return 0;
}

 


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> C++堆排序类
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: C++编程 标签: , , , ,
  1. 2010年9月27日03:54 | #1

    C++的太复杂了  看一会眼睛就受不了了
     
    挺喜欢delphi的   还在入门阶段

    [回复]

    代码疯子 回复:

    delphi感觉和VB差不多,都是封装了很多细节,所以你看起来不累。呵呵

    [回复]

  2. 2010年9月27日06:35 | #2

    头疼…..

    [回复]

    代码疯子 回复:

    慢慢熟悉就好

    [回复]

  1. 2010年9月26日15:33 | #1