C/C++实现八大排序算法汇总

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。如图：

再讨论对n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）                     

 算法的实现：

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

//调整为一个堆
void Heap_Adjust(int *list,int s,int m)
{
 int temp = list[s];
 for(int j=2*s+1;j<=m;j = 2*j+1)
 {
 if(list[j]<list[j+1]&&j<m)
 {
  j++;
 }
 if(temp>list[j])
  break;
 list[s] = list[j];
 s = j;
 }
 list[s] = temp;
}

//堆排序
void Heap_Sort(int *list,int len)
{
 //创建一个大顶堆
 for(int s = len/2-1;s>=0;s--)
 {
 Heap_Adjust(list,s,len-1);
 }

 //排序
 for(int i = len-1;i >= 1;i--)
 {
 swap(list[0],list[i]);
 Heap_Adjust(list,0,i-1);
 }
}