快速排序

快速排序是公认的排序之王，其基本思想为： 任取待排序元素序列中的某元素作为基准值，按照该基准值将待排序列分为两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右序列重复该过程，直到所有元素都排列在相应位置上为止。

对于如何按照基准值将待排序列分为两子序列，常见的方式有：
1、Hoare版本
2、挖坑法
3、前后指针法
这三种方法并没有明显的优缺点，时间复杂度都为O（nlogn）

递归实现

Hoare版本

Hoare版本单趟排序的基本步骤如下：
1.选一个key作为比较值，一般是最左边或者最右边。
2.定义一个left和right，如果key选取的是左边就让右边的先走，直到right找到一个比key小的值，然后让left从左边走，直到让它找到一个比key大的值，然后交换两者，之后继续让right先走，left后走，直到left与right相遇停下来。
3.最终再让相遇处与key处位置对应的值做交换，这样就可以达到我们想要的效果了。
4.之后递归它的左序列和右序列，最终排成升序。

注意：可能有小伙伴会问了，如果你最后key与meet（相遇处）处对应的值交换，万一meet比key处的值大，那不就达不到我们要的效果了吗？其实这里并不会出现这个问题，因为这种方法让right先走了，所以不会出现这种问题，大家可以多去尝试几组数据看看，是不是会有这个特点

代码实现

//快速排序（Hoare版本）
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)//当只有一个数据或是序列不存在时，不需要进行操作
		return;

	int begin = left;//L
	int end = right;//R
	int key = left;//key的下标
	while (left < right)
	{
		//right先走，找小
		while (left < right&&a[right] >= a[key])
		{
			right--;
		}
		//left后走，找大
		while (left < right&&a[left] <= a[key])
		{
			left++;
		}
		if (left < right)
		{
			swap(&a[left], &a[right]);
		}
	}
	int meet = left;//L和R的相遇点
	swap(&a[key], &a[meet]);//交换key和相遇点的值

	QuickSort1(a, begin, meet - 1);//key的左序列进行此操作
	QuickSort1(a, meet + 1, end);//key的右序列进行此操作
}

注意：
1.这里要保存一下left和right的值，因为你在代码过程中left和right的值会发生变化，如果你不保存，在递归时传参直接传left和right的话，那时就不是我们想要的值了。
2.这里你key要记录left的下标，而不是记录a[left]这个数值，因为如果这样的话，你在下面交换key位置和meet位置对应的值时就会出问题，你只有记录下标，才可以做到对应位置值得交换。

递归图解

挖坑法

挖坑法的单趟排序的基本步骤如下：
1.先选取一个初始坑位，并让此位置的值记作key（一般选取最左边或者最右边）
2.同样这里也是right先走，直到找到一个比key小的值，然后将这个值填入坑位，并让这个位置再来做坑，之后移动left，直到找到一个比key大的值，再将这个位置的值填入坑位，然后让这个位置来做坑。这样一直循环下去，直到left==right。
3.当left与right相遇时，此时将key的值赋值给相遇位置即可，这时就达到我们想要的效果：key左边的值都小于key，key右边的值都大于key。
4.然后仍然是递归其左序列和右序列，最终整个序列升序。

代码实现

//快速排序 （填坑法）
void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left; //保存left的值，为了下面的递归传递
	int end = right;//保存right的值，为了下面的递归传递
	/*int key = left;*/  //这个地方要记住那个数，因为记下标
	//的话，没用，left已经和其他位置交换过了，那么就不是我们想要的值了
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		while (left<right&&a[right]>=key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (left<right&&a[left]<=key)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	int meet = left;
	a[meet] = key;
	QuickSort2(a, begin, meet- 1);
	QuickSort2(a, meet+ 1, end);
}

注意：
1.这里同样也要保存下left和right的值，原因同Hoare法的一样，因为代码过程中其值发生改变会影响递归传递。
2.这里与Hoare法有所不同，这里key要记录a[left],而不是下标，因为你在之后的填坑过程中，left下标处的值可能被交换了，不是我们最初想要的值，所以要记录下来最初的那个值，即a[left]。

递归图解

