数据结构（六）：排序（二）

今天药忘吃喽~ 2021-09-08 01:02 371阅读 0赞

### 文章目录 ###

*  前言
 *  一、快速排序
 *   *  1.单趟排序
     *   *  （1）左右哨兵法
         *  （2）挖坑法
     *  2.非递归实现快速排序
     *  3.优化：三数取中法
 *  二、归并排序
 *   *  1.递归
     *  2.非递归实现
 *  三、计数排序
 *  排序算法的比较
 *  感谢阅读，如有错误请批评指正

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

# 前言 #

在[数据结构（六）：排序（一）][Link 1]中介绍了直接插入排序、希尔排序、选择排序、堆排序和冒泡排序，本文继续介绍剩下的快速排序、归并排序和计数排序

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

# 一、快速排序 #

快速排序的基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值（单趟排序），然后左右子序列重复该过程（递归），直到所有元素都排列在相应位置上为止。

将区间按照基准值划分为左右两半部分的常见方式有左右哨兵法、挖坑法。

## 1.单趟排序 ##

以下的三种方法都是**对\[left,right\]的闭区间进行排序**，所以假设对n个元素的数组排序，传参时一定要使left=0,right=n-1。

### （1）左右哨兵法 ###

一般选择最左边的元素或最右边的元素做key，需要注意的是，**若选最左边的元素作为key，则需要right先寻找比a\[key\]小的元素**（下面的代码即是以最左边的元素作为key），**若选最右边的元素作为key，则需要left先寻找比a\[key\]大的元素**。

选最左边的元素作为key，则先从右边开始寻找比a\[key\]小的元素，找到后再从左边开始寻找比a\[key\]大的元素，找到后交换。重复寻找和交换直到left和right相遇，将相遇处meet\_i的元素与key位置的元素交换，则可达到meet\_i左边的元素都比a\[meet\_i\]小、meet\_i右边的元素都比a\[meet\_i\]大的目的。

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center]

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

//左右哨兵法
    int PartSort1(int* a, int left, int right)
    { 
    	//下面两行代码为优化，后文会讲到
    	int midIndex = GetMidIndex(a, left, right);
    	Swap(&a[left], &a[midIndex]);
    	
    	
    	int key_i = left;
    	while (left < right)
    	{ 
    		//right找小
    		//从右边开始寻找比a[key]小的元素
    		//注意先判断left < right，否则可能越界
    		//注意a[right] >= a[key_i]的等号，否则可能死循环
    		while (left < right && a[right] >= a[key_i])
    			right--;
    
    		//left找大
    		//再从左边开始寻找比a[key]大的元素
    		while (left < right && a[left] <= a[key_i])
    			left++;
    
    		Swap(&a[left], &a[right]);
    	}
    
    	//left == right
    	int meet_i = left;
    	Swap(&a[key_i], &a[meet_i]);
    
    	return meet_i;
    }
    
    void QuickSort(int* a, int left, int right)
    { 
    	//[left,right]区间内只剩一个或0个元素，即有序，不需要排
    	if (left >= right)
    		return;
    
    	int mid = PartSort1(a, left, right);
    	//mid位置已经是最终的位置，对[left,mid-1]和[mid+1,right]排序
    	QuickSort(a, left, mid - 1);
    	QuickSort(a, mid + 1, right);
    }

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

### （2）挖坑法 ###

选定最左边（最右边也可以，以左为例）为坑hole并保存a\[hole\]的值，right从右边开始找比a\[hole\]小的数，找到后用a\[right\]的值覆盖hole位置，并把hole改为right位置；left从左边开始找比a\[hole\]大的数，找到后用a\[left\]的值覆盖hole位置，并把hole改为right位置。循环直到left>=right，跳出循环后，设置left和right相遇的位置为meet\_i，将**最开始保存的a\[hole\]的值**覆盖meet\_i位置。单趟排序结束。  
![在这里插入图片描述][20210530153253248.gif_pic_center]

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

代码如下（示例）：

