#include<iostream>
using namespace std;

//show array
void show(int *ar, int len)
{
	for(int i=0; i<len; ++i)
	{
		cout<<ar[i]<<" ";
	}
	cout<<endl;
}
//bubbleSort
//冒泡排序是一种稳定的排序算法
//最好时间复杂度为O(n)平均时间复杂度为O(n^2)最坏时间复杂度为O(n^2)
//空间复杂度为O(1)
void bubbleSort(int *ar, int len)
{
	bool flag = true;//使用标记能够是有序序列排序时间复杂度为O(n)
	for(int i=0; i<len-1&&flag; ++i)
	{
		for(int j=0; j<len-1-i; ++j)
		{
			flag = false;
			if(ar[j] > ar[j+1]) 
			{
				ar[j] ^= ar[j+1];
				ar[j+1] ^= ar[j];
				ar[j] ^= ar[j+1];
				flag = true;
			}
		}
	}
}

//selectSort
//直接选择排序不稳定 最好最坏平均时间复杂度都是O(n^2) 空间复杂度O(1) 
void selectSort(int *ar, int len)
{
	for(int i=0; i<len-1; ++i)
	{
		//如果第i个元素最小,以此类推
		int min = i;
		for(int j=i+1; j<len; ++j)
		{
			if(ar[j] < ar[min])
			{
				min = j;
			}
		}

		//如果第i个不是最小,把最小的交换到第一个 以此类推
		if(i != min)
		{
			ar[i] ^= ar[min];
			ar[min] ^= ar[i];
			ar[i] ^= ar[min];
		}
	}
}

//insertSort 
//直接插入排序为稳定排序
//最好时间复杂度O(n) 最坏时间复杂度O(n^2) 平均时间复杂度O(n^2)
//直接插入排序的特点是待排序数组越有序速度越快
//空间复杂度为O(1)
void insertSort(int *ar, int len)
{
	for(int i=1; i<len; ++i)
	{
		int temp = ar[i];

		//从后向前比較(有序数组能够保证时间复杂度为O(n)) 在合适的位置插入 
		int j = i-1;
		for(j; j>=0; --j)
		{
			if(ar[j] > temp)
			{
				ar[j+1] = ar[j];
			}
			else
			{
				break;
			}
		}

		ar[j+1] = temp;
	}
}

//shellSort
void shell(int *ar, int len, int size)
{
	for(int i=size; i<len; ++i)
	{
		int temp = ar[i];
		int j = i-size;
		for(j; j>=0; j-=size)
		{
			if(ar[j] > temp)
			{
				ar[j+size] = ar[j];
			}
			else
			{
				break;
			}
		}
		ar[j+size] = temp;
	}
}
void shellSort(int *ar, int len)
{
	int d[] = {5,3,1};//size
	for(int i=0; i<sizeof(d)/sizeof(d[0]); ++i)
	{
		shell(ar, len, d[i]);
	}
}

//quickSort(recursion)
int partition(int *ar, int low, int high)
{
	int temp = ar[low];

	while(low < high)
	{
		while(low<high && ar[high] >= temp)
		{
			--high;
		}
		if(low == high)
		{
			break;
		}
		else
		{
			ar[low] = ar[high];
		}

		while(low<high && ar[low] <= temp)
		{
			++low;
		}
		if(low == high)
		{
			break;
		}
		else
		{
			ar[high] = ar[low];
		}
	}

	ar[low] = temp;
	return low;
}
void quick(int *ar, int low, int high)
{
	int par = partition(ar, low, high);

	if(par > low+1)
	{
		quick(ar, low, par-1);
	}
	if(par < high-1)
	{
		quick(ar, par+1, high);
	}
}
void quickSort(int *ar, int len)
{
	quick(ar, 0, len-1);
}


