[八大排序]0基础C语言实现八大排序，详解快排，归并，希尔

冷不防 2022-09-12 03:52 12阅读 0赞

### 八大排序 ###

*  前言
 *  一、冒泡排序
 *   *  1.复杂度，稳定性分析
 *  二、插入排序
 *   *  2.复杂度，稳定性分析
 *  三、选择排序
 *   *  3.复杂度，稳定性分析
 *  四、希尔排序（ 缩小增量排序）
 *   *  4.复杂度，稳定性分析
 *  五、快排
 *   *  1.1. hoare版本
     *  2.1 挖坑法
     *  3.1 前后指针版本
     *   *  三数取中
 *  4. 快排代码
 *   *  5.复杂度，稳定性分析
 *  六、归并排序
 *   *  递归实现：
     *  迭代实现：
     *  5.复杂度，稳定性分析
 *  七、堆排
 *   *  7.复杂度，稳定性分析
 *  八、计数排序
 *   *  8.复杂度，稳定性分析
 *  九、归并排序外排序使用
 *  总结

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

# 前言 #

> 排序是啥？哪个排序最优？  
> 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

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

# 一、冒泡排序 #

> 大家应该最早接触的排序就是冒泡排序，以升序为例，每一趟的冒泡排序都是把一个最大的数放到最后面，其中 a\[i-1\]>a\[i\],我们将i-1,i的值进行交换。  
> 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

![在这里插入图片描述][3a040ece5e6845d1875a99171c174e70.gif]

> 观察上面动图，总结规律，我们可以发现一次冒泡排序两两交换之后可以把一个最大的数冒到最后面，那么我们要进行多少次冒泡排序才能将一组数据排好呢：n-1次，因为我们排到n-1的时候，最后一个数据也已经在他该在的位置啦！！  
> 难点：这里的n是元素和，最后一个元素的下标是n-1

void BubbleSort(int* a, int n)
    { 
    	//冒泡排序，升序为例 
    	int end = n - 2 ;
    	//end == n-2的时候是排好n-1位置的值，我们要排好最后排好下标为1的值，则0位置自然就是最小的
    	while (end >= 0)
    	{ 
    //n个数一次冒泡将一个数冒到最后，则需要n-1次
    		int i = 0;
    //当一次排序一个数都没交换即已经有序，跳出循环
    
    		int flag = 0;
    		while (i <= end)
    		{ 
    			//一次排序
    			if (a[i] > a[i + 1])
    			{ 
    				Swap(&a[i], &a[i + 1]);
    				flag = 1;
    			}
    			i++;
    		}
    		if (flag == 0)
    			break;
    
    		end--;
    	}
    }

## 1.复杂度，稳定性分析 ##

冒泡排序的空间复杂度O（1），时间复杂度是O(N^2),但是在加入裁剪之后的冒泡排序在接近有序的时候效率是可以达到O（N），并且两两交换的特性保证两个相同的值无论如何排序，都是保持顺序的，所以冒泡排序是稳定的。

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

# 二、插入排序 #

大家都玩过扑克牌吧，我们在整理牌的时候就可以以一个牌为中心，让后面比他大的牌往他的前面放，反之。  
![在这里插入图片描述][03851b7489b846cfa71090650ae7d8f5.gif]  
观察上图，总结规律，插入排序的思想就是在已经有序的一段区间中一次插入一个值，所以第一次我们以下标为0的数据可以当成一个有序区间，将下标为1的数往有序区间插入，同理后面n-1张牌都是这样处理。

void InsertSort(int* a, int n)
    { 
    	//排升序
    	for (int i = 0; i <= n - 2; i++) { 
    		//这里的end范围[0,n-2]，数组倒数第二个元素
    		int end = i ;
    		int tmp = a[end + 1];
    		while (end >= 0)
    		{ 
    			//当前end的值比tmp小都要往后移动
    			if (a[end] > tmp)
    			{ 
    				a[end + 1] = a[end];
    			}
    			else
    			{ 
    				break;
    			}
    			--end;
    		}
    		//两种情况出来的都可以在end后面这个位置放
    		a[end + 1] = tmp;
    	}
    }

