堆排序C++实现

满二叉树：所有分支节点多有左右孩子，而且所有叶子节点都在同一层的二叉树称为满二叉树

完全二叉树：对一棵二叉树按层序编号，编号为i（1<=i<=n）的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，这个二叉树就称为完全二叉树

堆：每个节点都小于或等于（大于等于）左右孩子的完全二叉树

堆排序步骤

把初始数组调整成一个堆将堆顶元素和数组的最后一个元素交换位置，此时的最后一个元素就处于有序区由于最后一个元素被交换到堆顶的位置，所以继续将该二叉树调整为堆（不包括后面有序区的元素）重复执行2,3步骤，执行n-1次，得到的数组就被排序好了

把以某一节点为根节点的子树跳转为堆

//a为要排序的数组，k为要调整为堆的某一节点的序号，n为堆的最后一个节点的编号 void sift(int a[],int k,int n){ int i=k,j=2*i; //2*i为第i个节点的左孩子 while(j<=n){ if(j<n&&a[j]<a[j+1]) //将j指向i的左右孩子值较大的那个节点 j++; if(a[i]>a[j]) //如果第i个节点的值大于较大孩子的值，就不用 //调整该节点了，直接跳出 break; else{ //如果第i个节点的值小于较大孩子的值，交换它们 //的值，然后对交换后的子树再进行调整 swap(a[i],a[j]); i=j; j=2*i; } } }

堆排序算法

void heapSort(int a[],int n){ for(int i=n/2;i>=1;i--) //对数组进行初始化为堆，从第一个叶 // 子节点的前一个节点开始 sift(a,i,n); for(int i=1;i<n;i++){ //对堆进行n-1次交换并调整为堆 swap(a[1],a[n-i+1]); //将堆顶元素交换到n-i+1的位置， //此时n-i+1到n的元素都已经排好序 sift(a,1,n-i); } }

主函数

#include<iostream> using namespace std; void sift(int a[],int,int); void heapSort(int a[],int); int main(){ int a[]={0,36,30,18,40,32,45,22,50}; int n=sizeof(a)/sizeof(int); heapSort(a,n-1); for(int i=1;i<n;i++) cout<<a[i]<<" "; cout<<endl; return 0; }