pex14_2.cpp

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

#include <iostream.h>
#include <iomanip.h>
#pragma hdrstop

#include "arrsort.h"
#include "random.h"
#include "ticks.h"

// merge sorted sublists A[low]..A[middle-1], A[middle]..A[high]
// into array B
void Merge(int A[], int low, int middle, int high, int B[])
{
    int left = low, right = middle, i = 0;
    
    // copy until we hit the end of one or both sublists
    while (left <= middle-1 && right <= high)
    {
        // if left sublist data value smaller or equal, assign it to
        // B. advance to next left sublist element
        if(A[left] <= A[right])
        {
            B[i] = A[left];
            left++;
        }
        // assign data from right sublist and advance right
        else
        {
            B[i] = A[right];
            right++;
        }
        i++;	// advance output index
    }

    // if one of the sublists is not complete, copy it to B
    if (left <= middle-1)
        while(left <= middle-1)
        	B[i++] = A[left++];
    else if (right <= high)
        while(right <= high)
        	B[i++] = A[right++];
}

// 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;
}

void main(void)
{
	int *a, *b, n;
	int mid;
	long elapsedTime;
	RandomNumber rnd;
	
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(1);
	
	// create two dynamic arrays of 20000 entries
	n = 20000;
	a = new int [n];
	b = new int [n];
	
	// initialize a and b with the same random numbers
	// in the range 0..32767.
	for(int i=0;i < n;i++)
		a[i] = b[i] = rnd.Random(32768L);

	// sort the array b using the ordinary selection sort
	elapsedTime = TickCount();
	SelectionSort(b,n);
	elapsedTime = TickCount() - elapsedTime;
	PrintFirst_Last(b,n);
	cout << "Ordinary selction sort took " << elapsedTime/60.0
		 << " seconds" << endl;

	// sort each half interval of a with the selection
	// sort and then merge the two halves into b. time the
	// process
	elapsedTime = TickCount();
	mid = n/2;
	// sort the elements a[0] .. a[mid-1]
	SelectionSort(a,mid);
	// sort the elements a[mid] .. a[n-1]
	SelectionSort(&a[mid],n-mid);
	// merge the two sorted sublists
	Merge(a,0,mid,n-1,b);
	elapsedTime = TickCount() - elapsedTime;
	PrintFirst_Last(b,n);
	cout << "Sort with merge took " << elapsedTime/60.0
		 << " seconds" << endl;
	// delete the dynamic memory for the two arrays
	delete [] a;
	delete [] b;
}

/*
<Run>

1  1  2  4  6  . . .  32754  32755  32755  32757  32760  
Ordinary selction sort took 50.1 seconds
1  1  2  4  6  . . .  32754  32755  32755  32757  32760  
Sort with merge took 24.8 seconds
*/