基于c/c++的希尔排序与插入排序对比

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/timeb.h>
#include <time.h>

using namespace std;

#define MAXLENGTH 100000

long getSystemTime()
{
	struct timeb tb;
	ftime(&tb);
	return tb.time * 1000 + tb.millitm;

}


//交换函数
void swapData(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}



//打印函数
void PrintArray(int arr[], int length)
{
	for (int i = 0; i < length; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

//冒泡排序改进版本
int flag = 0; //表示没有排序好
void BubbleSortFaster(int arr[], int length)
{
	for (int i = 0; i < length - 1 && flag == 0; i++)
	{
		flag = 1; //认为已经排序好
		for (int j = 0; j < length - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				flag = 0;
				swapData(&arr[j], &arr[j + 1]);
			}
		}
	}

}



//选择排序
void SelectSort(int arr[], int length)
{

	for (int i = 0; i < length; i++)
	{
		int min = i;
		for (int j = i + 1; j < length; j++)
		{
			if (arr[j] < arr[min])
			{
				min = j;
			}
		}

		if (min != i)
		{
			swapData(&arr[min], &arr[i]);
		}

	}

}

//插入排序
void InsertSort(int arr[], int length)
{
	int j;
	for (int i = 1; i < length; i++)
	{
		if (arr[i] < arr[i - 1])
		{
			int temp = arr[i];
			for (j = i - 1; j >= 0 && temp < arr[j]; j--)
			{
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = temp;
		}
	}
}

//希尔排序
//从小到大
void ShellSort(int arr[], int length) 
{
	int increasement = length;
	int i, j, k;
	do
	{
		//确定分组的增量
		increasement = increasement / 3 + 1;

		for (i = 0; i < increasement; i++)
		{
			for (j = i + increasement; j < length; j+=increasement)
			{
				if (arr[j]<arr[j-increasement])
				{
					int temp = arr[j];
					for ( k = j-increasement; k >=0 && temp<arr[k]; k-=increasement)
					{
						arr[k + increasement] = arr[k];
					}

					arr[k + increasement] = temp;
				}
			}
		}

	} while (increasement>1);


}
//从小到大排序
int main()
{
	int arr[MAXLENGTH];
	int arr2[MAXLENGTH];

	srand((unsigned int)time(NULL));
	for (int i = 0; i < MAXLENGTH; i++)
	{
		int numtemp = rand() % MAXLENGTH;
		arr[i] = numtemp;
		arr2[i] = numtemp;
	}

	//PrintArray(arr, MAXLENGTH);
	//InsertSort(arr, MAXLENGTH);
	long tshell_start = getSystemTime();
	ShellSort(arr, MAXLENGTH);
	long tshell_end = getSystemTime();
	cout << "希尔排序" << MAXLENGTH << "个元素所需时间：" << (tshell_end - tshell_start)<<"\n";
	//PrintArray(arr, MAXLENGTH);


	long tinsert_start = getSystemTime();
	InsertSort(arr2, MAXLENGTH);
	long tinsert_end = getSystemTime();
	cout << "插入排序" << MAXLENGTH << "个元素所需时间：" << (tinsert_end - tinsert_start)<<"\n";


	return 0;
}