【数据结构】一文带你全面了解排序（下）——冒泡排序、快速排序、归并排序、计数排序

朴灿烈づ我的快乐病毒、 2023-10-13 22:23 14阅读 0赞

**目录**

一、常见排序算法的实现

1.1 交换排序

1.1.1 基本思想

1.1.2 冒泡排序

1.1.3 快速排序

1.2 归并排序

1.3 非比较排序

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

--------------------

人总得为过去的懒惰而付出点代价！

--------------------

## 一、常见排序算法的实现 ##

### 1.1 交换排序 ###

#### 1.1.1 基本思想 ####

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

#### 1.1.2 冒泡排序 ####

详细内容见：[冒泡排序链接][Link 1]

冒泡排序：

void BubbleSort(int* a, int n)
    {
    	for (int i = 0; i < n - 1; i++)//趟数
    	{
    		int end = n - i - 1;
    		for (int j = 0; j < end; ++j)//交换次数
    		{
    			if (a[j] > a[j + 1])
    			{
    				Swap(&a[j], &a[j + 1]);
    			}
    		}
    	}
    }

冒泡排序优化：【当第一趟进行交换的时候，没有进行交换，说明数组是有序的，那么就不需要进行后面几趟的冒泡了】

void BubbleSort(int* a, int n)
    {
    	for (int i = 0; i < n - 1; i++)//趟数
    	{
    		int exchange = 0;
    		int end = n - i - 1;
    		for (int j = 0; j < end; ++j)//交换次数
    		{
    			if (a[j] > a[j + 1])
    			{
    				exchange = 1;
    				Swap(&a[j], &a[j + 1]);
    			}
    		}
    		if (exchange == 0)
    		{
    			break;
    		}
    	}
    }

**把直接插入排序和优化后的冒泡排序进行比较**： 如果顺序是有序的，两者是一样的；但是，如果是局部有序，或者接近有序，那么插入适应性和比较次数更少

> 1. 冒泡排序是一种非常容易理解的排序
> 
> 2. 时间复杂度：O(N^2)
> 
> 3. 空间复杂度：O(1)
> 
> 4. 稳定性：稳定

#### 1.1.3 快速排序 ####

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：**任取待排序元素序列中****的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右****子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止**。

--------------------

> 单趟排序：选出一个key，一般是第一个数或者是最后一个数，排序之后要求左边的值都比key小，右边的值都比key大

将区间按照基准值划分为左右两半部分的常见方式有（单趟排序）：

（1）**hoare版本（霍尔）**

> **key在左边（**第一个数**）**
> 
> 先右边的right找比key小的数据，找到就停止，然后左边的left找比key大的数据，找到就停止，然后进行交换数据，一直到left和right相遇，将该位置的值和key进行交换
> 
> 【因为，交换完之后【left是小的】，右面先走，所以相遇的位置一定是比key小的数字】
> 
> 【相遇的情况只有两种，left主动和right碰面和right主动和left碰面，这两种情况，都是在比key小的位置停下来】

> **key在右边（**最后一个数**）**
> 
> 先左边的left找比key大的数据，找到就停止，然后右边的right找比key小的数据，找到就停止，然后进行交换数据，一直到left和right相遇，将该位置的值和key进行交换
> 
> 【因为，交换完之后【left是小的】，左面先走，所以相遇的位置一定是比key大的数字】
> 
> 【相遇的情况只有两种，left主动和right碰面和right主动和left碰面，这两种情况，都是在比key大的位置停下来】

**代码1展示**：

void PartSort1(int* a, int left, int right)
    {
    	int keyi = left;
    	while (left < right)
    	{
    		while (left < right && a[right] >= a[keyi])
    			right--;
    		while (left < right && a[left] <= a[keyi])
    			left++;
    		Swap(&a[left], &a[right]);
    	}
    	Swap(&a[left], &a[keyi]);
    }

> 细节问题：（1）【key在左面】如果right在走得时候，遇到左面的数字一直小于等于key，就会一直--，就会越界，所以加上left<right

**（2）挖坑法**

