Data Structure--排序--归并排序(递归/非递归)--计数排序(非比较排序)

àì夳堔傛蜴生んèń 2022-11-03 11:19 283阅读 0赞

### 排序 ###

*  归并排序(递归+非递归)
 *  计数排序(非比较排序)

# 归并排序(递归+非递归) #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]  
**核心函数:合并实现接口**

//归并排序
    //先将序列进行分解,不停地拆分,一直到子序列只有一个元素,然后对子序列进行合并,最终成有序序列
    
    
    //==================================递归
    //相邻子序列合并
    //对于空间的二分,我们只需要三个数据就可以了
    //begin mid end 就可以将空间分为2
    void merge(int* arr, int begin, int mid, int end, int* tmp){ 
    	
    	//递增
    	int begin1 = begin;		//前半个区间
    	int end1 = mid;
    	
    	int begin2 = mid + 1;	//后半个区间
    	int end2 = end;
    
    	//辅助空间
    	int idx = begin;
    	
    	//合并有序的序列
    	//检查是否越界
    	while (begin1 <= end1&&begin2 <= end2){ 		//如果没有越界
    		
    		if (arr[begin1] <= arr[begin2])			//如果第一个元素小
    			tmp[idx++] = arr[begin1++];			//先将第一个输入
    
    		else
    			tmp[idx++] = arr[begin2++];			//否则,先将第二个输入
    	}
    	//上面的循环进行,直到结束
    	
    	//判断是否有没有合并的元素
    	if (begin1 <= end1)		//如果1中有剩余
    	
    		//直接将1中剩余的元素拷贝到序列中
    		memcpy(tmp + idx, arr + begin1, sizeof(int)*(end1 - begin1 + 1));
    	
    	if (begin2 <= end2)
    		//如果2中有剩余,直接将2中的拷贝过去
    		memcpy(tmp + idx, arr + begin2, sizeof(int)*(end2 - begin2 + 1));
    
    	//合并后的序列拷贝到原始的数据
    	memcpy(arr + begin, tmp + begin, sizeof(int)*(end - begin + 1));
    }

合并这里主要运用了字符串的部分接口,理解了就很简单

**1.递归实现:**

//======================递归
    void _mergeSort(int* arr, int begin, int end, int* tmp){ 
    	
    	if (begin >= end)	//判空
    		return;
    
    	int mid = begin + (end - begin) / 2;		//找到中间元素
    
    	//先进行子序列的合并
    	_mergeSort(arr, begin, mid, tmp);
    	_mergeSort(arr, mid + 1, end, tmp);
    	//上面两部是对于子序列的合并,也就是将一个个的小点点进行合并
    
    	//合并两个有序的子序列
    	merge(arr, begin, mid, end, tmp);
    }
    void mergeSort(int* arr, int n){ 
    	
    	//申请辅助空间
    	int* tmp = (int*)malloc(sizeof(int)*n);		//申请空间方便存放
    	_mergeSort(arr, 0, n - 1, tmp);		//调用函数
    	
    	free(tmp);		//将申请用完的空间进行释放
    }

**2.非递归实现:**

//=========================非递归
    void mergeSortNoR(int* arr, int n){ 
    
    	int* tmp = (int*)malloc(sizeof(int)*n);		//动态内存申请
    	//子序列的步长
    	int step = 1;		//步长也就是内部有一个元素步长为1,两个则为2
    	
    	while (step < n){ 		//步长最大就是原来的序列
    	
    		for (int idx = 0; idx < n; idx += 2 * step){   //注意这里,步长每次增加2!!!!!!!!
    
    			//找到两个待合并的子序列区间
    			//[begin,mid] [mid+1,end]
    			int begin = idx;
    			int mid = idx + step - 1;
    			
    			//判断是否存在第二个子序列
    			if (mid >= n - 1)
    				continue;	//不存在第二个子序列,直接跳过
    			int end = idx + 2 * step - 1;
    			//判断第二个子序列是否越界
    			if (end > n)
    				end = n - 1;
    				
    			merge(arr, begin, mid, end, tmp);
    		}
    
    		//更新步长
    		step *= 2;
    	}
    }

**主要就是大家理解后多敲代码,明白我上面那张图的逻辑原理,就很简单了!**

# 计数排序(非比较排序) #

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

//====================================3.非比较排序(计数排序)
    //所消耗的空间过大 空间复杂度大
    void countSort(int* arr, int n){ 
    	
    	//找到最大和最小值
    	int max, min;
    	min = max = arr[0];
    	
    	for (int i = 1; i < n; ++i){ 	//这里是进行循环选出最大值和最小值
    	
    		if (arr[i]>max)
    			max = arr[i];
    		if (arr[i < min])
    			min = arr[i];
    	}
    	
    	//计算出范围
    	int range = max - min + 1;
    	//创建一个计数数组,初始化为0
    	int* countArr = (int*)calloc(range, sizeof(int));  //动态开辟一个全0的数组
    
    	//计数
    	for (int i = 0; i < n; ++i){ 
    		
    		countArr[arr[i] - min]++;		//对其进行计数
    	}
    	
    	//遍历计数数组
    	int idx = 0;
    	for (int i = 0; i < range; ++i){ 	//遍历整个范围
    		
    		while (countArr[i]--){ 		//依次减减
    
    			arr[idx++] = i + min;		//对其进行循环赋值
    		}
    	}
    }

整体难度不是太高,多敲代码.计数排序的复杂度过高,并不常用,对于排序的理解我也总结的差不多了,下面我对**排序的优缺点进行总结:**

<table> 
 <thead> 
  <tr> 
   <th>排序方法</th> 
   <th>最坏复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n^2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n^2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n^2)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(n^2)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(nlogn)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(n^2)</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

大家注意理解,对自己框架的构建有挺大的帮助的,一起加油!!!多敲代码!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/d69ae94a9589456ea90357fc63869295.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/16889c98eb284771bec6ef2a816dab28.png