承接上篇的八大排序，今天本篇文章主要讲归并排序，冒泡排序，快速排序(挖坑，左右指针，前指针)和计数排序

交换排序

基本思想： 所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置；
交换排序的特点是： 将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序

冒泡排序思想

基本思想：
重复遍历序列，依次比较相邻的两个元素，如果不是按照特定的顺序那么就交换，直到最终序列为特定的顺序即可。 冒泡排序之所以被称为冒泡，就是其排序顺序的原理就像气泡上升一样，大的泡泡先浮上水面，小的泡泡浮上水面就慢。
整体步骤：
第一趟让最大的数冒到最后，第二趟将次大的数冒到最后…直到序列有序为止， 所以我们就知道要用到双层循环了，外层循环确定比较趟数（n-1），内层循环确定每趟比较次数（n-j-1）。

代码

//交换
void Swap(int*p1,int*p2)
{
	int* tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
	//方法一：
	for (int j = 0; j < n; ++j)//比较几轮
	{
		int enchange = 0;
		for (int i = 1; i < n-j; ++i)//将数组中最大值冒到最后面
		{//这里i=1，如果i=0的话要注意下面交换函数中会存在越界访问
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				enchange = 1;
			}
		}
		//这里用了有一个判断是对原冒泡排序的一个优化，原冒泡排序如果待排序列接近有序，难道我们还要依次去比较吗？
		//因此我们定义一个enchange，如果发生比较，那么enchange的值为1，如果没有比较，则enchange为0，就break
		if (enchange == 0)//如果enchange等于0的话，就结束循环，就是看数组是否有序
		{
			break;
		}
	}

	//方法二：这个方法使用while做了外层循环，本质一样
	/*int end = n;
	while (end > 0)
	{
		for (int i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
			}
		}
		--end;
	}*/
}
void TestBubbleSort()
{
	int a[] = { 3, 5, 2, 7, 8, 6, -1, 9, 9, 4, 0 };
	BubbleSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

冒泡排序总结

• 冒泡排序是一种非常容易理解，而且非常简单的排序；
• 时间复杂度：O(N^2)；
• 空间复杂度：O(1)；
• 稳定性：稳定。

快速排序

快速排序思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。（我们果然是站在巨人的肩膀上😛）
其本思想： 任取待排序元素序列中的某元素作为基准值，首趟让这个基准值放到它相应地位置，并采用分治的思想按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列递归重复该过程，直到所有元素都排列在相应位置上为止。

三数取中

问题： 从上面《快速排序思想》中知道了快速排序是在序列中选出一个元素作为基准值（一般是首元素，或者尾元素），但是如果我们选的元素是最小的或者是最大的呢？😵😵😵
答： 那么将存在一些弊端，因此我们引入了三数取中的思想： 当我们知道这个序列的首和尾之后，我们可以轻易地找到中间元素，将首，中，尾三个元素中，选一个中间值作为基准值，这样就可以提高快速排序的效率。下面代码中还有小区间优化，大家在理解快速排序的基础上可以试着将三数取中和小区间优化也了解一下。

快速排序之挖坑法

这里就讲解部分先不按照三数取中和小区间优化，大家理解之后可以进一步按照代码学习三数取中和小区间优化。😋😋😋

单趟步骤：

• 1.把最左边或者最右的位置的值保存到key中，这个地方形成坑位（pivot）；
• 2.定义两个指针left和right，分别指向序列首元素和尾元素；
• 3.让right先从右向左走，找到比key小的位置停下来，并将这个元素放到坑位，然后自己形成新的坑；
• 4.再让left从左向右走，找到比key大的位置停下来，并将这个元素放到坑位，然后自己形成新的坑。
• 5.重复步骤3和步骤4，当left和right相遇的时候，把key的值放到当时的坑位。
  

整体步骤：

• 1.当单趟排序完成之后，用分治的思想将序列分为[left,key-1] key [key +1,right]三个子区间；
• 2.分别递归将[left,key-1] 和 [key +1,right]排序，如果分出的区间还不是有序，那就再分区间，进行递归，以此往复，直到待排子区间只有一个元素，则序列有序。

挖坑法代码

//交换
void Swap(int*p1,int*p2)
{
	int* tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//三数取中--为了解决我们key选择的数不是最大，也不是最小的
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) >> 1;
	if (a[left] < a[mid])//如果左小于中间
	{
		if (a[mid] > a[right])//如果左小于中间，中间大于右，则返回中间
		{
			return mid;
		}
		else if (a[left] > a[right])//如果左小于中间，左大于右，则返回左
		{
			return left;
		}
		else
		{
			return right;//如果左小于中间，中间大于右，则返回右
		}
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort1(int* a, int left, int right)
{
	int index = GetMidIndex(a, left, right);//三数取中
	Swap(&a[left], &a[index]);
	int begin = left, end = right;
	int pivot = begin;
	int key = a[begin];
	//单趟排序
	//单趟排序时间复杂度是O(N)-begin从左向右走，end从右向左走
	while (begin < end)
	{
		//右边找小，放到左边
		while (begin < end && a[end] >= key)
			--end;
		//小的放到左边的坑里，自己形成新的坑位
		a[pivot] = a[end];
		pivot = end;

		//右边找大
		while (begin < end && a[begin] <= key)
			++begin;
		//大的放到右边的坑里，自己形成新的坑位
		a[pivot] = a[begin];
		pivot = begin;
	}
	//把小的放到pivot的左边，大的放到pivot的右边后，把key的值放到数组pivot的位置
	pivot = begin;
	a[pivot] = key;

	//返回的是坑的位置
	return pivot;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	//挖坑法
	int keyIndex = PartSort1(a, left, right);
	//一趟之后把数组分段
	//[left,right]
	//[left,keyIndex-1] keyIndex [keyIndex +1,right]
	// 左子区间和右子区间有序，我们就有序了，如果让他们有序呢？ 分治递归
	
	//小区间优化，很明显发现，递归一段时间后，后面的几层会占用大部分的递归次数，所以引进了一个小区间优化算法
	//小区间优化，就是当递归进行到一定层数之后，后面几层改用其他排序的方法，冒泡，堆排序，希尔都是不行的，再考虑到剩下几层
	//的数据量也不大，就直接用插入排序
	if (keyIndex - 1 - left > 13)
	{
		QuickSort(a, left, keyIndex - 1);//递归pivot的左边
	}
	else
	{
		//这里小区间为什么是a+left？，因为我们如果右递归，数组肯定不是从大数组的首元素开始的
		InsertSort(a + left, keyIndex - 1 - left + 1);
		//这里的为什么是piovt-1-left+1？为什么要加1呢？--假如我们数组是[0,9]，这个数组里面是10个元素，而9-0等于9，所以加1
		//（pivot - 1 - left + 1）为什么减left和（a + left）是一样的意思
	}
	if (right - (keyIndex + 1) > 13)
	{
		QuickSort(a, keyIndex + 1, right);//递归pivot的右边
	}
	else
	{
		InsertSort(a + keyIndex +1, right-(keyIndex +1)+1);
	}
}
void TestQuickSort()
{
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
}

快速排序之左右指针法

单趟步骤：

• 1.先选出一个元素保存到key中，再定义两个指针left和right，left从左向右走，right从右向左走；
• 2.先让right从右向左走，找到比key小的位置停下，再让left从左向右找到比key大的位置停下，；
• 3.交换left和right位置的元素，然后继续让left向右走，right向左走重复步骤2和3；
• 4.当left和right相遇的时候停下来，将key保存的元素和相遇位置的元素交换。
  

整体步骤：

• 接下来的步骤和挖坑法的一样，分段并递归使其有序即可。

左右指针法代码

//交换
void Swap(int*p1,int*p2)
{
	int* tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//快速排序更进--三数取中 
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) >> 1;
	if (a[left] < a[mid])//如果左小于中间
	{
		if (a[mid] > a[right])//如果左小于中间，中间大于右，则返回中间
		{
			return mid;
		}
		else if (a[left] > a[right])//如果左小于中间，左大于右，则返回左
		{
			return left;
		}
		else
		{
			return right;//如果左小于中间，中间大于右，则返回右
		}
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
//左右指针法
int PartSort2(int* a, int left, int right)
{
	//三数取中
	int index = GetMidIndex(a, left, right);//为了解决我们key选择的数不是最大，也不是最小的
	Swap(&a[left], &a[index]);
	int begin = left, end = right;
	int keyi = begin;
	while (begin < end)
	{
		//从右到左找小
		while (begin<end && a[end]>=a[keyi])
		{
			--end;
		}
		//从左到右找大
		while (begin < end && a[begin] <= a[keyi])
		{
			++begin;
		}
		//begin是找大，end是找小，当两个循环跳出就是找到了，然后交换
		Swap(&a[begin], &a[end]);
	}
	//当begin和end相遇的时候，就停止循环，再将相遇位置和keyi交换就行了
	Swap(&a[begin], &a[keyi]);

	return begin;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	//左右指针法
	int keyIndex = PartSort2(a, left, right);
	if (keyIndex - 1 - left > 13)
	{
		QuickSort(a, left, keyIndex - 1);//递归pivot的左边
	}
	else
	{
		InsertSort(a + left, keyIndex - 1 - left + 1);
	}
	if (right - (keyIndex + 1) > 13)
	{
		QuickSort(a, keyIndex + 1, right);//递归pivot的右边
	}
	else
	{
		InsertSort(a + keyIndex +1, right-(keyIndex +1)+1);
	}
}
void TestQuickSort()
{
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	//递归
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
}

快速排序之前后指针法

单趟步骤：

• 1.先选出一个元素保存到key中，定义两个指针分别是prev和cur，分别指向序列首元素和prev后一个元素；
• 2.如果cur指向的元素小于key，prev和cur向后移动；
• 3.如果cur指向的元素大于key，则prev不动，cur继续后移找小，如果找到了，就将prev向后移动一位，并将移动后的位置的元素和cur指向的元素交换；
• 4.然后cur继续向后走，并重复步骤2和3；
• 5.如果cur走出序列，则将key保存的元素与prev指向元素交换即可。
  

整体步骤：

• 步骤和上面两个算法一样

前后指针法代码

//交换
void Swap(int*p1,int*p2)
{
	int* tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) >> 1;
	if (a[left] < a[mid])//如果左小于中间
	{
		if (a[mid] > a[right])//如果左小于中间，中间大于右，则返回中间
		{
			return mid;
		}
		else if (a[left] > a[right])//如果左小于中间，左大于右，则返回左
		{
			return left;
		}
		else
		{
			return right;//如果左小于中间，中间大于右，则返回右
		}
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
//前后指针法
//cur找小，每次遇到比keyi小的值就停下来，++prev，交换prev和cur位置的值，等到cur走出这个数组后，将prev位置的值和keyi的值交换
int PartSort3(int* a, int left, int right)
{
	//三数取中
	int index = GetMidIndex(a, left, right);//为了解决我们key选择的数不是最大，也不是最小的
	Swap(&a[left], &a[index]);
	int keyi = left;
	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		/*if (a[cur] < a[keyi])
		{
			++prev;
			Swap(&a[prev], &a[cur]);
		}*/
		if (a[cur] < a[keyi] && ++prev != cur)//这串代码与上面代码的区别就是防止自己和自己交换，浪费时间
		{
			++prev;
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	//前后指针法
	int keyIndex = PartSort3(a, left, right);
	if (keyIndex - 1 - left > 13)
	{
		QuickSort(a, left, keyIndex - 1);//递归pivot的左边
	}
	else
	{
		InsertSort(a + left, keyIndex - 1 - left + 1);
	}
	if (right - (keyIndex + 1) > 13)
	{
		QuickSort(a, keyIndex + 1, right);//递归pivot的右边
	}
	else
	{
		InsertSort(a + keyIndex +1, right-(keyIndex +1)+1);
	}
}
void TestQuickSort()
{
    int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
}

快速排序总结

• 为啥敢叫快速排序，因为它真牛批，1962年沿用到现在；
• 时间复杂度：O(N*logN)；
• 空间复杂度：O(logN)；
• 稳定性：不稳定 。

归并排序

归并排序思想

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。
基本思想： 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

代码

//归并排序
//假设左半区间有序，右半区间有序，归并，依次对比取小的放到新的临时数组，
//最后把左右两个区间中剩余数据的区间的所有拷贝到临时数组后面，再把临时数组中的数组拷贝到原数组
void _MergeSort(int* a, int left, int right,int* tmp)
{
	if (left >= right)
		return;
	int mid = (left + right) >> 1;//右移一位相当于除2
	//这时区间被分为[left,mid],[mid+1,right]
	//假设[left,mid],[mid+1,right]有序，那么我们就可以归并
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	//归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	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++];
	}
	//拷贝回去--把临时数组内的元素拷贝到原数组中
	for (int i = left; i <= right; ++i)
	{
		a[i] = tmp[i];
	}
}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}
void TestMergeSort()
{
	int a[] = { 10, 6, 7, 1, 3, 9, 4, 2 };
	//递归归并
	MergeSort(a, sizeof(a) / sizeof(int));
}

归并排序总结

• 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题；
• 时间复杂度：O(N*logN)；
• 空间复杂度：O(N)；
• 稳定性：稳定。

计数排序

计数排序思想

基本思想：通过统计数组中相同元素出现的次数，然后通过统计的结果将序列放回到原来的序列中。 是一种牺牲空间换时间的算法。 较为简单，看代码就能看懂😎。

代码

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 = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);//将开辟的数组初始化为0，也就是出现了0次

	//统计次数
	for (int i = 0; i < n; ++i)
	{
		count[a[i]-min]++;//相对映射
	}
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(count);
}
void TestCountSort()
{
	int a[] = { 10, 6, 7, 1, 3, 9, 4, 2, 10, 6, 7, 1, 3, 9, 4, 2 };
	CountSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

计数排序总结

• 计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，则会造成空间浪费，并且计数排序只适用于整型排序，不适用与浮点型排序；
• 时间复杂度O(2N+range)=O(N+range)；
• 空间复杂度O(range)。

排序算法复杂度及稳定性分析

结语

😊😊😊数据结构到这里算是基本完结了，接下来会将快速排序和归并排序的非递归写一下，后续有空会将串、广义表等更新出来。😚😚😚