## 2.复杂度，稳定性分析 ##

插入排序对比冒泡排序，他的时间复杂度也是O（N^2）,在接近有序的情况下他的时间复杂度是O（N），因为遍历一遍就可以出结果了，空间复杂度O（1），这种排序也是稳定的，因为我们可以将相同的值放在后面，就能保证稳定了！

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

# 三、选择排序 #

![在这里插入图片描述][f813cc64c607441b85e824438697281d.gif]  
观察上面的选择排序，总结规律：在遍历排好位置后面的数值时，选择后面当中最小的，与当前索引的值进行交换，但是我们在这里可以进行一次优化，我们可以从遍历一次拿到最大值和最小值，最小值往前放，最大值往后面放，再将我们的区间缩小即可。

void SelectSort(int* a, int n)
    { 
    	//我们这里实现的选择排序优化，一次选择最大和最小的
    
    
    	//排升序
    	int begini = 0 , endi = n-1 ;
    	//一次
    	while(begini<endi){ 
    	//这里寻找最大和最小下标的索引
    	int maxi = begini, mini = begini;
    	for (int i = begini; i <= endi; ++i)
    	{ 
    		//我们这里找出最大和最小的索引
    		if (a[maxi] < a[i])
    		{ 
    			maxi = i;
    		}
    		if (a[mini] > a[i])
    		{ 
    			mini = i;
    		}
    	}
    	Swap(&a[begini], &a[mini]);
    	//1.mini与maxi相等说明是一个等值数列
    	//2.考虑begini会不会和maxi相等，相等就出事
    
    	//当maxi和begini是同一个位置的时候
    	//这里是因为bigini是先交换的，要考虑会不会影响到后面maxi，endi交换也会有这个问题
    	//即使极端情况 begini = maxi，endi = mini，也可以这样解决，最后endi就和自己交换了一下而已
    	if (begini == maxi)
    	{ 
    		maxi = mini;
    	}
    	Swap(&a[endi], &a[maxi]);
    	--endi;
    	++begini;
    }
    }

## 3.复杂度，稳定性分析 ##

选择排序的时间复杂度是O（N^2）,在接近有序的时候也是O（N ^ 2）,因为我们每次都要从剩下的牌中在进行挑选，N N-2 N-3 … 1,所以它是一个比较不实用排序了，并且他是一种不稳定的排序，我们遍历一遍的时候 a\[\]=\{1 1 1 2 1 1 1 \};这个数组当中把2和最后一个位置的1交换时，对于2后面的两个1，他们的相对顺序发生了改变。

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

# 四、希尔排序（ 缩小增量排序） #

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。引自百度。  
所以我们可以看出这个排序跟插入排序是强相关的。  
基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。  
![在这里插入图片描述][32ab66f9e9454872af16987ed5172900.gif]  
希尔排序就是在处理一些极端情况比较高效，比如在上面的**插入排序**时如果我们在原数组降序的情况下去排升序，那么我们交换的次数是十分多的，也可以说是插入排序的最坏的情况，这个时候聪明的先辈想到了希尔排序，将数组分成了gap组，然后可以理解为分别处理每一个小组，gap从5 – 2 – 1的过程在降序的情况下，**排在后面的数值小的数能步子更大排到前面**，当gap为1的时候实际上就是进行了**一次插入排序**。设置gap的过程我们也称之为**预排序**