前后指针法

前后指针法的单趟排序的基本步骤如下：
1.选出一个key作为比较值，一般是最左或者最右边。让prev指向left，cur指向left+1。
2.之后比较cur位置的值和key的值，首先要保证cur位置的值要小于key，而且++prev！=cur,这时交换prev和cur位置对应的值，不管满不满足这两个条件，cur都要++，这样才能迭代起来。
3.直到cur越界，此时prev为key应该在的位置，此时交换prev位置的值和key，就可以达到我们想要的效果。
4.仍然是递归其左序列和右序列，最终整个序列有序。

代码实现

//快速排序（前后指针法）
void QuickSort3(int *a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//这里没有必要记录left和right的值，因为整个代码中这两个量一开始是什么值，最终仍然是那个值
	//int begin= left;
	//int end = right;
	int pre = left;
	int cur = left + 1;
	int key = left; //这里要记住小标，不然值是交换不过去的，一般快排中用到交换的换，都是记录下标
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++pre != cur)
		{
			swap(&a[pre], &a[cur]);
		}
		cur++;
	}
	int meet = pre;
	swap(&a[meet], &a[key]);
	QuickSort3(a, left, meet - 1);
	QuickSort3(a, meet + 1, right);
}

注意：
1.这里没有必要再和上面一样保存left和right的值了，因为整个过程中left和right的值并没有变化。
2.这里和Hoare法那儿一样，key要记录left这个下标，而不是a[left]这个值，因为你之后要交换meet和key位置处对应的值，而你一开始如果记录a[left]是做不到这一点的。(一般而言如果有swap交换这个需求的话，都要记录下标，而不是下标处对应的值）
3.这里要注意a[cur] < a[key] && ++pre != cur这两个条件写的先后顺序，一定要把比较大小写在前面，如果你的a[cur]都不满足比a[key]小，那么就不需要++prev这一步的判断了。

递归图解

非递归实现

当我们需要将一个用递归实现的算法改为非递归时，一般需要借用一个数据结构，那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本，其实主体思想一致，只是调用的单趟排序的算法不同而已。

Hoare版本

//快速排序（前后指针法）
void QuickSort3(int *a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//这里没有必要记录left和right的值，因为整个代码中这两个量一开始是什么值，最终仍然是那个值
	//int begin= left;
	//int end = right;
	int pre = left;
	int cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++pre != cur)
		{
			swap(&a[pre], &a[cur]);
		}
		cur++;
	}
	int meet = pre;
	swap(&a[meet], &a[key]);
	QuickSort3(a, left, meet - 1);
	QuickSort3(a, meet + 1, right);
}

挖坑法

//挖坑法（单趟排序）
int QuickSort2(int* a, int left, int right)
{
	int key = a[left];//在最左边形成一个坑位
	while (left < right)
	{
		//right向左，找小
		while (left < right&&a[right] >= key)
		{
			right--;
		}
		//填坑
		a[left] = a[right];
		//left向右，找大
		while (left < right&&a[left] <= key)
		{
			left++;
		}
		//填坑
		a[right] = a[left];
	}
	int meeti = left;//L和R的相遇点
	a[meeti] = key;//将key抛入坑位
	return meeti;//返回key的当前位置
}

前后指针法

//前后指针法（单趟排序）
int QuickSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)//当cur未越界时继续
	{
		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	int meeti = prev;//cur越界时，prev的位置
	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
	return meeti;//返回key的当前位置
}

快速排序的非递归算法基本思路：
1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
2、当栈不为空时，读取栈中的信息（一次读取两个：一个是L，另一个是R），然后调用某一版本的单趟排序，排完后获得了meet的下标，然后判断meet的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的L和R入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
3、反复执行步骤2，直到栈为空为止。

非递归快排代码实现

