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

时间：2021-09-29 11:07:01

题目：

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

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;
}
 



 


标签：
相关文章