pex13_3.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#pragma hdrstop

#include "random.h"
#include "arrsort.h"
#include "toursort.h"
#include "ticks.h"			// for TickCount

// include the MaxHeap class
#include "maxheap.h"

// sort array A in ascending order
template <class T>
void HeapSort (T A[], int n)
{
   // array A is bound to Heap H
   MaxHeap<T> H(A,n);
   T elt;
   
   // iteration that loads element A[n-1] ... A[1]
   for(int i = n-1;i >= 1;i--)
   {
      // delete largest element from heap and store in A[i]
      elt = H.Delete();
      A[i] = elt;
   }
}

// prints the first 5 and last 5 items in the array
void PrintFirst_Last(int a[], int n)
{
    int i;
    
    for(i=0;i < 5;i++)
        cout << a[i] << "  ";
    cout << ". . .  ";
    for(i= n-5; i < n; i++)
        cout << a[i] << "  ";
    cout << endl;
}

enum SortType {heap,tournament,exchange};

void TimeSort(int *A, int n,
              char *sortName, SortType sort)
{
    long tcount;

    // TickCount is a system dependent function. it returns
    // the number of 1/60 th secs. since system startup.    
    
    cout << "Sorting with " << sortName << ':' << endl;
    
    // start the count then sort array A.  assign to 
    // tcount the elapsed sort time t in 1/60 th secs.
    tcount = TickCount();
    switch(sort)
    {
        case heap:          HeapSort(A,n);
                            break;
        case tournament:    TournamentSort(A,n);
                            break;
        case exchange:      ExchangeSort(A,n);
                            break;
    }
    tcount = TickCount() - tcount;
    
    // print the first 5 and last 5 elements of sorted array
    PrintFirst_Last(A,n);
    
    cout << sortName << " time is " << tcount << endl << endl;
}

void main(void)
{
    // pointers for arrays A, B, and C 
    int  *A, *B, *C;    
    RandomNumber rnd;
    
    // dynamically allocate memory and load arrays
    A = new int [2000];
    B = new int [2000];
    C = new int [2000];
    
    // load the arrays with 2000 identical random numbers 
    for(int i=0;i < 2000;i++)
        A[i] = B[i] = C[i] = rnd.Random(10000);
        
	// time the heap sort and delete dynamic array A
    TimeSort(A,2000,"Heap sort",heap);
    delete [] A;
    
    // repeat process for the tournament sort
    TimeSort(B,2000,"Tournament sort",tournament);
    delete [] B;
  
    // repeat process for the exchange sort
    TimeSort(C,2000,"Exchange sort",exchange);
    delete [] C;
}

/*
 
<Run>

Sorting with Heap sort:
10  19  21  23  25  . . .  9960  9960  9964  9977  9989
Heap sort time is 11

Sorting with Tournament sort:
10  19  21  23  25  . . .  9960  9960  9964  9977  9989
Tournament sort time is 40

Sorting with Exchange sort:
10  19  21  23  25  . . .  9960  9960  9964  9977  9989
Exchange sort time is 557
*/