#include <iostream>
#include <cstdlib>
#include <ctime>
#include <windows.h>
#define N 100000
using namespace std;

template<class T>
void Swap(T &x,T &y)
{
	T temp;
	temp = x;
	x = y;
	y = temp;
}

template<class T>
void SelectSort(T A[],int n)
{
	int s;
	for (int i = 0 ; i < n - 1 ; i++)
	{
		s = i;
		for (int j = i + 1 ; j < n ; j++)
		{
			if (A[j] < A[s])
			{
				s = j;
			}
			Swap(A[i],A[s]);
		}
	}
}

template<class T>
void InsertSort(T A[],int n)
{
	InsertSort(A,0,n);
}

template<class T>
void InsertSort(T A[],int n1,int n2)
{
	for (int i = n1 + 1 ; i < n2 ; i++)
	{
		int j = i;
		T temp = A[i];
		while (j > 0 && temp < A[j - 1])
		{
			A[j] = A[j - 1];
			j--;
		}
		A[j] = temp;
	}
}

template<class T>
void BubbleSort(T A[],int n)
{
	int i,j,last;
	i = n - 1;
	while (i > 0)
	{
		last = 0;
		for (j = 0 ; j < i ; j++)
		{
			if (A[j + 1] < A[j])
			{
				Swap(A[j],A[j + 1]);
				last = j;
			}
		}
		i = last;
	}
}

template<class T>
void QuickSort(T A[],int n)
{
	QSort(A,0,n - 1);
}

template<class T>
void QSort(T A[],int left,int right)
{
	int i,j;
	if (left < right)
	{
		i = left;
		j = right + 1;
		do 
		{
			do 
			{
				i++;
			} while(A[i] < A[left]);
			do 
			{
				j--;
			} while(A[j] > A[left]);
			if (i < j)
			{
				Swap(A[i],A[j]);
			}
		} while(i < j);
		Swap(A[left],A[j]);
		QSort(A,left,j - 1);
		QSort(A,j + 1,right);
	}
}

template<class T>
void QuickSort1(T A[],int n)
{
	QSort1(A,0,n - 1);
}

template<class T>
void QSort1(T A[],int left,int right)
{
	int i,j;
	if (right - left > 10)
	{
		i = left;
		j = right + 1;
		do 
		{
			do 
			{
				i++;
			} while(A[i] < A[left]);
			do 
			{
				j--;
			} while(A[j] > A[left]);
			if (i < j)
			{
				Swap(A[i],A[j]);
			}
		} while(i < j);
		Swap(A[left],A[j]);
		QSort(A,left,j - 1);
		QSort(A,j + 1,right);
	}
	else
		InsertSort(A,left,right);
}

template<class T>
void Merge(T A[],int i1,int j1,int i2,int j2)
{
	T *Temp = new T[j2 - i1 + 1];
	int i = i1,j = i2,k = 0;
	while (i <= j1 && j <= j2)
	{
		if (A[i] <= A[j])
		{
			Temp[k++] = A[i++];
		}
		else
			Temp[k++] = A[j++];
	}
	while (i <= j1)
	{
		Temp[k++] = A[i++];
	}
	while (j <= j2)
	{
		Temp[k++] = A[j++];
	}
	for (i = 0 ; i < k ; i++)
	{
		A[i1++] = Temp[i];
	}
	delete []Temp;
}

template<class T>
void MergeSort(T A[],int n)
{
	int i1,i2,j1,j2;
	int size = 1;
	while(size < n)
	{
		i1 = 0;
		while(i1 + size < n)
		{
			i2 = i1 + size;
			j1 = i2 - 1;
			if(i2 + size - 1 > n - 1)
				j2 = n - 1;
			else
				j2 = i2 + size - 1;
			Merge(A,i1,j1,i2,j2);
			i1 = j2 + 1;
		}
		size *= 2;
	}
}
template<class T>
void AdjustDown(T A[],int r,int j)
{
	int child = 2 * r + 1;
	T temp = A[r];
	while (child <= j)
	{
		if (child < j && A[child] < A[child + 1])
		{
			child++;
		}
		if (temp >= A[child])
		{
			break;
		}
		A[(child - 1) / 2] = A[child];
		child = 2 * child + 1;
	}
	A[(child - 1) / 2] = temp;
}

template<class T>
void HeapSort(T A[],int n)
{
	for (int i = (n - 2) / 2 ; i > -1 ; i--)
	{
		AdjustDown(A,i,n - 1);
	}
	for (i = n - 1; i > 0 ; i--)
	{
		Swap(A[0],A[i]);
		AdjustDown(A,0,i - 1);
	}
}

void ProducRand(int A[],int n)
{
	for (int i = 0 ; i < n ; i++)
	{
		A[i] = rand();
	}
}


void show(int num[],int n)
{
	for (int i = 0 ; i < n ; i++)
	{
		cout<<num[i]<<"   ";
	}
	cout<<endl;
}

int main()
{
	int now,next;
	int A[N];
	srand( (unsigned)time( NULL ) );
/*
 	ProducRand(A,N);
 	now = GetTickCount();
 	SelectSort(A,N);
 	next = GetTickCount();
	cout<<"選擇排序："<<next - now<<endl;
 	
 	ProducRand(A,N);
 	now = GetTickCount();
 	InsertSort(A,N);
 	next = GetTickCount();
	cout<<"插入排序："<<next - now<<endl;
 	
 	ProducRand(A,N);
 	now = GetTickCount();
 	BubbleSort(A,N);
 	next = GetTickCount();
	cout<<"冒泡排序："<<next - now<<endl;
	*/
	ProducRand(A,N);
	now = GetTickCount();
	QuickSort(A,N);
	next = GetTickCount();
	cout<<"快排排序："<<next - now<<endl;
	
 	now = GetTickCount();
 	ProducRand(A,N);
 	MergeSort(A,N);
 	next = GetTickCount();
 	cout<<"二路合并排序："<<next - now<<endl;

	ProducRand(A,N);
 	now = GetTickCount();
 	QuickSort1(A,N);
 	next = GetTickCount();
	cout<<"改進快排排序："<<next - now<<endl;
	
	ProducRand(A,N);
	now = GetTickCount();
	HeapSort(A,N);
	next = GetTickCount();
	cout<<"堆排序排序："<<next - now<<endl;
	return 0;
}