#include <stdio.h>
#include <time.h>

#define N 100000

/*库比较函数:qsort(int *base,int n,int struct_size,int (*compare)(const 

void *,const void *))中的比较函数*/
int compare(const void *first, const void *second)
{
	if (*(int *)first > *(int *)second)/*当第一个数比第二个数大的时候，

就进行排序，排序的结果是从小到大*/
		return 1;
	else
		return -1;
}


/*希尔排序*/
void ShellInsert(int *a, int n, int d)
{
	int i, j, temp;
	for (i = d; i < n; ++i){
		j = i - d;
		temp = a[i];
		while (j >= 0 && temp < a[j]){
			a[j + d] = a[j];
			j -= d;
		}
		a[j + d] = temp;
	}
}

void ShellSort(int *a, int n)
{
	int d = n / 2;
	while (d >= 1){
		ShellInsert(a,n,d);
		d /= 2;
	}
}

/*快速排序*/

void QuickSort(int *a,int low,int high)
{
	int l = low, h = high, temp;
	if (l < h){
		temp = a[low];
		while (l != h){
			while (l<h&&a[h]>temp)
				--h;
			if (l < h){
				a[l] = a[h];
				++l;
			}
			while (l < h&&a[l] < temp)
				++l;
			if (l < h){
				a[h] = a[l];
				--h;
			}
		}
		a[l] = temp;
		QuickSort(a,low,l-1);
		QuickSort(a,h+1,high);
	}
}

/*堆排序*/

void HeapInsert(int *a, int low, int high)
{
	int i = low, j = low * 2, temp = a[i];
	while (j <= high){
		if (j < high && a[j] < a[j + 1])
			++j;
		if (temp < a[j]){
			a[i] = a[j];
			i = j;
			j *= 2;
		}
		else
			break;
	}
	a[i] = temp;
}

void HeapSort(int *a, int n)
{
	int i, temp;
	for (i = n / 2; i >= 0; --i)
		HeapInsert(a,i,n-1);
	for (i = n - 1; i >= 1; --i){
		temp = a[i];
		a[i] = a[0];
		a[0] = temp;
		HeapInsert(a,0,i-1);
	}
}

/*折半排序*/

void BinarySort(int *a,int n)
{
	int i, j, low, middle, high, temp;
	for (i = 1; i < n; ++i){
		low = 0;
		high = i - 1;
		temp = a[i];
		while (low <= high){
			middle = (low + high) / 2;
			if (temp < a[middle])
				high = middle - 1;
			else
				low = middle + 1;
		}
		for (j = i - 1; j > high; --j)
			a[j + 1] = a[j];
		a[low] = temp;
	}
}

void initArray(int *a, int n)
{
	srand(time(NULL));
	int i;
	for (i = 0; i < n; ++i)
		a[i] = rand() % 100;
}

void print(int *a,int n)
{
	int i;
	for (i = 0; i < n; ++i){
		printf("%d ", a[i]);
		if (i && i % 20 == 0)
			printf("\n");
	}
	printf("\n");
}

int main()
{
	int a[N];
	double start, finish;

	//initArray(a, N);
	//printf("排序前:\n");
	//print(a, N);/*排序前*/

	/*计算系统库函数排序消耗的时间*/
	initArray(a, N);
	start = clock();
	qsort(a, N, sizeof(int), compare);
	finish = clock();
	printf("System library sort cost %.3fSeconds\n", (finish - start) / 

1000);
	/*计算折半插入排序消耗的时间*/
	initArray(a, N);
	start = clock();
	BinarySort(a,N);
	finish = clock();
	printf("Binary sort cost %.3fSeconds\n", (finish - start) / 1000);
	/*计算堆排序消耗的时间*/
	initArray(a, N);
	start = clock();
	HeapSort(a, N);
	finish = clock();
	printf("Heap sort cost %.3fSeconds\n", (finish - start) / 1000);
	/*计算希尔排序消耗的时间*/
	initArray(a, N);
	start = clock();
	ShellSort(a, N);
	finish = clock();
	printf("Shell sort cost %.3fSeconds\n", (finish - start) / 1000);
	/*计算快速排序消耗的时间*/
	initArray(a, N);
	start = clock();
	QuickSort(a, 0, N - 1);
	finish = clock();
	printf("Quick sort cost %.3fSeconds\n", (finish - start) / 1000);
	
	//printf("排序后:\n");
	//print(a, N);
	return 0;
}