pex14_5.cpp

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

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

#include "random.h"

// sort array A of n items using the Shell sort
template <class T>
void ShellSort(T A[], int n)
{	   
	int	i,j,k;
	T target;

	// select k from the increment sequence
	// ..., 1093, 364, 121, 40, 13, 4, 1. it can
	// be shown that the Shell sort does well with
	// this increment sequence. for 100 data values,
	// k will be 40
	for(k=1;k <= n/2;k = 3*k+1);
	
	for (;k >= 1;k /= 3)
	{
		// sort the sublists. locate A[k] in the sublist
		// A[0],A[k], locate A[k+1] in the sublist A[1],A[k+1],
		// locate A[k+2] in the sublist A[2],A[k+2], etc.
		// when we process i=n-1, all sublists will be sorted
		for(i = k; i < n; i++) 
		{
			target = A[i];
			// move the the sublist value before A[j]
			j = i - k;
			// insert target in its sublist. same code as for
			// the insertion sort, except we are using decrement
			// k
			while (j >= 0 && target < A[j]) 
			{
				A[j + k] = A[j];
				j = j - k;
			}  
			A[j + k] = target;
		}
	}
}

// print integer array a, 10 integers
// to a line
void PrintArray(int a[], int n)
{
	for (int i=0;i < n;i++)
	{
		cout << setw(6) << a[i];
		if ((i+1) % 10 == 0)
			cout << endl;
	}
	// if n is not a multiple of 10, generate
	// a final newline
	if (n % 10 != 0)
		cout << endl;
}

void main()
{
	int i;
	RandomNumber rnd;
	int *a;
	
	// allocate an array of 100 integers
	a = new int [100];
	// initalize a with random integers in the range 0..999
	for (i = 0; i < 100; i++)
		a[i] = rnd.Random(1000);
	cout << "Original array:" << endl;
	PrintArray(a,100);
	cout << endl;
	
	// sort a using the Shell sort and print it
	ShellSort(a,100);
	cout << "Sorted array:" << endl;
	PrintArray(a,100);
}

/*
<Run>

Original array:
   124   331   479   855   656   217   722   580    50   374
   493   633   876   494     5   140   859   771   906    94
   724   623   655   748   518   399   398   338    35   557
   426   655   830   677   985   679   660   474   111   819
   922   640   364   623   658   800   232   601   924   635
   404   309   478   327   561   489    92   682   772   452
   646   818   680   724   685   888   298   428   675   160
   787   778   141   386   799   122    97   157   520   773
   127   784   474   118   649   505   716   922   842   617
   387   733   576   838   366   388   873   902    66   711

Sorted array:
     5    35    50    66    92    94    97   111   118   122
   124   127   140   141   157   160   217   232   298   309
   327   331   338   364   366   374   386   387   388   398
   399   404   426   428   452   474   474   478   479   489
   493   494   505   518   520   557   561   576   580   601
   617   623   623   633   635   640   646   649   655   655
   656   658   660   675   677   679   680   682   685   711
   716   722   724   724   733   748   771   772   773   778
   784   787   799   800   818   819   830   838   842   855
   859   873   876   888   902   906   922   922   924   985
*/