//挖坑
    int PartSort2(int* a, int left, int right)
    { 
    	//下面两行代码为优化，后文会讲到
    	int mid = GetMidIndex(a, left, right);
    	Swap(&a[left], &a[mid]);
    
    	int hole = left;//选定最左边为坑hole
    	int key = a[hole];//保存a[hole]的值
    	while (left < right)
    	{ 
    		while (left < right && a[right] >= key)//right从右边开始找比a[hole]小的数
    			right--;
    		a[hole] = a[right];//找到后用a[right]的值覆盖hole位置
    		hole = right;//把hole改为right位置
    
    		while (left < right && a[left] <= key)//left从左边开始找比a[hole]大的数
    			left++;
    		a[hole] = a[left];//找到后用a[left]的值覆盖hole位置
    		hole = left;//把hole改为right位置
    	}
    	a[hole] = key;//将最开始保存的a[hole]的值覆盖meet_i位置
    	return hole;
    }
    
    void QuickSort(int* a, int left, int right)
    { 
    	//[left,right]区间内只剩一个或0个元素，即有序，不需要排
    	if (left >= right)
    		return;
    
    	int mid = PartSort2(a, left, right);
    	//mid位置已经是最终的位置，对[left,mid-1]和[mid+1,right]排序
    	QuickSort(a, left, mid - 1);
    	QuickSort(a, mid + 1, right);
    }

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

## 2.非递归实现快速排序 ##

代码如下（示例）：

void QuickSortNonR(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 key = PartSort1(a, left, right);//得到key
    		
    		//左右区间出栈后子区间再入栈，子区间入栈后会一一对该区间排序
    		
    		//left和key - 1之间还有元素
    		if (left < key - 1)
    		{ 
    			StackPush(&st, left);
    			StackPush(&st, key - 1);
    		}
    
    		//key + 1之间和right之间还有元素
    		if (right > key + 1)
    		{ 
    			StackPush(&st, key + 1);
    			StackPush(&st, right);
    		}
    	}
    	StackDestroy(&st);
    }

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

## 3.优化：三数取中法 ##

当待排序的序列为递减数列时，是最坏的情况，快速排序的效率达到最低，每次选取的key都是最大值或者最小值，所以在right或left寻找时不发生交换，遍历整个区间，时间复杂度退化为O(N^2)。

通过三数取中法选出最左边、中间位置和最右边三个数中间的值，之后与key交换，当碰到上述情况时直接变成最好的情况。

代码如下（示例）：

//三数取中，逻辑简单，但实现起来较为复杂
    int GetMidIndex(int* a, int left, int right)
    { 
    	int mid = (left + right) >> 1;
    	// left mid 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 // a[left] > a[mid]
    	{ 
    		if (a[mid] > a[right])
    		{ 
    			return mid;
    		}
    		else if (a[left] < a[right])
    		{ 
    			return left;
    		}
    		else
    		{ 
    			return right;
    		}
    	}
    }

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

快速排序：

1.  快速排序整体的综合性能和使用场景都是比较好的，所以才叫快速排序
2.  **时间复杂度：O(N\*logN)**
3.  空间复杂度：O(logN)
4.  **稳定性：不稳定**

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

# 二、归并排序 #

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。若将两个有序表合并成一个有序表，称为二路归并。

## 1.递归 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 1]

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

代码如下（示例）：

void _MergeSort(int* a, int left, int right, int* tmp)
    { 
    	if (left >= right)
    		return;
    
    	//从中间分开，递归使左右两段区间有序
    	int mid = (left + right) >> 1;
    	_MergeSort(a, left, mid, tmp);
    	_MergeSort(a, mid + 1, right, tmp);
    
    	//左右两段区间已经有序，排序使整个区间有序
    	int begin1 = left, end1 = mid;//区间1
    	int begin2 = mid + 1, end2 = right;//区间2
    	int begin = begin1;
    	int i = begin1;//tmp的起点
    
    	//在两段区间中找小的值尾插
    	while (begin1 <= end1 && begin2 <= end2)
    	{ 
    		if (a[begin1] < a[begin2])
    			tmp[i++] = a[begin1++];
    		else
    			tmp[i++] = a[begin2++];
    	}
    
    	//把两个区间其中一个区间剩余的数据拷贝到tmp中，下面两个循环只走一个
    	while (begin1 <= end1)
    		tmp[i++] = a[begin1++];
    	while (begin2 <= end2)
    		tmp[i++] = a[begin2++];
    
    	//归并结束，把tmp中对应位置的数据全部拷贝回a数组
    	for (i = begin; i <= end2; i++)
    		a[i] = tmp[i];
    }
    
    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);
    }

