重庆石桥铺网站建设公司百度论坛首页

堆排序算法

首先先引入需要的辅助函数

#include<stdio.h>/*辅助函数：1.打印数据2.判断整个数据序列是否已经有序3.交互两个数据swap方法
*/void Show(int *arr,int len)//打印数据
{for(int i=0;i<len;++i){printf("%d  ",arr[i]);}printf("\n");
}bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
{for(int i=0;i<len-1;++i){if(arr[i]>arr[i+1]){return false;}}return true;
}void SwapValue(int *a,int *b)//交互两个数据swap方法
{int tmp=*a;*a=*b;*b=tmp; 
}

堆排序算法需要用到完全二叉树
满二叉树：深度为k的二叉树，他的节点个数为2^k-1
完全二叉树： 从根节点开始，对节点个数为n的二叉树进行编号，深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时。

堆：最大堆 – 每一棵子树，他的根节点比左右孩子都大
最小堆 – 每一棵子树，他的根节点比左右孩子都小

堆排序的思想
堆排序中的堆是一棵完全二叉树：
如果当前的父节点下标为 i ， 则左孩子的下标 2i+1,
右孩子的下标 2i+2
如果一个孩子的下标是j，则其父节点的下标是 （j-1）/2

堆排序过程： 将待排序序列构建成一个大根堆
整个调整是从最后一棵子树开始向上调整
每次的调整过程都是从这个子树的根向下调整
再执行排序过程

接下来是对堆排序算法的实现

void OneAdjust(int *arr,int len,int root)//进行一次调整
{int i=root;int tmp=arr[i];int j=2*i+1;while(j<len){if(j+1<len&&arr[j+1]>arr[j]) j++;if(arr[j]<tmp) break;arr[i]=arr[j];i=j;j=2*i+1;}arr[i]=tmp;
}void CreateHeap(int *arr,int len)//从最后一棵子树开始
{//最后一棵子树的根节点下标int last_root=(len-2)/2;for(int i=last_root;i>=0;--i){OneAdjust(arr,len,i);} 
}void HeapSort(int *arr,int len)
{CreateHeap(arr,len);for(int i=0;i<len-1;++i){SwapValue(&arr[0],&arr[len-1-i]);OneAdjust(arr,len-1-i,0);}
}

最后完成主函数

int main()
{int arr[]={7,87,29,75,41,50,62,92,69,22,76,77,35};Show(arr,sizeof(arr)/sizeof(arr[0]));HeapSort(arr,sizeof(arr)/sizeof(arr[0]));Show(arr,sizeof(arr)/sizeof(arr[0])); return 0;}

运行结果如下

堆排序的分析
时间复杂度： O(nlogn)
空间复杂度： O(1)
稳定性： 不稳定（有跳跃数字）