//堆排序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void swap(int* a,int* b)//用于换位
{
int tamp;
tamp=*a;
*a=*b;
*b=tamp;
}
void heapify(int a[],int i,int n)//找最大的值,两数换位。有换位时一直遍历到叶子节点
{
int largest=i;
int lson=i*2+1;
int rson=i*2+2;
if(a[largest]<a[lson]&&lson<n)
{
largest=lson;
}
if(a[largest]<a[rson]&&rson<n)
{
largest=rson;
}
if(largest!=i)
{
swap(&a[largest],&a[i]);
heapify(a,largest,n);
}
}
void heap_sort(int a[],int n)//排序和交换操作
{
int i;
for(i=n/2-1;i>=0;i--)//从叶子节点的父节点开始的(即支节点)排序操作。这里i=4时开始构建初始大根堆
{
heapify(a,i,n);
}
for(i=n-1;i>0;i--)//交换最后一个叶子节点和第一个节点的值,从后面开始向前规律排序
{
swap(&a[i],&a[0]);
heapify(a,0,i);//从头开始往下遍历,维护大根堆性质
}
}
void print(int a[],int n)//输出
{
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
int main()
{
int a[10]={2,3,8,1,4,9,10,7,16,14};
int n=10;
print(a,n);
heap_sort(a,n);
print(a,n);
}
关键知识:
递归,交换,排序
小白问:
1.堆排序是在堆里运行的排序吗?
答:不是,堆排序算法的名称来源于它使用了一个数据结构叫做"堆"。但是,这里的"堆"并非指的是计算机内存中的堆(heap),而是一种完全二叉树的一种抽象数据结构。
堆排序算法的实质是通过将待排序的元素构建成一个大根堆(或小根堆),然后反复地将堆顶元素与堆中最后一个元素交换,并调整堆,使得剩余元素仍然满足堆的性质。通过这样的操作,最终可以得到一个有序的序列。
在堆排序过程中,并不直接在内存的堆(heap)上进行排序操作,而是通过对抽象数据结构"堆"的操作来实现排序。堆可以使用数组来表示,通过数组的下标关系来表示节点之间的关系,这样,在堆排序算法中,实际上是对数组元素的位置进行交换和调整,以实现排序的目的。
2.堆排序的优势有什么?
答:堆排序算法具有时间复杂度低、空间复杂度低、稳定性好、适用范围广等优势。在某些场合下,它比其他常见的排序算法更加高效和实用。
复杂度:?
时间复杂度:O(NlogN)
空间复杂度:O(1)
稳定性:相同值的可能不稳定(对于相同的值而言,可能比较后位置不确定),总体是稳定的(不相等的值时间没有影响)
NO.42
有不完整的内容欢迎评论🌹🌹🌹
<C语言数据结构>?