【C++】测试不同的增量序列下shell排序的时间开销

题目：

编程实现shell排序算法。尝试采用不同的增量序列，测试shell排序的时间开销。

输入可以为正序、逆序或随机序列。

初始化正序数组：

int record[MAXSIZE];

memset(record, 0, MAXSIZE * sizeof(int));

for (int i = 0; i < MAXSIZE; i++) {

         record[i] = i;

}

初始化逆序数组：

int record[MAXSIZE];

memset(record, 0, MAXSIZE * sizeof(int));

for (int i = 0; i < MAXSIZE; i++) {

         record[i] = MAXSIZE-1-i;

}

初始化随机数组：

int record[MAXSIZE];

memset(record, 0, MAXSIZE * sizeof(int));

srand((unsigned)time(NULL));

for (int i = 0; i < MAXSIZE; i++) {

         record[i] = rand()%MAXSIZE;

}

代码示例

//author:Mitchell
//date:5.25
#include<iostream>
#include<windows.h>
using namespace std;

template<class T>
void InsertSort(T Array[], int size, int delta) {
	for (int i = delta; i < size; i++) {
		for (int j = i; j >= delta; j -= delta) {
			if (Array[j] < Array[j - delta]) {
				int x = Array[j];
				Array[j] = Array[j - delta];
				Array[j - delta] = x;
			}
		}
	}
}

template<class T>
void ShellSort1(T Array[], int size) {
	for (int delta = size / 2; delta > 0; delta /= 2) {
		for (int i = 0; i < delta; i++) {
			InsertSort(&Array[i], size - i, delta);//注意传入的是Array[i]的地址
		}
	}
	//对于增量序列中首项不为1的额外添加
	//InsertSort(Array, size, 1);
}

template<class T>
void ShellSort2(T Array[], int size) {
	for (int delta = (size + 1) / 2; delta > 1; delta = (delta + 1) / 2) {
		for (int i = 0; i < delta; i++) {
			InsertSort(&Array[i], size - i, delta);//注意传入的是Array[i]的地址
		}
	}
	InsertSort(Array, size, 1);
}

template<class T>
void ShellSort3(T Array[], int size) {
	for (int delta = size / 3; delta > 3; delta /= 3) {
		for (int i = 0; i < delta; i++) {
			InsertSort(&Array[i], size - i, delta);//注意传入的是Array[i]的地址
		}
	}
	//InsertSort(Array, size, 1);
}

int main() {
		int size;
		cout << "数组大小：";
		cin >> size;
		int* test = new int[size];
		memset(test, 0, size * sizeof(int));
		for (int i = 0; i < size; i++) {
			//初始化正序数组
			//test[i] = i;
			//初始化逆序数组
			//test[i] = size - 1 - i;
			//初始化随机数组
			test[i] = rand() % size;
		}
		/*cout << "排序前：";
		for (int i = 0; i < size; i++) {
			cout << test[i] << " ";
		}*/

		float t1 = GetTickCount64();
		ShellSort1(test, size);
		float t2 = GetTickCount64();
		cout << "增量为{1，2，4，8，16……}的时间开销：" << t2 - t1 << "ms" << endl;

		for (int i = 0; i < size; i++) {
			//初始化随机数组
			test[i] = rand() % size;
		}
		t1 = GetTickCount64();
		ShellSort2(test, size);
		t2 = GetTickCount64();
		cout << "增量为{1，3，7，15，31……}的时间开销：" << t2 - t1 << "ms" << endl;

		for (int i = 0; i < size; i++) {
			//初始化随机数组
			test[i] = rand() % size;
		}
		t1 = GetTickCount64();
		ShellSort3(test, size);
		t2 = GetTickCount64();
		cout << "增量为{1，3，9，27，81……}的时间开销：" << t2 - t1 << "ms" << endl;
		
		/*cout << endl << "排序后：";
		for (int i = 0; i < size; i++) {
			cout << test[i] << " ";
		}*/
}

知识补充

C++获取代码运行时间