## 2.非递归实现 ##

代码如下（示例）：

void MergeSortNonR(int* a, int n)
    { 
    	int* tmp = (int*)malloc(sizeof(int)* n);
    	int i = 0, gap = 1;//每组gap个元素
    	while (gap < n)
    	{ 
    		for (i = 0; i < n; i += 2 * gap)
    		{ 
    			int begin1 = i, end1 = i + gap - 1;//区间1
    			int begin2 = i + gap, end2 = i + 2 * gap - 1;//区间2
    			
    			//第二个小组的开头就超出数组范围，说明数组中只有第一个小组，而第一个小组已经是排好序的，直接退出
    			if (begin2 >= n)
    				break;
    			
    			//第二个小组末尾超出数组范围，修正它的末尾保证不越界
    			if (end2 >= n)
    				end2 = n - 1;
    
    			//合并两个已经有序的区间
    			int begin = begin1;
    			int i = begin1;//tmp的起点
    		
    			//在两段区间中找小的值尾插
    			while (begin1 <= end1 && begin2 <= end2)
    			{ 
    				if (a[begin1] < a[begin2])
    					tmp[i++] = a[begin1++];
    				else
    					tmp[i++] = a[begin2++];
    			}
    		
    			//把两个区间其中一个区间剩余的数据拷贝到tmp中，下面两个循环只走一个
    			while (begin1 <= end1)
    				tmp[i++] = a[begin1++];
    			while (begin2 <= end2)
    				tmp[i++] = a[begin2++];
    		
    			//归并结束，把tmp中对应位置的数据全部拷贝回a数组
    			for (i = begin; i <= end2; i++)
    				a[i] = tmp[i];
    		}
    		gap *= 2;
    	}
    }

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

归并排序：

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

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

# 三、计数排序 #

统计相同元素出现次数，根据统计的结果将序列回收到原来的序列中。

![在这里插入图片描述][20210530163612458.gif_pic_center]

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

代码如下（示例）：

void CountSort(int* a, int n)
    { 
    	int max = a[0], min = a[0];
    	int i, j;
    
    	//找到最大值、最小值
    	for (i = 0; i < n; i++)
    	{ 
    		if (a[i] > max)
    			max = a[i];
    		if (a[i] < min)
    			min = a[i];
    	}
    
    	int* count = (int*)malloc(sizeof(int)* n);//辅助空间
    	memset(count, 0, sizeof(int) * n);
    	int range = max - min + 1;//最大的数据和最小的数据的跨度
    	for (i = 0; i < n; i++)
    		count[a[i] - min]++;
    	
    	i = 0;
    	for (j = 0; j < range; j++)
    	{ 
    		while (count[j]--)
    			a[i++] = j + min;
    	}
    
    	free(count);
    }

计数排序：

1.  **计数排序在数据范围集中时，效率很高，但是适用范围及场景有限**。
2.  时间复杂度：O(MAX(N,范围))
3.  空间复杂度：O(范围)
4.  稳定性：稳定

# 排序算法的比较 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 2]

# 感谢阅读，如有错误请批评指正 #

[Link 1]: https://blog.csdn.net/weixin_51983604/article/details/117135113?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center]: /images/20210813/239db7c5ea4543bb9a328fb92d79d906.png
[20210530153253248.gif_pic_center]: /images/20210813/7873cfd0605e4bd9a3efddde00d47b25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210813/aa0a3b56b7c4477a80c16b5b088e6324.png
[20210530163612458.gif_pic_center]: /images/20210813/e44636d594d340beb305fde2f61c7cc7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTk4MzYwNA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210813/f50395534dc04655a5b253071d9fd2eb.png