本文共 1072 字，大约阅读时间需要 3 分钟。

堆排序 -

堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）；每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。

时间复杂度：O(NlogN) 　　稳定性：不稳定

/*堆排序*///根节点元素自顶向下移动到合适的位置以构成最大堆void downToMaxHeap(vector
   
     &arr, int bgn, int end){
       int child;    int parent = bgn;    /*假根节点向下移动至合适的位置 --整个堆排序的核心代码块*/    while ((child = parent * 2 + 1) < end)    {
           if ((child < end - 1) && (arr[child] < arr[child + 1]))            ++child;    //右孩子节点        if (arr[child] > arr[parent])            mySwap(&arr[child], &arr[parent]);        else            break;        parent = child;    }}//将数组构造为最大堆void buildMaxHeap(vector
    
      &arr, int bgn, int end){
       if (bgn >= end - 1)        return;    int parent = end / 2 - 1;    while (parent >= 0)    {
           downToMaxHeap(arr, parent, end);        --parent;    }}//堆排序void heapSort(vector
     
       &arr, int bgn, int end){
       //构造最大堆    buildMaxHeap(arr, bgn, end);    while (end > 1)    {
           mySwap(&arr[0], &arr[--end]);        downToMaxHeap(arr, 0, end);    }}
     
    
   

转载地址：http://vimqf.baihongyu.com/