shellsort.cpp

数据结构c++-书的一些源代码

#include <iostream.h>
#include "datatype.h"

void ShellSort (datatype a[], int n, int d[], int numOfD)
//用希尔排序法对记录a[0]--a[n-1]排序
//各组内采用直接插入法排序
{
	int i, j, k, m, span;
	datatype temp;

	for(m = 0; m < numOfD; m++)
	{
		span = d[m];
		for(k = 0; k < span; k++)
		{
			for(i = k; i < n-span; i = i+span)
			{
				temp = a[i+span];
				j = i;
				while(j > -1 && temp.key <= a[j].key)
				{
					a[j+span] = a[j];
					j = j-span;
				}
				a[j+span] = temp;
			}
		}
	}
}

void main(void)
{
	datatype test[]={65,34,25,87,12,38,56,46,14,77,92,23};
	int n = 12, d[] = {6, 3, 1}, numOfD = 3;
	ShellSort (test, n, d, numOfD);
	for(int i = 0; i < n; i++)
		cout << test[i].key << "  ";
}