//类似于二叉树的遍历，根——右子树——左子树
void QuickSort4(int* a, int left, int right)
{
	ST p;
	StackInit(&p);
	StackPush(&p, left);
	StackPush(&p, right);
	while (!StackEmpty(&p))
	{
		int right= StackTop(&p);   //注意栈的性质，或进先出，因此先赋值给right
		StackPop(&p);
		int left= StackTop(&p);
		StackPop(&p);
		//if (left >= right)   可写可不写
		//{
		//	return;
		//}
		int meet = QuickSort5(a, left, right);
		if (left < meet - 1)  //左序列还存在时
		{
			StackPush(&p, left);
			StackPush(&p, meet - 1);
		}
		if (meet + 1 < right)  //右序列还存在时
		{
			StackPush(&p, meet + 1);
			StackPush(&p, right);
		}
	}
	StackDestory(&p);
}

注意：这里要注意栈的性质后进先出，因此要先赋值给right再赋值给left。

图解代码

时间复杂度：O（nlogn）

快速排序的两个优化

1.三数取中

快速排序的时间复杂度是O(NlogN)，是我们在理想情况下计算的结果。在理想情况下，我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：

 若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，那么快速排序的时间复杂度就是O(NlogN)。
但是万一当待排序列本就是一个有序的序列时，我们若是依然每次都选取最左边或是最右边的数作为key，那么快速排序的效率将达到最低：

这时的时间复杂度为O（n^2)。其实，对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则则效率越高。

为了避免这种极端情况的发生，于是出现了三数取中：
三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

代码实现

