void InSertSort(int* a, int n)
{
	//但趟排序 [0.end]有序，end+1插入进去、、、
	//假设排升序：

	//这里i最大取到倒数第二个位置就可以了。把最后一个位置在插入进去就排完了。
	for (int i = 0; i < n - 1; i++)
	{
		//单趟排序  [0,end] 有序，end+1，插入进前面的区间。
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			// 要降序改一下这里符号。
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				//a[end + 1] = tmp;   这句代码这里可以不写，和极端情况进行合并了。
				break;
			}
		}
		//极端情况end==-1时。
		a[end + 1] = tmp;
	}

}

2.冒泡排序

/ 最坏：O（N^2）
// 最好：O(N)
//冒泡排序
void BubbleSort(int* a, int n)
{
	//假设排升序

	for (int j = 0; j < n; j++)
	{
		int exchenge = 0;
		//单趟     多趟加一个j去控制单趟循环的结束位置。
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				exchenge = 1;
				swap(&a[i - 1],&a[i]);
			}
		}
		//没有发生交换，那么就一定已经有序了，不用在继续冒泡了。
		if (exchenge == 0)
			break;
	}
}

3.希尔排序

//希尔排序        算是插入排序的优化
// 平均 O(N^1.3)
// 最坏：O(log3(N) * N) 这里log3(N)是以3为底N的对数
void ShellSort(int* a, int n)
{
	//这是一组一组排序的写法，
	// 
	//int gap =n;  //这里gap等于3是不肯拍好的，gap大于1时都是预排序的，使之接近有序。再来一个循环控制gap的变化。

	//while(gap>1)  //gap>1  之前都是预排序的。
	//{
	//	gap=gap/3+ 1;  //+1时为了保证gap会有等于1的时候。

	控制多个分组的end 位置
	//	for (int j = 0; j < gap; j++)
	//	{
	//		//一个分组的排序  ，控制一个分组end的位置。
	//		for (int i = j; i < n - gap; i += gap)
	//		{
	//			//单趟 
	//			int end = i;
	//			//[0，end]  end加一插入进去
	//			int tmp = a[end + gap];
	//			while (end >= 0)
	//			{
	//				if (tmp < a[end])
	//				{
	//					a[end + gap] = a[end];
	//					end -= gap;
	//				}
	//				else
	//				{
	//					//a[end + gap] = tmp;  可以归到特殊情况里面。
	//					break;
	//				}
	//			}
	//			a[end + gap] = tmp;
	//		}
	//	}
	//}

	//其实我们不需要一组全部排完再去排下一组，可以每组排一个，在每组排一个。
	//思想上与前面那种写法是一样的，时间复杂度也是一样的。

	int gap =n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//一个分组的排序  ，控制一个分组end的位置。
		for (int i = 0; i < n - gap; i++)
		{
			//单趟 
			int end = i;
			//[0，end]  end加一插入进去
			int tmp = a[end + gap];
			while (end >= 0)     //end等于01也要比较一次的，万一tmp是最小的呢。
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}

4.快排

（1.）快排单趟排序三种写法

效率上没有区别的，写法上，越往后越是新的写的，越好写，越不容易出错。

【1】hoare版本单趟排序

int PartSort1(int* a, int left, int right)
{
	//三数取中优化
	int mid = Getmidindex(a, left, right);
	swap(&a[mid], &a[left]);
	//假设排升序
	int key = left;

	//key左边的值比他小，key右边的值比他大，等于key的值，放在左边还是右边都是可以的。
	while (left < right)
	{
		//右边先走，右边找小。
			while (left < right && a[right] >= a[key])
				right--;

		//左边后走，左边找大。
	   while(left < right && a[left] <= a[key])
				left++;

		swap(&a[left], &a[right]);
	}
	//1.因为右边先走的，所以相遇点一定是小于a[key],
	//2.或者右边直接找到了left也就是a[key]，那这时左边不能找了，自己与自己交换下也没啥。
	swap(&a[left], &a[key]);
	//left 是最后相遇点

	return left;
}

【2】挖坑法?

int PartSort2(int* a, int left, int right)
{
	//三数取中优化
	int mid = Getmidindex(a, left, right);
	swap(&a[mid], &a[left]);

	//不需要考虑left<right 因为	QuickSort中考虑过了。
	int key = a[left];
	int pit = left;
	while (left<right)   //等于相遇就不找了，返回相遇点。
	{
		//这里的== 最好俩个都写，至少要写一个，不然的话极端情况 左边右边都找到key值，都不跳过，死循环了就。
		// 5 1 2 3 4 5 5   俩个都不写==的话，俩边都不会收缩，一直交换，直接死循环了。
		while (left<right && a[right]>=key)
			right--;
			a[pit] = a[right];
			pit = right; //更新坑位。
		while (left < right && a[left] <=key)
			left++;
			a[pit] = a[left];
			pit = left;

	}
	a[pit]=key;
	return pit;
}

【3】前后指针法 ? 最新的写法，写起来最简单，最不容易出错

int PartSort3(int* a, int left, int right)
{
	//三数取中优化
	int mid = Getmidindex(a, left, right);
	swap(&a[mid], &a[left]);

   //左边做key
	int prev = left;  //left左key
	int cur = left + 1;
	int keyi=left;
	while (cur <=right)  //==也要进行一次比较的。
	{
		//prev及prev之前的都是小于key的,之后都是大于key的。
		while (a[cur] < a[keyi] && ++prev != cur)  // 防止自己和自己交换  a[prev+1]!=a[cur] 这样用值比较还行也许，
			                                       //但是用值判断是不是自己，感觉不太好.
			swap(&a[cur], &a[prev]);   //再这里++prev是不对的。

		cur++;//跳过大于key的，继续向后找小于key的。
	}
	swap(&a[keyi], &a[prev]);
	return prev;

	//右边做key
	//int prev = left-1; 
	//int cur = left;
	//int keyi = right;
	//while (cur <right)  //right现在是key不需要比较，最后换到在该在的位置上。
	//{
	//	//prev及prev之前的都是小于key的,之后都是大于key的。
	//	while (a[cur] < a[keyi] && a[++prev] != a[cur])  //a[prev+1]!=a[cur] 防止自己和自己交换
	//		swap(&a[cur], &a[prev]);   //再这里++prev是不对的。

	//	cur++;//跳过大于key的，继续向后找小于key的。
	//}
	//swap(&a[keyi], &a[++prev]);  //++prev 因为我们要把右边的key换回来，要把大的甩到右边。
	//return prev;
}

(2.)快排

【1.】快排递归

void QuickSort(int* a, int begin,int end)
{
	//等于是区间只有一个数据，已经在他该在的位置了。
	//还有一种是区间是不和法的，分过了，直接返回就好了。
	if (begin >= end)
		return;
	int keyi = PartSort3(a, begin, end);  
	//分治为子问题，递归去解决。 按照区间划分。[begin,keyi-1] keyi [keyi+1,end];
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1,end);
}