void ShellSort(int* a, int n)
    { 
    	
    	gap为3,排升序
    	//int gap = n;
    	//while (gap > 1) { 
    	// //这个是总结的经验
    	// gap = gap / 3 + 1;
    	// //end的范围是[0,n-gap)
    	// //只要保证每组都是前面先排就可以。
    	// //所以用这种写法比较简单，但时间复杂度跟套两层循环一样
    
    	// for (int i = 0; i < n - gap; ++i) { 
    	// int end = i;
    	// int tmp = a[end + gap];
    	// while (end >= 0)
    	// { 
    	// //当前的end的值比tmp大就要往end+gap位置挪
    	// //所以要提前保存end+gap的值
    	// if (a[end] > tmp)
    	// { 
    	// a[end + gap] = a[end];
    	// end -= gap;
    	// }
    	// else
    	// { 
    	// break;
    	// }
    	// a[end + gap] = tmp;
    	// }
    	// }
    	//}
    		//gap为3,排升序
    	int gap = n;
    	while (gap > 1) { 
    		//这个是总结的经验
    		gap = gap / 3 + 1;
    		//end的范围是[0,n-gap)
    
    		//也可以先排第一组再排gap组
    		//实际上都一样，时间复杂度一致的
    		for (int j = 0; j < gap; j++) { 
    			for (int i = j; i < n - gap; i += gap) { 
    				int end = i;
    				int tmp = a[end + gap];
    				while (end >= 0)
    				{ 
    					//当前的end的值比tmp大就要往end+gap位置挪
    					//所以要提前保存end+gap的值
    					if (a[end] > tmp)
    					{ 
    						a[end + gap] = a[end];
    						end -= gap;
    					}
    					else
    					{ 
    						break;
    					}
    					a[end + gap] = tmp;
    				}
    			}
    		}
    	}
    }

## 4.复杂度，稳定性分析 ##

希尔排序的时间复杂度是O(N^1.3),这个是由科学家们弄出来的数字。我个人觉得每一次当gap是以gap/3+1的步骤走，其实while大循环它会走logN(3为底)次循环，每一个循环里面每次接近是遍历一次数组O(N)，总的时间复杂度就是O(logN(3为底)\*N)，可以看出这已经算是一种非常厉害的排序了。这个排序是不稳定的，gap将一个组分为若干组进行排序之后出现两个相同值的顺序不同其实也是很正常的。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_12_color_FFFFFF_t_70_g_se_x_16]

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

# 五、快排 #

快排的单趟排序有很多个版本，这里说几个比较有名的，最早的是hoare版本的，也就是创始人。后面的挖坑法相对比较好理解。还有前后指针法（很多种叫法，这里我们先称作前后指针）

## 1.1. hoare版本 ##

![在这里插入图片描述][8f96cf9c3d944277acdc346eca38ca6e.gif]

hoare版本，就是先确定一个key，我们假设key取左边的值，我们就要先从右边找到比key小的值，再从左边找一个比key大的值，进行交换，知道左右区间为0时结束，就排好一个key这个数的位置了。

int PartSort1(int* a, int left, int right)
    { 
    //采用前后指针法,将key先设置为左边的值
    //一开始先让右边找小，左边找大，然后交换
    //最后相遇的位置一定是比key对应的值小，交换就把key的值放在正确的索引了
    	//注意这里分区间，key是left，不是0！！！
    	int midi = GetMidIndex(a,left,right);
    	Swap(&a[midi], &a[left]);
    
    	int key = left;
    	while (left < right)
    	{ 
    		//右边找比key的值小的
    		while (left < right && a[key] <= a[right])
    		{ 
    			right--;
    		}
    		//左边找大
    		while (left < right && a[key] >= a[left])
    		{ 
    			left++;
    		}
    		//进行交换
    		Swap(&a[left], &a[right]);
    	}
    	//跳出只有一个条件，就是left==right，而这个位置就是key要的索引，并且这个值小于key对应的索引
    	Swap(&a[left], &a[key]);
    	return left;
    }

## 2.1 挖坑法 ##

挖坑法可以选择在0索引处挖坑（即把数拿走保存），然后从右边找一个小的填坑，再从左边找一个大的埋住右边的坑。最后把key放入相遇点（最后一个坑位）即可。key在下图为Pivot  
![在这里插入图片描述][e56ab79118514d91aa731d2dbc231799.gif]

int PartSort2(int* a, int left, int right)
    { 
    	int midi = GetMidIndex(a, left, right);
    	Swap(&a[midi], &a[left]);
    
    	//挖坑法，让left为坑，右边先走找小埋坑，再左边
    	int hole = left;
    	int key = a[hole];
    	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[left] = key;
    
    	return left;
    }

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

