堆排序(HeapSort) -- C++实现


实现代码

// HeapSort.h
#ifndef HEAPSORT_H
#define HEAPSORT_H

#include<iostream>
using namespace std;

#include "Component.h"

namespace jay{

	// [下沉]调整子节点 最大堆
	template<typename T>
	void Sink(T *input,int k,int n)
	{
		while (2*k <= n) 
		{
			// k的左子节点
			int leftnode = 2*k;

			// 比较左/右节点 找出较大的节点
			if (leftnode < n && input[leftnode] < input[leftnode+1]) 
				leftnode++;
			// 比较父节点与较大的子节点
			if (input[k] > input[leftnode])
				break;

			// 如果子节点比父节点大,则交换他们的位置
			ExchangeArrayElements(input,k, leftnode);

			k = leftnode;

		}
	}

	template< typename T >
	void HeapSort(T *input,int input_len )
	{
		int nRightIndex = input_len;

		// 初始化最大堆的另外一个解法
		// 可以用swim来解决,使用sink是更优的解法
		for (int k = input_len/2; k >= 1; k--)
		{
			Sink(input,k,nRightIndex);
		}

		// 此时input已是最大(二叉)堆


		while (nRightIndex > 1) 
		{
			// input[1]和input[nRightIndex]交换位置
			// input[nRightIndex]保存input[1]到input[nRightIndex]的最大值
			ExchangeArrayElements(input,1,nRightIndex);
			nRightIndex--;

			// 重排最大堆
			Sink(input,1,nRightIndex);
		}
		
	}


};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

#include <iostream>
using namespace std;

#include "Component.h"
#include "HeapSort.h"

using namespace jay;


int main(int argc, char* argv[])
{

	int iCount = 0;
	cin>>iCount;
	int *testarray = new int[iCount+1];

	iCount = 0;
	int p;
	while(cin>>p)
	{
		// testarray数组的0不使用
		iCount++;
		testarray[iCount] = p;
	}

//	PrintArray<int>(&testarray[1],iCount,"排序前:");

	TimeCalculator timec;
	HeapSort<int>(testarray,iCount);
	timec.PrintTimeInfo();

//	PrintArray<int>(&testarray[1],iCount,"排序后:");
	
	cout << "是否已序? " << isSortedAndPrintInfo<int>(testarray,1,iCount) << endl;

	delete []testarray;

}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。