当前位置：首页 > news >正文

归并排序，外排序，计数排序(非比较排序)

news 2025/7/1 3:26:58

归并排序：（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
也就是：假设左边有序，右边有序，然后合并在一起归并后就有序。归并要借助临时的第三方数组。
不一定是均分，只是下面的例子正好比较均匀。
快排是前序，归并是后续。
归并是先递归到两个数再归并，一层一层往回返着归并（排序）。
时间复杂度：O(N*logN)
空间复杂度：O(N) — 开辟临时数组
在这里插入图片描述

 // 归并排序递归实现
void _MergeSort(int* a, int left, int right, int* tmp)
{//分到最后区间只有一个数或者没有这样的区间了返回。if(left >= right){return;}int mid = (left + right)/2;//[left, mid] [mid+1, right]_MerageSort(a, left, mid, tmp);_MerageSort(a, mid+1, right, tmp);// 两段有序子区间归并放到tmp中然后拷贝回aint begin1 = left, end1 = mid;int begin2 = mid+1, end2 = right;int i = left;// 在两个区间中选择小的数先放进tmpwhile(begin1 <= end1 && begin2 <= end2){if(a[begin1] < a[begin2])tmp[i++] = a[begin1++];elsetmp[i++] = a[begin2++];}//将两个区间中没放完的那个区间的有序数组尾插到tmp中while(begin1 <= end1)tmp[i++] = a[begin1++];while(begin2 <= end2)tmp[i++] = a[begin2++];// 将tmp的数据返回给a right是下标 所以得<=for(int j = left; j<=right; j++)a[j] = tmp[j];
}
void MergeSort(int* a, int n) //n传参传的是数组的大小
{int* tmp = (int*)malloc(sizeof(int)*n)_MergeSort(a, 0, n-1, tmp) //n-1传参传的是数组下标的闭区间大小free(tmp);
}

非递归方法：每次归完后都需要将归好的数组返回给原数组。最后将有序的tmp给a然后释放tmp。
代码控制中有个gap，gap是1 就是11归(两个相比)，gap是2就是22归(四个相比)， gap是4就是44归(八个相比)。
问题：
1.最后一个小组归并时，第一个小区间不够gap个，则不需要归并不处理时OK的因为他同样满足第二个小区间不存在，因此不处理OK。
2.最后一个小组归并时，第二个小区间不存在，则不需要归并了
3.最后一个小组归并时，第二个小区间存在但是第二个区间不够gap个
问题1和问题2可以合并处理。
在这里插入图片描述

 // 归并排序非递归实现
void _Merge(int*a, int* tmp, int begin1, int end1, int begin2, int end2)
{int i = begin1;int j = begin1;// 在两个区间中选择小的数先放进tmpwhile(begin1 <= end1 && begin2 <= end2){if(a[begin1] < a[begin2])tmp[i++] = a[begin1++];elsetmp[i++] = a[begin2++];}//将两个区间中没放完的那个区间的有序数组尾插到tmp中while(begin1 <= end1)tmp[i++] = a[begin1++];while(begin2 <= end2)tmp[i++] = a[begin2++];// 将tmp的数据返回给a right是下标 所以得<=for(; j<=end2; j++)a[j] = tmp[j];
}
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n)_MergeSort(a, 0, n-1, tmp) //n-1传参传的是数组下标的闭区间大小int gap =1;while(gap < n){//进来gap = 1是11 gap =2 是22 gap=4 是44for(int i=0; i<n; i += 2*gap){int begin1 = i, end1 = i+gap-1, begin2 = i+gap, end2 = i+2*gap-1;//第二个小区间不存在，则不需要归并了if(begin2 >= n)break;//第二个区间存在但是第二个区间不够gap个，结束位置越界了，需要修正if(end2 >= n)end2 = n-1;//循环控制归并的边界啊// [i, i+gap-1] [i+gap, i+2*gap-1] ..._Merge(a, tmp, begin1 , end1 , begin2, end2); //传的就是两个边界 每次传两个边界}gap *= 2;} free(tmp);
}

计数统计排序：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤：
1.统计相同元素出现次数
2.根据统计的结果将序列回收到原来的序列中
时间复杂度：O(max(N,rang)) 就是N和范围谁大就是O谁。适合一组数据数据范围比较集中，优秀的排序。
空间复杂度：O(range)
范围集中效率高，具有局限性。并且只适合整数。
在这里插入图片描述

 // 计数排序
void CountSort(int* a, int n)
{int max = a[0], min = a[0];for(int i = 0; i <n; ++i){if(a[i] > max)max = a[i];if(a[i] < min)min = a[i];}int range = max-min +1;int* count = (int*)malloc(sizeof(int)*range);memset(count, 0, sizeof(int)*range); //将count初始化为0for(int i =0; i<n; ++i){count[a[i] - min]++ //让对应的位置++}//写入a中int i=0;for(int j=0; j<range; j++) // 循环count数组{while(count[j]--)//让这个位置的次数一直-到0 就打印完了次数。{a[i++] = j+min;}}free(count);
}