int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2; //防止整形溢出
	if (a[right] > a[mid])
	{
		if (a[mid] > a[left])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else
	{
		if (a[left] > a[mid])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}

2.小区间的优化

我们可以看到，就算是上面理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以2倍的形式快速增长。
为了减少递归树的最后几层递归，我们可以设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。小区间优化若是使用得当的话，会在一定程度上加快快速排序的效率，而且待排序列的长度越长，该效果越明显。

代码实现

//快速排序的小区间优化
void QuickSort6(int *a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if (right - left + 1 > 20)
	{
		int meet = QuickSort5(a, left, right);
		QuickSort5(a, left, meet - 1);
		QuickSort5(a, meet + 1, right);
	}
	else
	{
		ShellSort(a,right-left+1);
	}
}

---

归并排序

归并排序是采用分治法的一个非常典型的应用。其基本思想是：先让每个子序列都有序，然后再合并这些子序列，让整个序列有序。这其中要注意了：子序列又可以看成是一个整体又可以分成两个子序列，要直到分到序列只有一个数时，这时才不能继续分了，且当只有一个数时，这个序列就是有序的。其实这儿的思想和二叉树的好像，当你看完代码和递归过程后，你还会发现其实这个和二叉树的后序遍历很相似。
下面来看个例子：

其实这张图就相当于是整个递归的过程，分解的过程相当于递归的顺序执行，合并的过程相当于递归返回的过程。

递归实现

其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列，合并完毕后再将数据拷贝回原数组。

void  MergeSort(int* a, int left, int right,int* temp)
{
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	int begin1 = left, end1 = mid;
	int begin2 = mid+1, end2 = right;
	int i = left,j=0;  //i一定要写成left不能写成0，如果是递归左序列还可以适用，但是递归到右序列时就不行了
	MergeSort(a, left, mid, temp);  //这里要注意区间的划分，不然可能出现死递归
	MergeSort(a, mid + 1, right, temp);
	while (begin1 <= end1&&begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			temp[i++] = a[begin1++];
		}
		else
		{
			temp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = a[begin2++];
	}
	for (j = left; j < right + 1; j++)
	{
		a[j] = temp[j];
	}
}

时间复杂度 ： O（NlogN） 空间复杂度： O（N）

递归图解

区间划分要注意（死递归）

在上面的代码中，我们将区间划分成了[left,mid]和[mid+1，right],是不是只能这样分了？带着这样的好奇，我尝试了另一种分法，将区间划分成[left,mid-1]和[mid,right],这样划分是否可以了？经过画图分析后，答案是不可以的，在这个问题中，区间只能这么划分。

如果你是这样划分的话，在某些测试用例中，可能会出现死递归。其原因是你的mid和right有可能永远不会相等，也就无法结束掉某个递归，因此造成了死递归。

非递归实现

归并排序的非递归并不像快速排序那样一定要用栈来实现，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序

这只是一个理想化的例子，在做这种题目时，我们一定要充分考虑到边界情况。

情况一：
第二个小区间存在，但是个数不满，这时我们需要对边界进行控制，不然会导致序列合并时数组越界的问题。

情况二：
第二个小区间不存在，第一个小区间存在，这时我们不需要在意第一个小区间有没有满，因为这时只有一个区间，无法进行序列的合并，所以直接不管它，即break出去就行。

代码实现

void _MergeSort(int *a, int begin1,int end1,int begin2,int end2, int * temp)
{
	int j = begin1;
	int i = begin1;
	while (begin1 <= end1&&begin2 <= end2)  //用&&链接，其中有一个结束就结束了
	{
		if (a[begin1] < a[begin2])
		{
			temp[i++] = a[begin1++];
		}
		else
		{
			temp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)   //如果区间一还有则全部赋值过去
	{
		temp[i++] = a[begin1++];  
	}
	while (begin2 <= end2)   //如果区间二还有则全部赋值过去，这时两个序列合并完成
	{
		temp[i++] = a[begin2++];
	}
	for (; j <= end2; j++)  //将合并好的序列传给原数组
	{
		a[j] = temp[j];
	}
}

void MergeSort2(int *a, int n)
{
	int *temp = (int *)malloc(sizeof(int)*n);
	if (temp == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	int gap = 1; //控制每次元素的个数
	int i = 0;
	while (gap < n)
	{
		for (i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + (2 * gap) - 1;
			if (begin2 >= n)  //此时只有第一个区间，不存在两个序列合并的需求，因此直接break
			{
				break;
			}
			if (end2 >= n) //此时第二个区间元素个数不满，为了防止合并两个序列时数组访问越界，在这里处理掉
			{
				end2 =n-1;
			}
			_MergeSort(a, begin1, end1, begin2, end2, temp);
		}
		gap *= 2;
	}
	free(temp);
}

递归图解

计数排序

计数排序又叫非比较排序，它不需要比较就可以排序，是不是很神奇了？它主要是利用哈希映射来实现的（这在之后c++部分会详细介绍），这里大概说下它的思路：
1.首先创建一个数组，那么这个数组的大小怎么定了？这取决于原数组中的最大值和最小值。
2.然后我们遍历原数组，遇到哪个值则在创建的数组中以他为下标的位置++。
3.最后打印创建的数组的下标，那个下标存放的值为几，则那个下标就打印几次。

注意：为什么我们这样就能保证数组是有序的了？其实最主要的原因是因为数组的下标本来就是有序的，其次这其中利用了哈希映射。

绝对映射和相对映射

上列中的映射方法称为绝对映射，即arr数组中的元素是几就在count数组中下标为几的位置++，但这样会造成空间浪费。例如，我们要将数组：1001,1002,1005，进行排序，难道我们要开辟1006个整型空间吗？
所以我们使用计数排序时，最好是使用相对映射。下面我们来简单介绍下相对映射：数组中的最小值就相对于count数组中的0下标，数组中的最大值就相对于count数组中的最后一个下标。这样，对于数组1001,1002,1005我们只需要开辟5个空间即可，即此时count数组中下标为i的位置，记录的是1001+i出现的次数。
总的来说：
绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。
这里也要注意：计数排序针对数字较为集中时处理比较高效，如果刚刚那个数组为1,100,1005则不管使用什么映射，都会存在空间的浪费。

代码实现

//计数排序
void CountSort(int*a, int sz)
{
	int min = a[0], max = a[0];
	int i = 0;
	int j = 0;
	for (i = 1; i < sz; i++)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i]>max)
		{
			max = a[i];
		}
	}
	int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身）
	int *count = (int*)calloc(range, sizeof(int));//min和max之间的自然数个数（包括min和max本身）
	if (count == NULL)
	{
		printf("calloc failed\n");
		exit(-1);
	}
	统计相同元素出现次数（相对映射）
	for (i = 0; i < sz; i++)
	{
			count[a[i]-min]++;
	}
	根据统计结果将序列回收到原来的序列中
	for (i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i+min;
		}
	}
	free(count);
}