> **key在左边（**第一个数**）**
> 
> 边首先，把key值保存，然后这个位置成为一个坑位，然后右边的right找比key小的数据，找到就填补坑位，此时右面的right形成一个坑位，需要左面的left找比key大的数据，找到后填补右面的坑位，一直到left和right相遇，然后key填补相遇时的坑位【左边做坑，右边先走；右边做坑，左边先走】
> 
> **key在右边（**最后一个数**）也同理**

> 和hoare相比，代码几乎一样，但是容易理解：（1）不用理解为什么相遇位置比key小（2）不需要理解左边做key，右边先走

**代码2展示**：

int PartSort2(int* a, int left, int right)
    {
    	int key = a[left];
    	int pit = left;
    	while (left < right)
    	{
    
    		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）前后指针法**

> **key在左边（**第一个数**）**
> 
> 两个指针，一个prev，一个cur。刚开始 prev在keyi的位置，cur在keyi的下一个位置;cur找小，如果找到prev++,并交换prev和cur的值；【如果cur和prev++在同一个位置，就没有交换数据的必要：如果cur的第一个位置就是比key小，那么需要prev++,然后交换位置，但是在同一个位置，就没有必要】【while(cur <= right)】

> prev和cur的关系：（1）cur还没有遇到比key大的值，prev紧跟cur，一前一后（2）cur遇到比key大的值，prev和cur之间间隔着一段比key大的值的区间。

代码3展示：

int PartSort3(int* a, int left, int right)
    {
    	int key = a[left];
    	int prev = left;
    	int cur = left + 1;
    	while (cur <= right)
    	{
    		if (a[cur] < key && a[cur] != a[++prev])//这个条件，只有前面条件符合才会走后面的条件
    		{
    			Swap(&a[cur], &a[prev]);
    		}
    		cur++;
    	}
    	Swap(&a[left], &a[prev]);//这里不能写&key，因为并不能改变a[left]的值，不要和局部变量交换
    	return prev;
    }

> **key在右面（最后**一个数**）**
> 
> 两个指针，一个prev，一个cur。刚开始 prev在left-1的位置，cur在left;cur找小，如果找到prev++,并交换prev和cur的值；【如果cur和prev++在同一个位置，就没有交换数据的必要：如果cur的第一个位置就是比key小，那么需要prev++,然后交换位置，但是在同一个位置，就没有必要】【while (cur <= right - 1】

int PartSort4(int* a, int left, int right)
    {
    	int key = a[right];
    	int prev = left - 1;
    	int cur = left;
    	while (cur <= right - 1)
    	{
    		if (a[cur] < key && a[cur] != a[++prev])//这个条件，只有前面条件符合才会走后面的条件
    		{
    			Swap(&a[cur], &a[prev]);
    		}
    		cur++;
    	}
    	Swap(&a[right], &a[++prev]);//这里不能写&key，因为并不能改变a[left]的值，不要和局部变量交换
    	return prev;
    }

--------------------

> 整体排序：单趟排序之后，key已经放在正确的位置，不需要进行移动，此时只要保证左边有序，右面有序，就可以保证整体有序了【分治解决子问题】

代码展示：（hoare单趟排序+分治整体排序）

//快速排序
    
    int PartSort(int* a, int left, int right)
    {
    	int keyi = left;
    	while (left < right)
    	{
    		while (left < right && a[right] >= a[keyi])
    			right--;
    		while (left < right && a[left] <= a[keyi])
    			left++;
    		Swap(&a[left], &a[right]);
    	}
    	Swap(&a[left], &a[keyi]);
    	return left;
    }
    
    void QuickSort(int* a, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int keyi = PartSort(a, begin, end);
    	QuickSort(a, begin, keyi - 1);
    	QuickSort(a, keyi + 1, end);
    }

> 1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫**快速**排序
> 
> 2. 时间复杂度：O(N\*logN) 每次调用快速排序，都需要把所有元素进行遍历一遍
> 
> 最好的情况：每次选key都是中位数O(N\*logN) 最差的情况：每次选key都是最大的数字或者最小的数字O(N^2) \[有序或者接近有序\]
> 
> 3. 空间复杂度：O(logN)
> 
> 4. 稳定性：不稳定

--------------------

**快速排序优化**

> 因为最坏的情况，所以可以对key进行优化，让key不是最大或者最小的数字：（1）随机选key（2）三个数字选不大也不小的那个数字，然后这个数字和left或者right位置的数据进行交换。

代码展示：

int GetMinIndex(int* a, int left, int right)
    {
    	int mid = left + (right - left) / 2;
    	if (a[left] < a[mid])
    	{
    		if (a[right] > a[mid])
    		{
    			return mid;
    		}
    		else if (a[left] > a[right])
    		{
    			return left;
    		}
    		else
    		{
    			return right;
    		}
    	}
    	else
    	{
    		if (a[mid] > a[right])
    		{
    			return mid;
    		}
    		else if (a[right] > a[left])
    		{
    			return left;
    		}
    		else
    		{
    			return right;
    		}
    	}
    }
    
    int PartSort1(int* a, int left, int right)
    {
    	int midi = GetMidIndex(a, left, right);
    	Swap(&a[left], &a[midi]);
    	int keyi = left;
    	while (left < right)
    	{
    		while (left < right && a[right] >= a[keyi])
    			right--;
    		while (left < right && a[left] <= a[keyi])
    			left++;
    		Swap(&a[left], &a[right]);
    	}
    	Swap(&a[left], &a[keyi]);
    	return left;
    }

> 小区间优化：区间很小时，不再使用递归划分的思路，而是直接使用插入排序对小区间进行排序，减少递归调用

void QuickSort(int* a, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	if (end - begin + 1 <= 10)
    	{
    		InsertSort(a + begin, end - begin + 1);
    	}
    	else
    	{
    		int keyi = PartSort1(a, begin, end);
    		QuickSort(a, begin, keyi - 1);
    		QuickSort(a, keyi + 1, end);
    	}
    }

--------------------

**快速排序非递归（栈）**

void QucikSort(int* a, int begin, int end)
    {
    	ST 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 = PartSort(a, left, right);
    		if (left < keyi - 1)
    		{
    			StackPush(&st, left);
    			StackPush(&st, keyi -1);
    		}
    		if (right > keyi + 1)
    		{
    			StackPush(&st, keyi - 1);
    			StackPush(&st, right);
    		}
    	}
    	StackDestory(&st);
    }

> 递归改成非递归：（1）用循环（2）用栈【递归会有爆栈的风险】

### 1.2 归并排序 ###

先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表【先让左右区间有序，再对两个区间归并】

--------------------

一个数组分成左右两个数组，假设数组有序，两个有序数组，归并成一个有序数组。（取两个数组中小的数据，依此尾插到新的数组），但是这个数组是无序的，所以把数组一直分，一直分到一个数据或者没有数据，就可以认为是有序的，然后依次合并，然后这个数组就是有序的。【先分再合并】

代码展示：【递归】

void _MergeSort(int* a, int begin, int end, int* tmp)
    {
    	if (begin >= end)
    	{
    		return;
    	}
    	int mid = (begin + end) / 2;//中间值
    	_MergeSort(a, begin, mid, tmp);//左边有序
    	_MergeSort(a, mid + 1, end, tmp);//右边有序
    	int begin1 = begin;
    	int end1 = mid;
    	int begin2 = mid + 1;
    	int end2 = end;
    	int index = begin;
    	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, sizeof(int) * (end - begin + 1));
    }
    
    void MergeSort(int* a, int n)
    {
    	int* tmp = (int*)malloc(sizeof(int) * n);
    	if (tmp == NULL)
    	{
    		printf("malloc fail\n");
    		exit(-1);
    	}
    	_MergeSort(a, 0, n - 1, tmp);
    	free(tmp);
    	tmp = NULL;
    }

> （1）mid等于（第一个数据的下标+最后一个数据的下标）/2，分成的两个区间应该是【left，mid】【mid+ 1, right】,否则就会出现死循环。
> 
> （2）分割完再合并，分割完分别调用合并排序， 合并排序写在调用后面。【分割的两个数组都有序之后，再合并】【函数主框架，左面有序+右面有序+合并】
> 
> （3）归并完再把内容复制到原来的数组里。【归并的时候需要新的数组】
> 
> （4）类似于后序遍历

> 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
> 
> 2. 时间复杂度：O(N\*logN) N个数据，logN层
> 
> 3. 空间复杂度：O(N) 时间复杂度是O(N + logN) 但是 logN可以忽略不计
> 
> 4. 稳定性：稳定

代码展示：【非递归】

//归并排序
    //非递归
    void MergeSort2(int* a, int n)
    {
    	int* tmp = (int*)malloc(sizeof(int) * 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;
    			if (end1 >= n)
    				end1 = n - 1;
    			if (begin2 >= n)
    			{
    				begin2 = n;
    				end2 = n - 1;
    			}
    			// begin2没有越界， end2越界，修正end2即可
    			if (begin2 < n && end2 >= n)
    				end2 = n - 1;
    
    			int index = i;
    			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, tmp, n * sizeof(int));
    		gap *= 2;
    	}
    	free(tmp);
    }

