基于C++的归并排序、快速排序、希尔排序对比测试

#include <iostream>
#include <time.h>
#include <sys/timeb.h>

using namespace std;

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

}

//创建数组
int* CreateArray() 
{
	srand((unsigned int)time(NULL));
	int* arr = (int*)malloc(sizeof(int) * MAX);
	for (int i = 0; i < MAX; i++)
	{
		if (arr)
		{
			arr[i] = rand() % MAX;
		}
		
	}

	return arr;
}

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



//合并算法 从小到大
void Merge(int arr[], int start, int end, int mid, int* temp)
{
	int i_start = start;
	int i_end = mid;
	int j_start = mid + 1;
	int j_end = end;

	//表示辅助空间有多少个元素
	int length = 0;

	//合并两个有序序列
	while (i_start <= i_end && j_start <= j_end)
	{

		if (arr[i_start] < arr[j_start])
		{
			temp[length] = arr[i_start];
			length++;
			i_start++;
		}
		else
		{
			temp[length] = arr[j_start];
			j_start++;
			length++;
		}
	}

	//i这个序列
	while (i_start <= i_end)
	{
		temp[length] = arr[i_start];
		i_start++;
		length++;
	}

	//j序列
	while (j_start <= j_end)
	{
		temp[length] = arr[j_start];
		length++;
		j_start++;
	}

	//辅助空间的数据覆盖到原空间
	for (int i = 0; i < length; i++)
	{
		arr[start + i] = temp[i];
	}

}


//归并排序
void MergeSort(int arr[],int start,int end,int* temp)
{
	if (start>=end)
	{
		return;
	}
	int mid = (start + end) / 2;

	//分组
	//左半边
	MergeSort(arr, start, mid, temp);
	//右半边
	MergeSort(arr, mid + 1, end, temp);

	//合并
	Merge(arr, start, end,mid,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);


}


//快速排序 从小到大
void QuickSort(int arr[], int start, int end)
{
	int i = start;
	int j = end;
	int temp = arr[start]; //基准数

	if (i < j)
	{
		while (i < j)
		{

			//从右向左找比基准数小的数字
			while (i < j && arr[j] >= temp)
			{
				j--;
			}

			//填坑
			if (i < j)
			{
				arr[i] = arr[j];
				i++;
			}

			//从左向右找比基准数大的数字

			while (i < j && arr[i] < temp)
			{
				i++;
			}
			//填坑
			if (i < j)
			{
				arr[j] = arr[i];
				j--;
			}

		}

		//把基准数放到i的位置
		arr[i] = temp;
		//对左半部分进行快速排序
		QuickSort(arr, start, i - 1);
		//对右半边进行快速排序
		QuickSort(arr, i + 1, end);

	}
}


int main(void) 
{
	int* myArr = CreateArray();
	//PrintArray(myArr, MAX);
	//辅助空间
	int* temp = (int*)malloc(sizeof(int) * MAX);
	long t_start = getSystemTime();
	//QuickSort(myArr, 0, MAX - 1);
	MergeSort(myArr, 0, MAX - 1,temp);
	//ShellSort(myArr, MAX);
	long t_end = getSystemTime();
	cout << "合并排序" << MAX << "个元素所需时间：" << (t_end - t_start);
	//PrintArray(myArr, MAX);
	//释放空间
	free(temp);
	free(myArr);
	return 0;
}