八大排序（下）冒泡、快排、归并、计数

这里是八大排序的下篇

其他的四个排序在这篇博客：

一、冒泡排序

前言：冒泡排序我们可谓是在熟悉不过了，第一个学会的排序就是冒泡，还记得当初刚学C语言的时候，完全不会冒泡排序，都是借鉴书上的或者别人的代码写的，知道是怎么个事，但是无从下手，好不容易写出来，不是这里错就是那里错，还挺怀念那个时候的，当然你无法同时拥有青春和对青春的感悟！话不多说，我们进入正题。

冒泡排序的思想是从左到右逐个比较，如果左边的值必右边的值要大，那么我们两个就交换位置，再继续往后面比较，如果左边的值必右边的值要小，那么我的就变成了你，再往后面比较，直到到达了末尾。

这个步骤说白了就是遍历数组，将大的值往后面放。

冒泡排序代码实现 

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		bool flag = false;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				swap(a[j], a[j + 1]);
				flag = true;
			}
		}
		if (flag == false)
			break;
	}
}

这里需要注意的地方就是对于j的控制，因为我们一趟可以将最大的值放在最后面，因此我们后续的排序就不要管放在最后面的值， 每一趟排序都会让我们多少一次比较，因此写出   j < n - i - 1  这样的代码。

同时为了处理有序数组无需再次排序的问题，我们引入了flag，如果一趟排序完成后flag没有变化，就证明了目前的数据是有序的，因此直接break就好。但如果不是这种有序情况冒泡排序的时间复杂度是O(n^2)。

二、快速排序

不知道大家冒泡排序这块甜点吃得咋样了，现在要上一点点强度啦！！！

快速排序是一个自负的小伙子，他竟然敢直接以快速命名，有点嚣张的小伙子，让我们看看他是怎么个事。

1.霍尔法

快速排序的主要思想是找到某一个key（key我们可以随便选）该放在的位置，并使得key的左边都比他小，key的右边都比他大即可。

我们直接上图 

就如上图所言，我们拍一次序后变成了下面这样

保证了 key（6）这个位置的合理性，到这里我们就可以通过递归的方式，又分别处理它的左边和右边 ，直到保证数组有序。

那么现在我们该如果使得他变成上面这个样子呢？

我们可以发现，当左为key的时候，我们让右边找比key小的，找到后停止，继续让左边找比Key大的，如果找到后，左右两个值还没相遇，我们就交换这样就保证了左边存的是比key小的，右边存的是比key大的，直到最后相遇时，再将key和相遇点交换即可。

那么问题又来了，为什么左边为key要从右边先出发呢？ 我们举个例子

找到后交换 

再次寻找 

再次交换 

到这里问题就出现了，你说我现在是左边先走还是右边先走呢？

右边先走找比key小，因此找到了4，然后左边走，走到4后left==right因此循环结束，将5和4交换，完美，没问题！

左边先走找比key大，因此找到了6，同时此时left==right 循环也结束了，完了，5和6交换位置不对了 ，寄了！

为了避免出现这种情况，我们选择key在一侧，就另一侧先走。

下面我们上代码（注：代码选择的是右边为key）

int PartSort1(int* a, int left, int right)
{
	int key = right;
	while (left < right)
	{
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		swap(a[left], a[right]);
	}
	swap(a[left], a[key]);
	return left;
}

 当然，这只是一趟的过程，我们还要递归他，去找他的左和右。

下面是递归代码

void QuickSort(int* a, int left, int right)
{
	if (right - left < 1)
	{
		return;
	}
	int key = PartSort2(a, left, right);
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

这是一种实现，也是快排之父霍尔的思路，后续基于快排的思想，又产生了  挖坑法、前后指针法

让我们继续学习吧

2.挖坑法

挖坑法思想：先定一个坑，并保存坑里的值，最左边或者最右边都可以，依然是右边找比他小的，找到后就将这个值放到上一个坑中，又将这个值设置为坑，再让左边去找比他大的，找到后依然放到坑中，这个位置又变为坑。重复循环，直到左右见面即可。

挖坑法无需左为坑右先走，因为他每找到一个就会将自己的值赋给坑，不会发生错过的现象。 

 

代码如下 ，并没有发生交换操作，只有赋值操作。

//挖坑法，默认第一个为坑，前面往后走找到比他大的，
//后面往前走找到比他小的   找到就把值给之前的坑
//现在这个位置又形成新的坑，直到结束循环，再把最开始的坑给到最后的坑
int PartSort2(int* a, int left, int right)
{
	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;
	}
	a[hole] = key;
	return hole;
}

3.前后指针法

 前后指针法思想：他是一个翻跟斗的思想，目的是将大的往后面翻，也是先找最左为key，初始化时prev在当前key的位置，cur在下一个位置，如果cur遇到比key大的，cur就++，这样便会和prev拉开差距，如果cur比prev只大一个，证明他们差距是1，因此就是初始化的差距，中间没有比key大的值，无需交换，prev和cur都++，如果差距不为1，就将cur与prev的下一个进行交换，就让中间这些大个子的往后面走。

具体代码如下 

int PartSort3(int* a, int left, int right)
{
	int cur = left + 1;
	int prev = left;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] < key && ++prev != cur)
		{
			swap(a[prev], a[cur]);
		}
		++cur;
	}
	swap(a[left], a[prev]);
	return prev;
}

这里用得很巧如果   ++prev != cur  我才需要交换（因为距离大于1了）同时还把prev给自加了

然后cur是每一次都需要自加的，这样就开始动起来了。

4.快速排序非递归

因为递归可能会导致栈溢出的问题，因此如果差距不大，能不适用递归最好就不要用递归（虽然他真得很简单，我真的喜欢）。

