堆排序(heap sort) 详解 及 代码(C++)

?

堆排序包含两个步骤:

第一步: 是建立大顶堆(从大到小排序)或小顶堆(从小到大排序), 从下往上建立; 如建堆时, s是从大到小;

第二步: 是依次交换堆顶和堆底, 并把交换后的堆底输出, 只排列剩余的堆, 从上往下建立; 如构造时, s始终是1;

?

堆排序(Heap Sort)的时间复杂度是O(nlogn), 最坏情况下也是如此.

而快速排序(Quick Sort), 若初始记录序列有序, 快速排序将退化为起泡排序(Bubble Sort), 时间复杂度是O(n^2).

这是堆排序比快速排序的优点.

?

代码:

?

/*
 * main.cpp
 *
 *  Created on: 2014.6.12
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   
#include 
   
     #include 
    
      using namespace std; void HeapAdjust (std::vector
     
      & L, int s, int num) { int temp = L[s-1]; for (int j=2*s; j<=num; j*=2) { if (j
      
        L[j]) //选取最小的结点位置 ++j; if (temp < L[j-1]) //不用交换 break; L[s-1] = L[j-1]; //交换值 s = j; //继续查找 } L[s-1] = temp; } void HeapSort (std::vector
       
        & L) { int num = L.size(); for (int i=num/2; i>0; --i) { HeapAdjust(L, i, num); //从第二层开始建堆 } for (int i=num; i>1; --i) { std::swap(L[0], L[i-1]); HeapAdjust(L, 1, i-1); //从顶点开始建堆, 忽略最后一个 } return; } int main (void) { std::vector
        
          L = {49, 38, 65, 97, 76, 13, 27, 49}; HeapSort(L); for (std::size_t i=0; i
         
          
?
          
输出:
          
?
          
97 76 65 49 49 38 27 13 
 
          
 
          
 
          
?
 
          
?
 
          
 
          
?