【2】快排非递归

这里其实是用我们之前写的栈去模拟递归的，如果之前没有写的话，c++里面stl是直接有的，但是c语言没有，需要去写一下栈就好了。

void QuickSort2(int* a, int begin, int end)
{
	Stack st;
	StackInit(&st);

	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(a, left, right);
		//[begin,keyi-1]  [keyi+1,end]
		if (left < keyi - 1)
		{
			StackPush(&st,left);
			StackPush(&st, keyi - 1);
		}

		if (keyi + 1 < right)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, right);
		}
	}

	StackDestory(&st);
}

【3】快排的优化一三数取中优化

这个是快排的核心优化，非常重要

//三数取中
int Getmidindex(int* a, int left, int right)
{
	int mid = left+(right - left) / 2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
			return right;
		else
		{
			if (a[left] < a[right])
				return left;
			else
				return right;
		}
	}
	else
	{
		if (a[mid] < a[right])
			return mid;
		else
		{
			if (a[left] > a[right])
				return left;
			else
				return right;
		}
	}
	/*if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else
		{
			if (a[left] > a[right])
				return left;
			else
				return right;
		}
	}
	else 
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else
			return right;

	}*/

}

【4】快排的优化二小区间优化

这个优化堆快排的效率优化不是特别大，但是也是有优化的。

//快排的小区间优化，  也就是当区级比较小时，不去递归再分了，改用插入排序去直接排好序。
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if (end-begin+1 <=20)
	{
		//注意这里一定要注意的是  a+begin 才是起点。  后面是end-begin，小心写反了。
		InSertSort(a+begin, end-begin + 1);
	}
	else
	{
		int keyi = PartSort3(a, begin, end);

		QuickSort1(a, begin, keyi-1);
		QuickSort1(a, keyi+1,end);
	}

}

5.归并排序?

（1.）归并排序递归写法

【1】归并排序子函数

因为用子函数更方便一点，我们写一个子函数去递归