非递归的思想可以用栈和队列来处理，用栈就是深度优先，用队列就是广度优先，这里我们选择使用栈来处理。先将left和right入栈，再取出来left和right，然后使用前面的三个方法去处理，返回key元素该放的位置，再将left和key-1入栈，和right和key+1入栈，模拟递归的方法，直到left>=right就证明这段区间有序不需要在入栈了。

下面是代码

void QuickSortNonR(int* a, int left, int right)
{
	stack<int> st;
	st.push(left);
	st.push(right);
	while (!st.empty())
	{
		int end = st.top();
		st.pop();
		int begin = st.top();
		st.pop();
		if (begin >= end)
		{
			continue;
		}
		int key = PartSort1(a, begin, end);
		st.push(key + 1);
		st.push(end);
		st.push(begin);
		st.push(key - 1);
	}
}

但是，如果数组是有序的情况下，快速排序的时间复杂度会成为O(n^2)，因为排序一次你的left或right会移动到最末尾，递归起来有一边全是数据，有一边一个数据都没有，这就类似于单叉树或者链表的形状，会变得很慢很慢。

从上图可以看出来，快排去排序有序数组，甚至会比选择排序还慢，属于跟狗一桌了。因此我们需要优化一下它。

这里我们选择使用三数取中的方法，

int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	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 midi = GetMidIndex(a, left, right);
	swap(a[right], a[midi]);

将key的位置和midi的位置交换一下，防止最坏结果，便可加快有序数组的排序速度

处理之后，快排速度直线上升！！！ 

到此我们快速排序就算了结了。

三、归并排序

这又是一个硬菜，我们慢慢来！

1.递归版归并排序

归并排序是采用的分治的思想。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

先两个两个有序，在四个四个有序，一直到全局有序。

局部有序是将两个局部看成两个数组，两个有序数组合并为一个新的有序数组，再将这个有序数组和另外一个有序数组再次合并，直到合并完所有元素。

这需要借助一个size跟原数组一样大的数组来完成拷贝过程，并可以使用memcpy来进行拷贝。 归并排序也可以通过递归来实现

代码如下

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
 
void MergeSort(int* a, int n)
{
	int* tmp = new int[n];
	_MergeSort(a, 0, n - 1, tmp);
	delete[] tmp;
}

归并排序的思路跟这道力扣题一模一样88. 合并两个有序数组

 2.非递归版归并排序

因为递归对于栈的压力很大，因此奶奶常说能不用递归最好就不要使用递归，我们尝试着不用递归处理它，首先分析栈和队列合不合适，可以发现栈和队列的是适合一直做减法，由一个较大的数值往小了走，但是归并排序需要合并起来，因此栈和队列不合适，我们只能选择尝试while能否处理

首先定义gap，gap为左右两组每一组的个数，如果先将gap定为1，便可以实现将两个sz为1的数组合并起来，形成一个sz=2的有序数组  再通过   gap*=2   通过while循坏控制这个gap，便可达到两两合并，四四合并，直到合并完整个数组。

代码如下

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int gap = 1;
	int* tmp = new int[n];
	int j = 0;
	while (gap<n)
	{
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
		}
		j = 0;
		memcpy(a, tmp, sizeof(int)* n);
		gap *= 2;
	}
 
}

好像我们的代码看起来没啥问题，我们运行一下

OK ，完美，完美地将数组排好序了。

但是，哥哥们，有大坑啊 

当我们arr的长度不再为   n^2  时，便出现了数据越阶的问题我们画个图来看看

数据为9时 第一次归并就出现了问题，我们很简单就可以想到 这个代码只适合 长度为 n^2  这一种情况，因此我们的再做修改。

我们尝试观察哪个地方会越界

int begin1 = i, end1 = i + gap - 1;     // i<n  因此begin1不会越阶
int begin2 = i + gap, end2 = i + 2 * gap - 1;

除开begin1外，其他都有可能会越界 

end1和begin2不越界时，我们就正常排序，当越界时，我们选择直接break跳出循环，后面的无需处理，等着后面再将这个部分与前面所有的排好序数组再次归并即可。

但是我们代码中还是有问题     memcpy(a, tmp, sizeof(int)* n);  每一次都讲整个数据全部拷贝，是不够合理的，因为break后，tmp数组会缺失数据，我们可以选择归并一部分，就拷贝一部分，防止之前break后出现数据丢失的问题。因此可以将  memcpy   放到for循环内部。

因为end2不会改变，因此可以将sz修改成

memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));

但是当end2越界时，上面这句代码也会出现问题，于是我们在循环中判断一下  

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

  我们修正end2为n-1即可，终于将坑填完了

写出如下代码

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int gap = 1;
	int* tmp = new int[n];
	int j = 0;
	while (gap<n)
	{
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
		}
		j = 0;
		gap *= 2;
	}
}

终于将sz不等于n^2处理好了！！！

艰难的归并排序非递归版就完成了！

归并排序的时间复杂度是O(n*logn),跟有无序无关。

 四、计数排序

计数排序通常使用的很少，但是在某些特定的条件下很好用，比如数组是一段非常密集的重复数组，也就是数据很多重复且数组的  max-min   范围很小。

他的思想是先遍历一遍数组，找出最大值和最小值，并相减，然后开辟一个 max-min 大小的空间，用这块空间去统计原数组的值出现的次数，最后再拷贝到原数组中。

代码如下：

void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (min > a[i])
		{
			min = a[i];
		}
		if (max < a[i])
		{
			max = a[i];
		}
	}
	int range = max - min + 1;
	int* count = new int[range];
	memset(count, 0, range * sizeof(int));
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int k = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[k++] = i + min;
		}
	}
}

用得很少，思路不也难，非主流排序。

总结

希望大家能够点点赞，求求。