main.cpp

实现数据结构的堆排序

#include <cstdlib>
#include <iostream>
#include <cmath>
#include <iomanip>
#include "Timer.h"
#include <stdlib.h>
#include <time.h>

using namespace std;

int counter1=0,counter2=0;

/********************************************
void shiftdown(Ritr a, int i, int n):
Williams shift down

precondition:
a[i+1..n] is already a heap

postcondition:
a[i..n] is a heap
********************************************/
template<typename Ritr>
void
shift_down(Ritr a, int i, int n)
{ //Williams
  for(int bc = 2*i; bc <= n; bc = 2*i)
  {
    if(bc < n && a[bc] < a[bc+1])
    {
      bc = bc + 1;
      counter1++;
    }
    if(a[i] < a[bc])
    {
      std::swap(a[i], a[bc]);
      i = bc;
      counter2++;
    }
    else 
      break;
  }
}//~shift_down()

//a[0..n)排序
template<typename Ritr>
void heap_sort(Ritr a, int n)
{
  --a;
  // make a[1, n] heap
  int i;
  for(i = n/2; i > 0; --i)
    shift_down(a, i, n);

  for(i = n; i > 1; --i)
  {
    std::swap(a[1], a[i]);
    counter2++;
    shift_down(a, 1, i - 1);
  }
}//~heap_sort(T*a, int n)


int main()
{
    int num[10000];
    
    srand(time(NULL));
    
    for(int i=0;i<=9999;i++)
        num[i]=1+rand()%1000;
    
    Timer timer;
    
    timer.start();
    
    heap_sort(num,10000);
    
    timer.stop();
    double clock=timer.seconds();
    timer.reset();
    
    for(int i=0;i<=9999;i++)
        cout<<setw(6)<<num[i];
        
    cout<<endl<<endl;
    
    cout<<"程序运行时间为："<<clock<<'s'<<endl;
    cout<<"键值比较次数为："<<counter1<<endl;
    cout<<"键值交换次数为："<<counter2<<endl; 
    
    system("pause");
    return 0;
}