## 3.1 前后指针版本 ##

思想：一个指针从后面找小，填到前面指针指向的位置。直到后指针越界。总之也都是填好一个值在他该在的位置所做的操作。

int PartSort3(int* a, int left, int right)
    { 
    	//不这样做排已经有序会造成单边树，O（N^2）;
    	int midi = GetMidIndex(a, left, right);
    	Swap(&a[midi], &a[left]);
    
    	//前后指针法的key可以选择第一个或者最后一个，逻辑差不多
    	int key = left;
    	int prev = left, cur = left + 1;
    	while (cur <= right)
    	{ 
    		//防止自己和自己交换的一种写法
    		if (a[cur] < a[key] && ++prev != cur)
    		{ 
    			Swap(&a[prev], &a[cur]);
    		}
    		cur++;
    	}
    	Swap(&a[prev], &a[key]);
    	return prev;
    }

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

### 三数取中 ###

因为在实际当中，当我们接近有序的时候，会变成类似一颗单边树，所以我们会通过从left mid right 三个位置当中挑选一个适中的值作为key，这样也能够保证树的高度为logN

//三数取中
    int GetMidIndex(int* a, int left, int right)
    { 
    	//为了防止int越界[1,4] 1 + 1=2 
    	int mid = left + (right - left) / 2;
    	if (a[left] > a[mid])
    	{ 
    		//a[mid] >= a[right] ,mid为中
    		if (a[mid] >= a[right])
    		{ 
    			return mid;
    		}
    		//a[mid] < a[right] 即 left>mid , mid<right，在left，right找中 
    		else if (a[left] >= a[right])
    		{ 
    			//小的right为中
    			return right;
    		}
    		else
    		{ 
    			return left;
    		}
    	}
    	else //a[left] <= a[mid]
    	{ 
    		//a[left] >= a[right]
    		if (a[left] >= a[right])
    		{ 
    			return left;
    		}
    		//a[left] < a[right] right和mid中选小的
    		else if (a[right] >= a[mid])
    		{ 
    			return mid;
    		}
    		else
    		{ 	//a[right] <a[mid]
    			return right;
    		}
    	}
    }

# 4. 快排代码 #

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

快排实际上就是在单趟排序当中划分了左右区间，对于左右区间做一个相同的操作，所以这里我们写了递归和非递归（借助栈）这两种实现方式

//递归
    void QuickSort(int* a, int left, int right)
    { 
    	//当区间分割到一个值或者不存在就返回
    	//还剩两个值我们都需要再排序
    	if (left >= right)
    		return;
    	//当前要做就是确定一个位置,划分区间递归
    	//[left,key-1]key[key+1,right]
    	int key = PartSort3(a, left, right);
    	//递归左右区间
    	QuickSort(a, left, key - 1);
    	QuickSort(a, key+1,right);
    
    }

非递归的在这里借助栈，存放我们要进行单趟排序的区间，然后将划分的左右区间入栈，直到不存在左右区间则停止入栈，栈为空的时候即处理完毕。

//非递归
    void QuickSortNonR(int* a, int left, int right)
    { 
    	//非递归，我们可以处理当前的区间，再处理分区间
    	//先入右，后入左，就先拿到左
    	Stack s;
    	StackInit(&s);
    	StackPush(&s,right);
    	StackPush(&s,left);
    	while (!StackEmpty(&s))
    	{ 
    		left = StackTop(&s);
    		StackPop(&s);
    		right = StackTop(&s);
    		StackPop(&s);
    		//处理当前区间 [left,right]
    		int key = PartSort3(a, left, right);
    
    		//划分左右区间，分别入栈
    		//[left,key-1]key[key+1,right]
    		//先入右区间,区间有两个值才需要处理
    		if (key + 1 < right)
    		{ 
    			StackPush(&s, right);
    			StackPush(&s, key + 1);
    		}
    		//再入左区间
    		if (left < key - 1)
    		{ 
    			StackPush(&s, key - 1);
    			StackPush(&s, left);
    		}
    	}	
    }

