算法导论 习题6.2-5 用迭代法实现堆排序

#include <iostream>using namespace std;

void swap(int array[] , int i , int j){    array[i] = array[i]+array[j];    array[j] = array[i]-array[j];    array[i] = array[i]-array[j];}void MaxHeapify(int array[] , int i , int hSize){    int l = 2*i;    int r = 2*i+1;    int largest;    while(l <= hSize)    {        if(array[l] > array[i])        {            largest = l;        }        else        {            largest = i;        }        if(r<=hSize && array[r]>array[largest])       //It's r<=hSize other than r<hSize.        {            largest = r;        }        if(largest != i)        {            swap(array , i ,largest);            i = largest;            l = 2*i;            r = 2*i+1;        }        else        {            break;        }    }}

void BuildMaxHeap(int array[] , int hSize){    for(int i=hSize/2 ; i>=1 ; i--)    {        MaxHeapify(array , i , hSize);    }}

void HeapSort(int array[] , int length){    int hSize = length;    BuildMaxHeap(array , hSize);    for(int i=length ; i>=2 ; i--)    {        swap(array , 1 , i);        hSize--;        MaxHeapify(array , 1 , hSize);    }}int main(){    int a[99];    for(int i=1 ; i<99 ; i++)    {        a[i] = rand()%100;    }    HeapSort(a,99);    for(int i=1 ; i<99 ; i++)    {        cout << a[i] << ' ';    }    return 0;}

 

本文来自博客，转载请标明出处：http://blog.csdn.net/rockerman_shane/archive/2011/02/15/6185506.aspx