首页 > 代码库 > [2] 算法之路 - 选择之堆排序

[2] 算法之路 - 选择之堆排序

题目:

选择排序法的概念简单,每次从未排序部份选一最小值,插入已排序部份的后端,其时间主要花费于在整个未排序部份寻找最小值,如果能让搜寻最小值的方式加 快,选择排序法的速率也就可以加快

Heap排序法让搜寻的路径由树根至最后一个树叶,而不是整个未排序部份,从而可以加快排序的过程,因而称之为改良的选择排序法


整个堆排序的过程分建堆、取值、调整为新的堆三个过程。分别如下示:(以最小堆积树为例。关于HeapTree请参阅数据结构与算法) 

建堆 - 算法

1、  加至堆积树的元素会先放置在最后一个树叶节点位置

2、  然后检查父节点是否小于子节点(最小堆积)

3、  将小的元素不断与父节点交换,直到满足堆积树的条件为止


取最小值算法

1、将根节点与最后一叶子结点交换

2、树长度减一,调整树为新的堆积树


调整为新堆积树算法

1、  比较左孩子节点与右孩子节点,取其较小一个节点

2、  比较孩子节点与父节点,若父节点大则交换孩子与父节点,令孩子节点为新的父节点,并求其新的孩子节点;程式进入1.循环


SourceCodes


// 创建最小堆积树- 建堆算法
// 1. 加至堆积元素先放置在最后一个叶子节点的位置
// 2. 检查父节点是否小于子节点,若小,则交换父节点与子节点
// 3. 将父节点设置为新的子节点,同时求其新的父节点,程式进入.循环
int CreatMinHeap3(int a[],int lens)
{
	int i;// 临时增量变量
	int child,parent;// 子节点与父节点下标
	int* pheap=new int[lens];	// 新的堆
	
	for(i=1;i<lens;i++)
	{
		pheap[i]=a[i];
		child=i;
		parent=child/2;
		while(child>=2 && pheap[parent]>pheap[child])
		{
			SWAPER(pheap[parent],pheap[child]);
			child=parent;
			parent=child/2;
		}
	}
	for(i=1;i<lens;i++)
	{
		a[i]=pheap[i];
	}
	delete pheap;
    pheap=NULL;

	return 0;
}


// 调整最小堆积树
// 1. 比较左孩子节点与右孩子节点,取其较小一个节点
// 2. 比较孩子节点与父节点,若父节点大则交换孩子与父节点,令孩子节点为新的父节点,并求其新的孩子节点,程式进入1.循环
int AdjustMinHeap2(int a[],int specificlens)
{
	

	if(specificlens<2) return -1;
	if(specificlens==2) 
	{
		if(a[1]>a[2]) SWAPER(a[1],a[2]);
		return 0;
	}

	int tail=specificlens;
	int parent=1;
	int child=2*parent;

	while(child+1<=tail)
	{
		if(a[child]<a[child+1])
		{
			if(a[parent]>a[child])
			{
				SWAPER(a[parent],a[child]);
				parent=child;
				child=2*parent;
			}
			else break;
		}
		else
		{
			if(a[parent]>a[child+1])
			{
				SWAPER(a[parent],a[child+1]);
				parent=child+1;
				child=2*parent;
			}
			else break;
		}
		
	}
	return 0;
}



// 堆排序
// 1. 建立最小堆积树
// 2. 取下最小节点 (交换最小堆积树的根与最后一个节点)
// 3. 树长度减一,调整新的堆为最小堆积树.
// 4. 程式进入.2循环
int HeapSort(int a[],int lens)
{
	CreatMinHeap3(a,lens);

	int i = 0;
	int parent,child;
	int m=lens-1;
	
	while(m>1)
	{
		SWAPER(a[1],a[m]);
		m--;
		AdjustMinHeap2(a,m);
	}
	return 0;
}