//quickSort2(norecursion)
void quickSort2(int *ar, int len)
{
	int *stack = new (nothrow) int[len];
	int top = 0;
	int low = 0;
	int high = len-1;

	stack[top++] = low;
	stack[top++] = high;
	do
	{
		high = stack[--top];
		low = stack[--top];
		int par = partition(ar, low, high);
		if(par > low+1)
		{
			stack[top++] = low;
			stack[top++] = par-1;
		}
		if(par < high-1)
		{
			stack[top++] = par+1;
			stack[top++] = high;
		}
	}while(top > 0);

	delete []stack;
}

//mergeSort(recursion)
void sort(int *ar, int low, int mid, int high)
{
	int i = low, j = mid+1, k = 0;
	int *temp = new (nothrow) int[high-low+1];

	while(i<=mid && j<=high)
	{
		if(ar[i] < ar[j])
		{
			temp[k++] = ar[i++];
		}
		else
		{
			temp[k++] = ar[j++];
		}
	}

	while(i<=mid)
	{
		temp[k++] = ar[i++];
	}
	while(j<=high)
	{
		temp[k++] = ar[j++];
	}

	for(int i=low, k=0; i<=high; ++i, ++k)
	{
		ar[i] = temp[k];
	}
	delete []temp;
}
void merge(int *ar, int low,  int high)
{
	if(low < high)
	{
		int mid = (low+high)/2;
		merge(ar, low, mid);
		merge(ar, mid+1, high);
		sort(ar, low, mid, high);
	}
}
void mergeSort(int *ar, int len)
{
	merge(ar, 0, len-1);
}

//mergeSort2(norecursion)
void mergeSort2(int *ar, int len)
{
	int size = 1, low, mid, high;

	while(size < len-1)
	{
		low = 0;
		while( low+size < len)//low+size-1 < len-1
		{
			mid = low+size-1;
			high = mid+size;
			if(high > len-1)
			{
				high = len-1;
			}
			sort(ar, low, mid, high);
			low = high+1;
		}
		size *= 2;
	}
}
//堆排序为不稳定排序 时间复杂度为O(nlog2n) 空间复杂度为O(1)
void adjustFromUp(int *ar, int start, int end)//调整最大堆 end下标可取
{
	int i=start, j=2*i+1;//记录双亲结点和孩子结点
	int temp = ar[i];

	while(j<=end)
	{
		if(j+1<=end && ar[j+1]>ar[j])//在不越界的情况下,j为值最大的孩子结点
		{
			++j;
		}
		if(temp >= ar[j])//start结点比孩子结点大
		{
			break;
		}		
		ar[i] = ar[j];//将大的孩子结点赋值个双亲结点
		//调整下标
		i = j;
		j = 2*i+1;		
	}
	ar[i] = temp;
}
void makeMaxHeap(int *ar, int len)//建立最大堆
{
	for(int i=(len-1)/2; i>=0;--i)
	{
		adjustFromUp(ar, i, len-1);//扩大的调整范围
	}
}
void heapSort(int *ar, int len)
{
	//建立最大堆
	makeMaxHeap(ar,len);
	for(int i=0;i<len-1; ++i)
	{
		//将最大的元素和最后一个元素交换
		int temp = ar[0];
		ar[0] = ar[len-i-1];
		ar[len-i-1] = temp;
		adjustFromUp(ar, 0, (len-1-i)-1); //len-1-i保证下标可取, 再减1表示最后一个元素已经有序,不须要再调整
	}
}

int main(void)
{
	int ia[] = {45,56,78,9,23,45,12,99,82,65,3000,};
	int len =sizeof(ia)/sizeof(ia[0]);
	//heapSort(ia, len);	

	//bubbleSort(ia, len);
	//selectSort(ia, len);
	//insertSort(ia, len);
	//shellSort(ia, len);
	quickSort(ia, len);
	//quickSort2(ia, len);
	//mergeSort(ia, len);
	//mergeSort2(ia, len);
	show(ia, len);

	return 0;
}