## 5.复杂度，稳定性分析 ##

快排的时间复杂度O(N*logN),加了三数取中的快排将最坏的情况转变为最好的情况了，空间复杂度O(logN),注意空间是累计的，即使是非递归的空间复杂度也是O(logN),因为最后一层入栈是2*O(logN),可以理解为之前的用的空间都没有比这个大的，我们递归左区间的空间是可以给右区间后面使用的。这种排序也是不稳定的，因为它只是将后面选一个大的放到前面，将前面小的放到后面，a\[\]= \{10,10,3,4,3\};这样的假如是前后指针法在第一次的时候末尾的3就跟前面的10交换了位置。

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

# 六、归并排序 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
归并的排序的思想就是在两个**有序的区间**合并成一个有序的区间，观察上图每个被分割成**一个整数的数组**，只有一个整数的时候我们就可以认为他是有序的，这个时候左右区间有序，我们就可以合并成一个有序的数组，实际上这种方法类似于树的后序遍历。

## 递归实现： ##

我们可以把一个数组分成两半，对于每一个数组当他们是有序的就可以进行一次合并操作。对于他们的两个区间进行递归。当区间只有一个值的时候我们就可以进行合并返回上一层，让上一层合并再返回。

void _MergeSort(int* a, int left, int right,int* newArr)
    { 
    	if (left >= right)
    		return;
    	int mid = left + (right - left) / 2;
    	//[left,mid][mid+1,right]
    	_MergeSort(a, left, mid,newArr);
    	_MergeSort(a, mid + 1, right,newArr);
    	//走到这里已经是左右区间有序
    	//将两个区间合并成一个区间
    	//拷贝到newArr当中，排完再放回
    	int index = left;
    	int begin1 = left, end1 = mid;
    	int begin2 = mid+1,end2 = right;
    
    	while (begin1 <= end1 && begin2 <= end2)
    	{ 
    		if (a[begin1] < a[begin2])
    		{ 
    			newArr[index++] = a[begin1++];
    		}
    		else
    		{ 
    			newArr[index++] = a[begin2++];
    		}
    	}
    	//走到这里一定有一边没有走完
    	while (begin1 <= end1)
    	{ 
    		newArr[index++] = a[begin1++];
    	}
    	while (begin2 <= end2)
    	{ 
    		newArr[index++] = a[begin2++];
    	}
    	//拷贝回元素组 letf -- right 的位置
    	for (int i = left; i <= right; ++i)
    	{ 
    		a[i] = newArr[i];
    	}
    }
    void MergeSort(int* a, int n)
    { 
    //归并排序就是在左右区间有序重新组合起来
    //所以保证左右区间都是有序，遍历到叶子就可以
    	int* newArr = (int*)malloc(sizeof(int) * n);
    	int left = 0;
    	int right = n - 1;
    	_MergeSort(a, left, right,newArr);
    }

## 迭代实现： ##

迭代实现可以用循环来实现，这里我们根据递归思想其实很容易知道，我们控制迭代从最小的子问题出发，保存最小子问题的值，然后提供给后面用，这其实就是一个[动态规划][Link 1]的思想，我们可以从利用子问题的解，解决 **“大BOSS”** 。