//归并子函数
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	//只有一个或者区间不存在。
	if (begin >= end)
		return;
	int mid = begin + (end - begin) / 2;
	//[begin,mid] [mid+1,end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	//但是要注意这样子划分区间是不行的 [begin,mid-1] [mid,end] 
	//因为如果遇到奇数偶数子再一起的，相除是奇数，第一个区间不存在，但是第二个区间不会往前走，死循环了就。
	_MergeSort(a, begin1, end1, tmp);
	_MergeSort(a, begin2, end2, tmp);

	//走到这里的话，那就说明这里的左右是有序的了，进行归并
	//也就是[begin1,end1]  [begin2,end2]  区间有序了。

	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}

	//剩下的再放在后面。
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	//归并好的那一段拷贝回原数组，注意不是从开始拷贝的。
	memcpy(a+begin, tmp+begin,(end-begin+1)*sizeof(int));
}

【2】归并排序

void MergeSort(int* a, int n)
{
	//用来归并的数组。
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
	}

	_MergeSort(a,0,n-1,tmp);

	free(tmp);
}

（2.）归并排序循环写法

用循环写是因为优先情况下递归太深回造成栈溢出的，所以用循环去该

//递归 现代编译器优化很好，性能已经不是大问题
 //最大的问题->递归深度太深，程序本身没问题，但是栈空间不够，导致栈溢出
 //只能改成非递归，改成非递归有两种方式：
 //1、直接改循环-》斐波那契数列求解
 //2、树遍历非递归和快排非递归等等，只能用Stack存储数据模拟递归过程
//归并排序循环写法
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp== NULL)
	{
		printf("malloc fail\n");
	}
	int gap = 1;

	while (gap < n)

	{

		for (int i = 0; i < n; i += 2 * gap)
		{
			// 注意边界控制，带几个值取看看。
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			//修正1   思路简单。
			//if (end1 >= n)
			//	end1 = n - 1;

			//if (begin2>=n)
			//{
			//	begin2 = n;
			//	end2 = n - 1;
			//}

			//if (begin2 < n && end2 >= n)
			//{
			//	end2 = n - 1;
			//}
//修正2			
//注意最后一次归并特殊情况（越界代码就会****崩****，再free（）的时候，就会报错）       1.3.归为一种情况，第二个区间不存在就不用再归了。
//1.最后一个小组归并时，第二个小区间不存在，不需要归并了。
//2.最后一个小组归并时，第二个小区间存在，但是第二个小区间不够gap个。
//3.最后一个小组归并时，第一个小区间不够gap的，不需要归并了。
// 
			// 如果第二个小区间不存在就 ***不需要归并了***，结束本次循环
			if (begin2 >= n)       //  1.3的情况，第一个满，begin2等于n，第一个都不满，begin2大于n。
				break;

			//走到这里的话那就是begin2是小于n的，并且第一个区间存在。
			// 如果第二个小区间存在，但是第二个小区间不够gap个，结束位置越界了，需要修正一下
			if (end2 >= n)
				end2 = n - 1;   //直接修正到数组最后一个值的位置。




			//用来打印区别看是否正确，比较是方便一点
			//然后就可以用条件断点直接跳到错误的地方低调试。
			//然后后我们发现其实区间越界了，需要我们取修正。
			//printf("[%d %d][%d %d]\n", begin1, end1, begin2, end2);

			//条件断点，方便调试
			//if (begin1 == 12 && end1 == 13 && begin2 == 14 && end2 == 15)
			//{
			//	int x = 0;
			//	int y = 0;
			//}


			
			int index = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else
				{
					tmp[index++]= a[begin2++];
				}
			}

			//剩下没有归完的，继续归。
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
		}

		//拷贝回原数组，一个gap全部归完再去拷贝。
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;
	}

	free(tmp);

}

6.选择排序

//选择排序
void SelectSort(int* a, int n)
{
	//写一个优化一点的版本，俩边找一个最大，最小。
	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int maxi = left, mini = left;
		for (int i = left; i <= right; i++) //i==right也是要比较的。这里right和left都是闭区间。
		{
			//找最大值
			if (a[maxi] < a[i])
				maxi = i;
			//找最小值
			if(a[mini] > a[i])
				mini =i;
		}

		swap(&a[mini], &a[left]);
		if (maxi == left)
		{
			//此时要进行修正最大值，因为最大值已经被换到mini坐标的位置上去了。
			maxi = mini;
		}
		swap(&a[maxi], &a[right]);
		left++;
		right--;
	}

}

7.堆排序

【1.】向下调整算法

//向下调整算法，  假设这里我们要建大堆 为了排升序
void AdjustDown(int* a,int size,int root)
{
	int parent = root;
	int child = parent*2+1;  //左孩子
	while (child<size)
	{
		//找出俩孩子中小的那个
		if (child+1<size && a[child + 1]>a[child])
			child++;
		if (a[child]>a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break; //已经是小堆了，不需要再调整了。
		}
	}
}

