堆排序是很重要的排序算法，应该仅次于快速排序吧，但是它却一般不用来排序。不过堆排序给我印象最深刻的，还是消除堆排序的递归特别难。

#include <iostream>

#include <stdlib.h>

#include <algorithm>

#include <set>

#define LEN 20

//Heap sort

void makeHeap(int *array, int p, int n)
{
     int r = 2 * p + 2;
     int l = 2 * p + 1;
     int largest = p;
     if (l < n)
         largest = (array[p] > array[l])?p:l;
     if (r < n)
         largest = (array[largest] > array[r])?largest:r;
     if (largest != p)
     {
         std::swap(array[largest], array[p]);
         makeHeap(array, largest, n);
     }
     
}

void makeHeap2(int *array, int p, int n)
{
     int largest = p;
     do
     {
         p = largest;
         int r = 2 * p + 2;
         int l = 2 * p + 1;
         if (l < n)
             largest = (array[p] > array[l])?p:l;
         if (r < n)
             largest = (array[largest] > array[r])?largest:r;
         if (largest != p)
             std::swap(array[largest], array[p]);
     }while(largest != p);
     
}

void BuildHeap(int *array, int n)
{
     for(int i = (n + 1) / 2; i >= 0; --i)
         makeHeap2(array, i, n);
}

void sort_heap(int *array, int n)
{
     BuildHeap(array, n);
     
     for(int j = n - 1; j > 0; --j)
     {
         std::swap(array[0], array[j]);
         makeHeap2(array, 0, j);
     }
}

int main()
{
     int array[LEN];
     for(int i = 0; i < LEN; ++i)
         array[i] = rand() % LEN;
     std::cout << "Before sort:\t";
     for(int i = 0; i < LEN; ++i)
         std::cout << array[i] << " ";
     std::cout << "\n";
     sort_heap(array, LEN);
     std::cout << "After sort:\t";
     for(int i = 0; i < LEN; ++i)
         std::cout << array[i] << " ";
     std::cout << "\n";
}

[原文在百度空间已经关闭]