void MergeSortNonR(int* a, int n)
    { 
    	//int a[] = { 8,4,5,7,1,3,6,2,7,8 };
    	
    	int* newArr=(int*)malloc(sizeof(int)*n) ;
    	int groupNum = 1;
    	int left;
    	int right;
    	//动态规划的思想，当我们把最小的问题切割
    	while(groupNum<n/2+1)
    	{ 
    		for (int i = 0; i < n; i += (2*groupNum))
    		{ 
    		//分成两组[begin1,end1][begin2,end2]
    		int begin1 = i;
    		int end1 = i + groupNum - 1;
    		int begin2 = i + groupNum;
    		int end2 = i + 2 * groupNum - 1;
    		//处理两种情况，当end1已经越界，说明处理end1的边界
    		if (end1 >= n)
    		{ 
    			end1 = n - 1;
    		}
    		//当end1越界，理所当然的begin2和end2都越界了
    		//这里可能的[begin1,end1]区间，也需要拷贝到临时数组，再拷回原数组
    		if (begin2 >= n)
    		{ 
    			//表示右区间不存在
    			begin2 = n;
    			end2 = n-1;
    		}
    		else if (begin2 < n && end2 >= n)
    		{ 
    			end2 = n - 1;
    		}
    
    		left = begin1;
    		right = end2;
    		//index用于放到临时数组newArr当中的
    		int index = begin1;
    
    			while (begin1 <= end1 && begin2 <= end2)
    			{ 
    				if (a[begin1] < a[begin2])
    				{ 
    					newArr[index++] = a[begin1++];
    				}
    				else
    				{ 
    					newArr[index++] = a[begin2++];
    				}
    			}
    			//走到这里一定有一边没有走完
    			while (begin1 <= end1)
    			{ 
    				newArr[index++] = a[begin1++];
    			}
    			while (begin2 <= end2)
    			{ 
    				newArr[index++] = a[begin2++];
    			}
    			//拷贝回元素组 letf -- right 的位置
    			for (int x = left; x <= right; ++x)
    			{ 
    				a[x] = newArr[x];
    			}
    		}
    		groupNum*=2;
    	}
    	free(newArr);
    	newArr = NULL;
    }

## 5.复杂度，稳定性分析 ##

归并排序复杂度是O(N\*logN),可以看出他的递归写法每次都将一组平均分，分完后高度大概是logN，空间复杂度O（N），因为开了一个相同大小的数组。他是一种稳定的排序，因为它最后是从小到大有序的汇成一组的。

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

# 七、堆排 #

堆排在之前出过一期，详细[点击这里][Link 2]。  
**注意的是排升序要建大堆，排降序建小堆  
注意的是排升序要建大堆，排降序建小堆  
注意的是排升序要建大堆，排降序建小堆**

void AdjustDwon(int* a, int n, int parent)
    { 
    	//大堆
    	//默认左孩子为最大的
    	int child = parent * 2 + 1;
    	//孩子更新到叶子就停止更新
    	while (child < n)
    	{ 
    		if (child + 1 < n && a[child + 1] > a[child])
    		{ 
    			child++;
    		}
    		if (a[child] > a[parent])
    		{ 
    			Swap(&a[child], &a[parent]);
    			parent = child;
    			child = child * 2 + 1;
    		}
    		else
    		{ 
    			break;
    		}
    	}
    }
    void HeapSort(int* a, int n)
    { 
    	//建堆
    	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    	{ 
    		AdjustDwon(a, n, i);
    	}
    	//排升序为例（大堆）
    	int size = n-1;
    	while (size > 0) { 
    		Swap(&a[0], &a[size]);
    		AdjustDwon(a, size, 0);
    		size--;
    	}
    }

## 7.复杂度，稳定性分析 ##

建堆的复杂度是O（N），如下图，堆排的时间复杂度是O（N\*logN），空间复杂度O（1）。当然堆排序也是不稳定的，因为向下调整的时候可能把一个值就调到最底下了改变相对顺序了。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 2]

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

# 八、计数排序 #

这是一种非比较排序，看前面的那些排序，他们都是两两比较确定是否交换，而这种排序是通过将这个值通过映射到数组，数组里存的值表示有多少个这样的值，当然，在对于数据比较大的时候我们可以通过相对映射，让（该值-min）后的数组加一，最后还原回去即可。如图最小的是90，95-90映射到我们的数组当中，最后再还原![在这里插入图片描述][c5c797522c2d4e45a7a5783b84ae123e.jpg]