【2.堆排序】

//O(N*log(N)
// 堆排序
void HeapSort(int* a, int n)
{
	int index= (n - 2) / 2;  //最后一个孩子的父亲。
	//建堆  假设升序，建大堆
	for (int i = index; i>=0; i--)
	{
		AdjustDown(a, n, i);
	}
	int j = 0;
	for (int i = n-1; i>0; i--)  
	{
		swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
}

8.计数排序

 时间复杂度：O(N+range)
 只适合，一组数据，数据的***范围比较集中***8. 如果范围集中，效率是很高的，但是局限性也在这里
 并且只适合整数，如果是浮点数、字符串等等就不行了
 空间辅助度：O(range)
//      计数排序

void CountSort(int* a, int n)
{
	//求出最大，最小数
	int max = a[0], min = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (a[i] > max)
			max = a[i];

		if (a[i] < min)
			min = a[i];
	}

	//求有出几个数
	int range = max - min + 1;
	int* count = malloc(sizeof(int) * range);

	//初始化数组：
	memset(count, 0, sizeof(int) * range);

	//这里使用相对映射记数，节省空间。
	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;
	}

	int i = 0;
	for (int j = 0; j < range; ++j)
	{
		while (count[j]--)   //后置--，是几就进行几次
		{
			a[i++] = j + min;   //相对映射
		}
	}

	free(count);
}

三，测试排序

【1.】是否排好序

//void InSertSort()   这样子取名字会被误认为函数定义的，那么就重定义了。
void testInSertSort()

{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	InSertSort(a, sizeof(a) / sizeof(a[0]));
	printf("InSertSort\n");
	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testBubbleSort()

{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	BubbleSort(a, sizeof(a) / sizeof(a[0]));
	printf("BubbleSort\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testHeapSort()

{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	printf("HeapSort\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testShellSort()

{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	printf("ShellSort\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testQuickSort1()

{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	//按照闭区间写的。
	QuickSort(a, 0,sizeof(a) / sizeof(a[0])-1);
	printf("QuickSort\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testQuickSort2()
{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	//按照闭区间写的。
	QuickSort1(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	printf("QuickSort1\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testQuickSort3()
{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	//按照闭区间写的。
	QuickSort2(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	printf("QuickSort2\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testSelectSort()

{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	//按照闭区间写的。
	SelectSort(a,sizeof(a) / sizeof(a[0]));
	printf("SelectSort\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testMergeSort()

{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	//按照闭区间写的。
	MergeSort(a, sizeof(a) / sizeof(a[0]));
	printf("MergeSort\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}
void testMergeSortNonR()
{
	int a[] = { 1,4,8,6,43,6,8,9,4,43,5,6,8,5,34,2,65,5,43,89 };
	//按照闭区间写的。
	MergeSortNonR(a, sizeof(a) / sizeof(a[0]));
	printf("MergeSortNonR\n");

	Printf(a, sizeof(a) / sizeof(a[0]));
}

【2.各个排序效率如何呢】

是骡子是马，拉出来溜溜

测试代码

void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);
	int* a9 = (int*)malloc(sizeof(int) * N);
	int* a10 = (int*)malloc(sizeof(int) * N);





	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
		a9[i] = a1[i];
		a10[i] = a1[i];



	}

	int begin1 = clock();
	//InSertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	//ShellSort(a2, N);
	int end2 = clock();
	
	int begin7 = clock();
	//BubbleSort(a7, N);
	int end7 = clock();
	
	int begin3 = clock();
	//SelectSort(a3, N);
	int end3 = clock();
	
	int begin4 = clock();
	//HeapSort(a4, N);
	int end4 = clock();
	
	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();
	
	int begin6 = clock();
	QuickSort1(a6, 0, N - 1);
	int end6 = clock();

	int begin8 = clock();
	QuickSort2(a8, 0, N - 1);
	int end8 = clock();

	int begin9 = clock();
	MergeSortNonR(a9,N);
	int end9 = clock();

	int begin10= clock();
	MergeSortNonR(a10, N);
	int end10= clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("BublleSort:%d\n", end7 - begin7);

	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("QuickSort1:%d\n", end6 - begin6);
	printf("QuickSort2:%d\n", end8 - begin8);

	printf("MergeSortNonR:%d\n", end9 - begin9);
	printf("MergeSort:%d\n", end10 - begin10);




	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}
int main()
{
	testInSertSort();
	testBubbleSort();
	testShellSort();
    testQuickSort1();
	testQuickSort2();
	testQuickSort3();
	testSelectSort();
    testHeapSort();
	testMergeSort();
	testMergeSortNonR();
	TestOP();
	return 0;
}