> 首先gap为1进行归并，此时2个数据一组是有序的，然后gap = gap\*2 = 2,判断gap是否>=n, 然后gap为2进行归并，此时4个数据一组是有序的，然后gap = gap\*2 = 4判断gap是否>=n,然后gap为4进行归并……直到gap>=n的时候结束【gap是多少，就多少一组进行合并】

> **越界问题:**begin1是不可能越界的（begin1是等于i的，i又是小于n的）end1、begin2、end2是可能越界的
> 
> (1)只有end2越界，进行修正，n-1
> 
> （2）begin2越界，那么end2也越界，此时归并的第二组数据都越界，那么begin2和end2就不需要修正，那么第二组区间不存在
> 
> （3）end1越界，进行修正，那么第二组区间不存在即可

> 时间复杂度：O(N\*logN) 空间复杂度：O(N)

> **调试小技巧：**
> 
>     // 条件断点
>     			if (begin1 == 8 && end1 == 9 && begin2 == 9 && end2 == 9)
>     			{
>     				int x = 0;
>     			}
> 
> 当我们想要在某一个地方停止，但是比较麻烦，可以直接写一个条件断点，然后打一个断点即可

### 1.3 非比较排序 ###

**比较排序**：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序

**非比较排序**：（1）计数排序（2）基数排序、桶排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

