void print(int a[], int n ,int i){  
	cout<<i <<":  ";  
	for(int j= 0; j<n; j++){  
		cout<<a[j] <<" ";  
	}  
	cout<<endl;  
}  
void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}
//直接插入排序
void StraightInsertSort(int a[], int num)
{
	cout<<"StraightInsertSort "<<endl;  

	for (int i=1; i<num; i++)
	{
		if (a[i] < a[i-1])	//插入元素小于前一个元素，向前插入
		{
			int x = a[i];
			int k = i-1;
			a[i] = a[i-1];
			while (x < a[k])	//依次向后移动
			{
				a[k+1] = a[k];
				k--;
			}
			a[k+1] = x;
		}
		print(a, num, i);
	}
}
//希尔排序，改进直接插入排序
void ShellInsertSort(int a[], int num, int dk)
{
	cout<<"dk= "<<dk<<endl;  

	for (int i=dk; i<num; i++)
	{
		if (a[i] < a[i-dk])
		{
			int x = a[i];
			int k = i - dk;
			a[i] = a[k];
			while (x < a[k])
			{
				a[k+dk] = a[k];
				k -= dk;
			}
			a[k+dk] = x;
		}
		print(a, num, i);
	}
}
void ShellSort(int a[], int num)
{
	cout<<"ShellInsertSort "<<endl;  

	int dk = num/2;
	while (dk >= 1)
	{
		ShellInsertSort(a, num, dk);
		dk /= 2;
	}
}

//简单选择排序
void SimpleSelectSort(int a[], int num)
{
	for (int i=0; i<num; i++)
	{
		int minNum = a[i];
		int pos = -1;
		for (int k=i+1; k<num; k++)
		{
			if (minNum > a[k])
			{
				minNum = a[k];
				pos = k;
			}
		}
		if (pos != -1)
		{
			a[pos] = a[i];
			a[i] = minNum;
		}
		print(a, num, i);
	}
}
//双向选择排序
void SelectionExSort(int a[], int num)
{
	for (int i=1; i<=num/2; i++)
	{
		int maxPos = i-1;
		int minPos = num-i;
		for (int k=i+1; k<num-i; k++)
		{
			if (a[maxPos] < a[k])
			{
				maxPos = k;
			}
			if (a[minPos] > a[k])
			{
				minPos = k;
			}
		}
		if (a[minPos] < a[i-1])
		{
			swap(a[minPos], a[i-1]);
		}

		if (a[maxPos] > a[num-i])
		{
			swap(a[maxPos], a[num-i]);
		}

		print(a, num, i);
	}
}

//冒泡排序
void BubbleSort(int a[], int num)
{
	for (int i=0; i<num; i++)
	{
		for (int k=0; k<num-1-i; k++)
		{
			if (a[k] > a[k+1])
			{
				swap(a[k], a[k+1]);
			}
		}
		print(a, 10, i);
	}
}
//简化冒泡排序，如果之后有序，不在排列
void BubbleSort_1(int a[], int num)
{
	int endPos = num-1;
	int i = 0;
	while (endPos > 0)
	{
		int pos = 0;
		for (int k=0; k<endPos; k++)
		{
			if (a[k] > a[k+1])
			{
				pos = k;
				swap(a[k], a[k+1]);
			}
		}
		endPos = pos;
		print(a, 10, i++);
	}
}
//双向冒泡排序
void BubbleSort_2(int a[], int num)
{
	int lowPos = 0;
	int highPos = num-1;
	int k;
	int i = 0;
	while (lowPos < highPos)
	{
		for (k=lowPos; k<highPos; k++)
		{
			if (a[k] > a[k+1])
			{
				swap(a[k], a[k+1]);
			}
		}
		highPos--;
		print(a, 10, i);
		for (k=highPos; k>lowPos; k--)
		{
			if (a[k] < a[k-1])
			{
				swap(a[k], a[k-1]);
			}
		}
		lowPos++;
		print(a, 10, i++);
	}
}

static int i = 0;
//快速排序
void QuickSort(int a[], int low, int high)
{
	if (low >= high)
	{
		return;
	}
	int first = low;
	int last = high;
	int key = a[low];
	while (first < last)
	{
		while (first < last && a[last] >= key)
		{
			last--;
		}
		a[first] = a[last];
		while (first < last && a[first] <= key)
		{
			first++;
		}
		a[last] = a[first];
	}
	a[first] = key;
	print(a, 10, i++);
	QuickSort(a, low, first-1);
	QuickSort(a, first+1, high);
}

//归并排序
void Merge(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex)
{
	int i = startIndex,j=midIndex+1,k = startIndex;
	while(i!=midIndex+1 && j!=endIndex+1)
	{
		if(sourceArr[i]<sourceArr[j])
			tempArr[k++] = sourceArr[i++];
		else
			tempArr[k++] = sourceArr[j++];
	}
	while(i!=midIndex+1)
		tempArr[k++] = sourceArr[i++];
	while(j!=endIndex+1)
		tempArr[k++] = sourceArr[j++];
	for(i=startIndex;i<=endIndex;i++)
		sourceArr[i] = tempArr[i];
}
//内部使用递归
void MergeSort(int sourceArr[],int tempArr[],int startIndex,int endIndex)
{
	int midIndex;
	if(startIndex<endIndex)
	{
		midIndex=(startIndex+endIndex)/2;
		MergeSort(sourceArr,tempArr,startIndex,midIndex);
		MergeSort(sourceArr,tempArr,midIndex+1,endIndex);
		Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);
	}
	print(sourceArr, 10, i++);
}