堆排序的简单实现

简单实现"/>

堆排序的简单实现

堆排序算法

简要说明：关于堆排序（要具体的看/%E5%A0%86%E6%8E%92%E5%BA%8F/2840151?fr=aladdin链接），首先你得了解什么是堆，通俗一点讲堆的条件1.完全二叉树/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin（不懂请自行充电）2.父节点要大于子节点

堆的结构        

一般都用数组来表示堆，i结点它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。这是从0开始的结构。

堆的分类    

    堆分为最大堆（大顶堆）和最小堆（小顶堆），顾名思义就是父节点和左右孩子节点的关系，如果父节点大于所有的子节点的堆就是大顶堆，父节点小于所有子节点的堆就是小顶堆，选择大顶堆和小顶堆决定了排序的顺序，是从大到小还是从小到大排序。

。。。。。。下面还是通过代码描述吧！

​
#include<iostream>
using namespace std;
/*
arr为一棵完全二叉树
i为默认最大值
size为树的结点个数 
*/ 
/*函数功能：将父节点与子节点比较，实现父节点大于子节点 
*/
void three_max(int arr[],int i,int size){if(i<size){int left=2*i+1;int right=2*i+2;int largest=i;if(left<size){if(arr[largest]<arr[left]){largest=left;}}if(right<size){if(arr[largest]<arr[right]){largest=right;}}if(largest!=i){int temp=arr[largest];arr[largest]=arr[i];arr[i]=temp;three_max(arr,largest,size);}}
}
void heap_ljw(int arr[],int size){//建堆过程，实现所有结点满足堆的条件 for(int i=size-1;i>=0;i--){three_max(arr,i,size);}
}
void heap_sort(int arr[],int size){//不断的将每次筛选出的最大值切断，递归建堆 for(int i=size-1;i>=0;i--){heap_ljw(arr,i+1);int temp=arr[0];arr[0]=arr[i];arr[i]=temp;}
}
int main(){int arr[]={12,345,6,8,0,9,56789};heap_ljw(arr,7);//每次将最大值放到数组的前面 for(int j=0;j<7;j++){cout<<arr[j]<<" ";}cout<<endl;heap_sort(arr,7);//堆排完成 for(int i=0;i<7;i++){cout<<arr[i]<<" ";}return 0;
}​

可能，要恭喜那个看得懂的你了，写的不好，多担待！（跟着大佬学的，哈哈！！！）       

                                                                                                                                       L-MP