189 8069 5689
堆排序：堆排序是一个时间复杂度为O(nlogn)空间复杂度为O(1)的十分优秀且非常稳定的排序算法，不论是在最好还是最坏情况下，其时间复杂度都稳定在O(nlogn),同时一般也可以用来快速求出一组数据中大或最小的前几个数。
堆排序算法的过程主要可以分为三个部分，调整部分（也是最主要的过程）、建堆和排序。接下来详细介绍这三个过程的步骤。
1.调整过程：调整就是将一组数据，从非堆的状态调整为堆的状态。堆就是满足如下定义的结构(以大顶堆为例，大顶堆排序得到的升序序列)，左右孩子都小于自身，且其左右孩子所构成的堆也满足该定义。假设调整的是第i个数据，那么需要比较的就是arr[2i]与arr[2i+1]的数据的大小关系，将大于arr[i]的数据调整到i的位置，并且用此方法继续去调整被调走的那个数据；
2.建堆过程：当调整的过程做好后，建堆也就十分简便了，只需要不断地调用调整函数即可。每次从n/2的位置开始调整，依次往前，知道调整到1位置后结束该过程；
3.排序过程：排序过程就是将前两个过程结合起来。建堆，然后不断地将堆顶数据交换到末尾，并且把堆的长度减1，然后继续调整，直到堆的长度为1时停止；
请结合代码加深对堆排序的过程的理解。
void swap(int&a,int&b)// 交换函数 &为C++用法
{a = a^b;
b = b^a;
a = a^b;
}
void adjust(int*arr,int i,int n)// 调整函数
{int j,t = arr[i];
while(1)
{if(2*i+1<=n)// 左右孩子都有
{ j = arr[2*i]>arr[2*i=1]?2*i:2*i+1;// 找出左右孩子大的一个
if(arr[j]>t)// 比较是否比t大
{ arr[i] = arr[j];
i = j;
}
else // 否则跳出
break;
}
else if(2*i==n)// 只有左孩子 此处的判断条件极为重要！exceedingly crucial!!!
{ if(arr[2*i]>t)
{ arr[i] = arr[2*i];
i *= 2;
}
break;// 只要进入此判断条件下一步必然要跳出
}
}
arr[i] = t;// 将t放在找到的位置
}
void buildHeap(int*arr,int n)// 从n/2处开始向上调整
{int i;
for(i=n/2;i>0;i--)
adjust(arr,i,n);
}
void heapSort(int*arr,int n)// heapSort 排序函数
{int i;
buildHeap(arr,n);// 首先建堆
for(i=n;i>0;i--)
{swap(arr[1],arr[i--]);// 每次交换根结点到最后位置 并length--
adjust(arr,i);
}
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