void CountSort(int* a, int n)
    { 
    	//int a[] = { 31,24,25,16,1,0,79 };
    
    	//遍历一遍找到最大和最小，然后开大一的数组
    	int max = a[0];
    	int min = a[0];
    	for (int i = 1; i < n; ++i)
    	{ 
    		if (max < a[i])
    		{ 
    			max = a[i];
    		}
    		if (min > a[i])
    		{ 
    			min = a[i];
    		}
    	}
    	int size = max - min + 1;
    	int* tmp = (int*)calloc(size,sizeof(int));
    	//将a遍历映射到tmp当中,a的长度是n，tmp的长度只有size
    	for (int i = 0; i < n; ++i)
    	{ 
    		tmp[a[i] - min]++;
    	}
    	//在按照tmp当中的存放放回去
    	int index = 0;
    	for (int i = 0; i < size; ++i)
    	{ 
    		while (tmp[i] > 0)
    		{ 
    			//这里应该是下标+映射的
    			a[index++] = i + min;
    			--tmp[i];
    		}
    	}
    }

## 8.复杂度，稳定性分析 ##

计数排序的时间复杂度是O（N），我们只需要遍历一遍元素组，再把映射的数组表填回去就可以了，所以这在一些场景下使用是非常高效的，空间复杂度是O(max-min),就是我们开的数组是这个区间的范围差。所以对于数值差距比较大的情况下这不适用。它是一种稳定的排序。

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

# 九、归并排序外排序使用 #

这里我的实现是自己控制每次想在内存当中存放多少数据NUM ，当然这个数字是可以稍微大一点的，因为一次IO所需要的时间比在内存上差距是很大的，所以我们电脑允许的话一次放入1G，2G的数据进行排序在写回文件夹是很好的选择，这里我们实现还用了宏FILENUM让我们自己选择创建文件夹的多少，所以对于一个具体的数字时，需要算一算然后填写这两个值。NUM可以直接给到5千万，然后用（要排的总数/NUM+1）放到FILENUM当中。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
要解决上述这种情况，我们可以先切分成小文件进行排序写回文件，**注意这里文件也不要太小，最好和内存挂钩，一次IO的时间消耗是很大的**，我们假设一次在内存中排5千万的数，则需要20个文件  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
第二步就把这些有序文件在硬盘当中进行合并就可以了。![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 5]

**代码如下：**

