#include <stdio.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <time.h>

//#define		print
using namespace std;


long size;
/////////////////////////////////插入排序
void insert_sort(long a[]){
	long i,j,temp;
	for(j = 1;j<size;j++)
	{

	   temp = a[j];
	   i = j-1;
	   while(i>=0&&a[i]>temp)
	   {
		   a[i+1] = a[i];
		   i--;
	   }
	   a[i+1] = temp;

   }
}

/////////////////////////////////////希爾排序//分段插入排序
void shell_pass(long a[],int d){
	int i,j;
	int temp;
	for(i = d;i<size;i++){
		if(a[i]<a[i-d])
		{
			temp = a[i];
			j = i - d;
			while(j>=0&&temp<a[j])
			{
				a[j+d] = a[j];
				j = j-d;
			}
			a[j+d] = temp;
		}
	}
}

void shellsort(long a[],int d[])
{
	int i = 0;
	int increment;
	while(i < 3)
	{
		increment = d[i];
		i++;
		shell_pass(a,increment);
	}
}


///////////////////////////////合并排序
void merge(long a[],long p,long q,long r){
	long i;
	long j;
	long k;
	long n1 = q-p+1;
	long n2 = r-q;
	long *L =new long[n1+1];
	long *R =new long[n2+1];

	for(i = 0;i<n1;i++)
		L[i] = a[p+i];
	for(j = 0;j<n2;j++)
		R[j] = a[q+j+1];

	//設(shè)定監(jiān)視哨
	L[n1] = R[n2] = 2147483647;

	//合并、排序
	i = j = 0;
	for(k = p;k<=r;k++)
	{
		if(L[i]<=R[j]){
			a[k] = L[i];
			i++;
		}
		else{
			a[k] = R[j];
			j++;
		}
	}
}
void merge_sort(long a[],long p,long r){
	long q = 0;
	if(p<r)
	{
		q = (p+r)/2;
		merge_sort(a,p,q);
		merge_sort(a,q+1,r);
		merge(a,p,q,r);
	}
}


//////////////////////////////////堆排序
void max_heapify(long a[],long i)
{
	long l,r,largest,temp;
	l = 2*i +1;
	r = 2*i +2;
	if(l<size&&a[l]>a[i])
		largest = l;
	else 
		largest = i;
	if(r<size&&a[r]>a[largest])
		largest = r;
	if(largest!=i){
		temp = a[i];
		a[i] = a[largest];
		a[largest] = temp;
		max_heapify(a,largest);
	}
}

void build_max_heap(long a[]){
	long i;
	for(i = size/2;i>=0;i--)
		max_heapify(a,i);
}

void heapsort(long a[]){
	long i,temp;
	build_max_heap(a);
	for(i = size-1;i>0;i--)
	{
		temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		size--;
		max_heapify(a,0);
	}
}



//////////////////////////////快速排序
long partition(long a[],long p,long r){
	long j,temp;
	long x = a[r];
	long i = p-1;
	for(j = p;j<r;j++)
		if(a[j]<=x)
		{
			i++;
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		else;
		temp = a[i+1];
		a[i+1] = a[r];
		a[r] = temp;
		 return(i+1);
}

void quicksort(long a[],long p, long r)
{
	long q;
	if(p<r)
	{
		q = partition(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}



////////////////////////////////////


void main()
 {
   int m;
   printf("請輸入大小：（16的指數(shù)）\n");
   scanf("%d",&m);
   size = pow(16,m);
   long constsize;
   constsize = size;
   long *a = new long[size];
   long *b = new long[size];
   long *c = new long[size];
   long *e = new long[size];
   long *f = new long[size];

   long i;
   int d[] = {7,3,1};
   time_t t1,t2;

   srand( (unsigned)time( NULL ) );
//   cout<<"排序前:\n";
   for(i =0;i<constsize;i++){
		a[i] =b[i] = c[i] = f[i] = e[i] = (long)(rand()+90) * (2147483647/40000);
//		cout<<a[i]<<"\t";			//////////////////
   }


   t1 = clock();
   insert_sort(a);
   t2 = clock();
#ifdef print
   cout<<"\n插入排序后:\n";			/////////////////

   for(i =0;i<constsize;i++){
		out<<a[i]<<"\t";
		cout<<a[i]<<"\t";				//////////////////
   }
#endif 

   cout<<"\n插入排序耗時："<<t2-t1<<"ms"<<"\n";

   t1 = clock();
   shellsort(b,d);
   t2 = clock();

#ifdef print
   cout<<"\n希爾排序后:\n";			//////////////////////

   for(i =0;i<constsize;i++){
		out<<b[i]<<"\t";
		cout<<b[i]<<"\t";			///////////////////////
   }
#endif

   cout<<"\n希爾排序耗時："<<t2-t1<<"ms"<<"\n";

   t1 = clock();
   merge_sort(c,0,size-1);
   t2 = clock();

#ifdef print
   cout<<"\n合并排序后:\n";
   for(i =0;i<constsize;i++){
		cout<<c[i]<<"\t";			////////////////////
   }
#endif

   cout<<"\n合并排序耗時："<<t2-t1<<"ms"<<"\n";

   t1 = clock();
   heapsort(e);
   t2 = clock();

#ifdef print
   cout<<"\n堆排序后:\n";			/////////////////////
   for(i =0;i<constsize;i++){
		cout<<e[i]<<"\t";			//////////////////////
   }
#endif

   cout<<"\n堆排序耗時："<<t2-t1<<"ms"<<"\n";

   t1 = clock();
   quicksort(f,0,constsize-1);
   t2 = clock();

#ifdef print
   cout<<"\n快速排序后:\n";			/////////////////
   for(i =0;i<constsize;i++){
		cout<<f[i]<<"\t";				////////////////////
   }
#endif

   cout<<"\n快速排序耗時："<<t2-t1<<"ms"<<"\n";
}