计数排序代码展示：

void CountSort(int* a, int n)
    {
    	int min = a[0];
    	int max = a[0];
    	for (int i = 1; i < n; i++)
    	{
    		if (a[i] < min)
    			min = a[i];
    		if (a[i] > max)
    			max = a[i];
    	}
    	int range = max - min + 1;
    	int* countA = (int*)malloc(sizeof(int) * range);
    	if (countA == NULL)
    	{
    		printf("malloc fail\n");
    		exit(-1);
    	}
    	memset(countA, 0, sizeof(int) * range);
    	for (int i = 0; i < n; i++)
    	{
    		countA[a[i] - min]++;
    	}
    	int j = 0;
    	for (int i = 0; i < range; i++)
    	{
    		while (countA[i]--)
    		{
    			a[j++] = i + min;
    		}
    	}
    }

> 首先找出数据的最大值的最小值，然后相减+1算出新数组的大小，然后新数组的值都赋值为0，然后遍历以前的数组，遍历的数字-min，就是新数组的下标，这个下标里面的值就+1，遍历完以前的数组之后，再把新的数组的值再返回以前的数组即可

> 1. 计数排序**在数据范围集中时**，效率很高，但是适用范围及场景有限。（适用于数据范围集中）（适用于整数，负数也可以，其他类型不可以）
> 
> 2. 时间复杂度：O(MAX(N,范围))
> 
> 3. 空间复杂度：O(范围)
> 
> 4. 稳定性：稳定

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

![727d21ae8dc14233a4302d0f722304f6.png][]

![4f17b3d419304413b1a4df266924f8f5.png][]

[Link 1]: http://t.csdn.cn/ml7Uv
[727d21ae8dc14233a4302d0f722304f6.png]: https://img-blog.csdnimg.cn/727d21ae8dc14233a4302d0f722304f6.png
[4f17b3d419304413b1a4df266924f8f5.png]: https://img-blog.csdnimg.cn/4f17b3d419304413b1a4df266924f8f5.png