// 我们做这个最好知道大概有多少数据，我们内存一次拿多少数据排好放在一个文件
    // 一般来说，32位数组开个2G左右就很勉强了，所以我们的n可以到5千万左右。
    // 但这里模拟的话我们只给100个数据，一次从文件当中拿10个数据排序，模拟这个过程。
    // 排好若干子文件后，再通过两两文件进行归并实现。
    #define NUM 10 //控制一次性放多少数据到文件当中，就从log.txt拿多少排序好放到文件中
    #define FILENUM 11 //控制文件的数量
    void MergeSortFile()
    { 
    	
    	//先对我们要排序的文件进行分成若干份有序的子文件
    	FILE* pf = fopen("log.txt", "r");
    	char filename[20];//文件名给个20够了
    	int n = NUM;//一次读取十个,后续可以通过需求直接替换成宏
    
    	//对filename进行初始化
    	memset(filename, 0, sizeof(filename));
    	int a[10];//缓冲区，将文件的数据放入a当中
    	int i = 1;
    	int count = 0;
    	//注意考虑一次性读到文件尾的情况
    	while (count++ < FILENUM)
    	{ 
    		memset(filename, 0, sizeof(filename));
    		//创建子文件，从log.txt当中读取10个数放到a进行归并排序
    		sprintf(filename, "%d",i++);
    		FILE* nf = fopen(filename, "w");
    
    		//从pf流里面写入到a当中
    		int index = 0;
    
    		//这里控制两个边界有一点难，所以要多一个条件判断。
    		while (~fscanf(pf, "%d", &a[index]))
    		{ 
    			//一次读数据有n个拿n个，没有就拿到index个
    //这里当数据不足这样写有问题,可能有数据只有1个的时候，index应该是0，又在这里++
    			if (index < n - 1)
    				index++;
    			else
    				break;
    		}
    
    		if (index != (NUM - 1))
    		{ 
    			index--;
    		}
    
    		//这里的index是我们读到的最大值的索引 0--9
    		QuickSort(a, 0, index);
    
    		//往新的文件里面写在内存当中排好的数据
    		for (int i = 0; i <= index; ++i)
    		{ 
    			fprintf(nf, "%d\n", a[i]);
    		}
    		fclose(nf);
    	}
    	//每一个文件都已经是有序的了
    	//对已经创建出来的文件进行两两归并，注意这里不能在内存归并了
    	//我们要在硬盘上进行归并，我们选择将两两归并的文件以两个文件名的和
    	char filename1[20];
    	char filename2[20];
    	//归并的文件放到filename当中
    	sprintf(filename, "12");
    	sprintf(filename1, "1");
    	sprintf(filename2, "2");
    
    	//i控制合并多少次 ， 12 ... 1234567891011 9次即可
    	for (int i = 2; i <= FILENUM; ++i)
    	{ 
    		FILE* f1 = fopen(filename1, "r");
    		FILE* f2 = fopen(filename2, "r");
    		FILE* pf = fopen(filename, "w");
    		//f1 ,f2 两个有序文件中读取放入pf指向的文件
    		int num1 = 0;
    		int num2 = 0;
    		//每次从两个文件中读取一个，放到num当中进行比较
    		int ret1 = fscanf(f1, "%d", &num1);
    		int ret2 = fscanf(f2, "%d", &num2);
    		while (~ret1 && ~ret2)
    		{ 
    			//当两个当中一个读到文件尾则结束
    			if (num1 > num2)
    			{ 
    				//读一个更新文件指针，另一个文件不动
    				fprintf(pf, "%d\n", num2);
    				ret2 = fscanf(f2, "%d", &num2);
    			}
    			else
    			{ 
    				fprintf(pf, "%d\n", num1);
    				ret1 = fscanf(f1, "%d", &num1);
    			}
    		}
    		//到这里还有一个没有读完
    		while (ret1 !=EOF)
    		{ 
    			fprintf(pf, "%d\n", num1);
    			ret1 = fscanf(f1, "%d", &num1);
    		}
    		while (ret2 != EOF)
    		{ 
    			fprintf(pf, "%d\n", num2);
    			ret2 = fscanf(f2, "%d", &num2);
    		}
    		fclose(pf);
    		//这里不改变i，所以我们弄个临时变量保存i。
    		int x = i;
    		x++;
    		//在这里我们更新文件名
    		sprintf(filename2, "%d", x);
    		sprintf(filename1, "%s", filename);
    		sprintf(filename, "%s%d", filename,x);
    
    	}
    }

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

# 总结 #

制作不易，一键三连支持一下吧！！！

[3a040ece5e6845d1875a99171c174e70.gif]: /images/20220828/72d8f1ff1ab247baafa42edb27b1b951.png
[03851b7489b846cfa71090650ae7d8f5.gif]: /images/20220828/b4023378bc5d41cca7ff54603e23257d.png
[f813cc64c607441b85e824438697281d.gif]: /images/20220828/b9434d03661a4ce79dc3635932f46c41.png
[32ab66f9e9454872af16987ed5172900.gif]: /images/20220828/a4365c38f58b47f0bfb62d5d54e75d0f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/73de5fc9d6784169b5d7c39320e44401.png
[8f96cf9c3d944277acdc346eca38ca6e.gif]: /images/20220828/4503bf4fef9b46f88247ef565c0b7395.png
[e56ab79118514d91aa731d2dbc231799.gif]: /images/20220828/accce625465140498f03b25f4d40c6e3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2db3dbf8d45f41879d5d775d31f436c2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/63dacf4c6aa14d1fb3a4c8121ed79387.png
[Link 1]: https://blog.csdn.net/weixin_52344401/article/details/119655486
[Link 2]: https://blog.csdn.net/weixin_52344401/article/details/120061391?spm=1001.2014.3001.5501
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/d8b0bb806a3d4093b2866075baf420a2.png
[c5c797522c2d4e45a7a5783b84ae123e.jpg]: /images/20220828/b086af74b1d94378b9f8df0261fe9e89.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/dfcd76e77a3444ebb0be55b253b421a0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/ec3d2accec0b4da7b18734ba2a6868a1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/81b38bcd7aa746468445710a186522cc.png