堆排序（Python与C语言实现）

堆排序（Python与C语言实现）

堆排序最好还是要找个动画看看具体的实现方法，推荐大家先看看这个视频，先大致了解算法的思路

清华博士72小时讲完的【数据结构与算法】整整100集，学完可就业！拿走不谢，学不会退出编程界_哔哩哔哩_bilibili

Python实现代码

def sift(li,low,high):              #low为根节点位置，high为堆的最后一个节点的位置 
    i = low
    j = i * 2 +1                    #由父节点找左子节点的方法
    t = li[low]                     # t 为堆顶的数据
    while j <= high:                #将数据排列为大根堆，堆顶为最大值 
        if j+1 <= high and li[j+1] > li[j]: #找出 a[i]的子节点中大的一个 作为 a[j]
            j = j+1
        if li[j] > t:
            li[i] = li[j]
            i = j
            j = i*2+1
        else:
            li[i] = t               #当 t 放到某一个根节点时退出循环
            break
    else:
        li[i] = t                   # t 无法放到任何一个根节点时，退出循环，将 t 放到最后一个叶子节点上 



def pai(li):
    n=len(li)
    for i in range((n-2)//2,-1,-1):#(n-2)//2为最后一个非叶子节点，由孩子节点找父节点的方法
        sift(li,i,n-1)              #从最后一个非叶子节点开始，使每一个叶子节点下均为堆 
    for i in range(n-1,-1,-1):      #循环，将最大的数放到堆的最后 
        li[0],li[i] = li[i],li[0]
        sift(li,0,i-1)
        #注意，最后一个数字已经是最大的数了，不在堆中

li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)

pai(li)
print(li)

C语言实现代码

#include
int main()
{
	void zhengli(int a[],int low,int high);		//将堆的调整 
	void jiandui(int a[],int n); 				//建立 堆 ，并将数据从小到大排列 
	int a[10];
	int i;
	for(i=0;i<10;i++)
	{
		scanf("%d",&a[i]);
	}
	jiandui(a,10);
	for(i=0;i<10;i++)
	printf("%d ",a[i]);
}

void jiandui(int a[],int n)
{
	int i,t;
	int k=(n-2)/2;				//由孩子节点找父节点的方法 
	for(i=k;i>=0;i--)			//从最后一个非叶子节点开始，使每一个非叶子节点下均为堆 
		zhengli(a,i,n-1);       //循环完成之后，所有数据就成了大根堆 
	for(i=n-1;i>=0;i--)
	{							//循环，将最大的数放到堆的最后 
		t=a[0];
		a[0]=a[i];
		a[i]=t;
		zhengli(a,0,i-1);		//重新调整堆，使得堆顶仍为堆中最大的数；
		//注意，最后一个数字已经是最大的数了，不在堆中 
	}
	
}

void zhengli(int a[],int low,int high)	//low为根节点位置，high为堆的最后一个节点的位置 
//循环从数据最后一个非叶子节点开始向前， 
{
	int t,i,j;
	i=low;
	j=i*2+1;							//由父节点找左子节点的方法 
	t=a[low];							// t 为堆顶的数据 
	while(j <= high)					//将数据排列为大根堆，堆顶为最大值 
	{
		if(a[j] < a[j+1] && j+1 <= high) //找出 a[i]的子节点中大的一个 作为 a[j] 
			j=j+1;
		if(a[j] > t)
		{
			a[i]=a[j];
			i=j;
			j=i*2+1;
		}
		else							//当 t 放到某一个根节点时退出循环 
		{
			a[i]=t;
			break;
		}
	}
	a[i]=t;       						//当 t 无法放到任何一个根节点时，退出循环，将 t 放到最后一个叶子节点上 
}