本文主要是介绍归并排序/计数排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1：归并排序
1.1：代码
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+1, right, tmp); int begin1 = left; int end1 = mid; int begin2 = mid + 1; int end2 = right; int i = begin1; while (begin1 <= end1 && begin2 <= end2) { if(arr[begin1] < arr[begin2]) { tmp[i++] = arr[begin1++]; } if (arr[begin1] > arr[begin2]) { tmp[i++] = arr[begin2++]; } } while (begin1 <= end1) { tmp[i++] = arr[begin1++]; } while (begin2 <= end2) { tmp[i++] = arr[begin2++]; } for (int i = left; i <= right; i++) { arr[i] = tmp[i]; }
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n); _MergeSort(arr, 0, n - 1, tmp);
}
1.2：递归过程
图一：
if (left >= right){return;}int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+1, right, tmp); 通过这三行代码，可以得到如图所示的结果，当传递的 left 和 right 满足 if 条件时，递归开始返回,
图二：
注：方框内容为自定义函数：void _MergeSort(int* arr, int left, int right, int* tmp)
注：对于新手（编者我而言）需要知道的是，每次递归，都会向系统开辟新的空间，而原先的空间会临时贮存在空间中，通过return返回重新调用该函数。
第一次返回时，来到D这个位置，接下来就将执行排序，即如下代码：该函数中 left = 0 mid = 0 right = 1，是对两个元素进行排列。
int begin1 = left;
int end1 = mid;
int begin2 = mid + 1;
int end2 = right; int i = begin1;
while (begin1 <= end1 && begin2 <= end2)
{ if(arr[begin1] < arr[begin2]) { tmp[i++] = arr[begin1++]; } if (arr[begin1] > arr[begin2]) { tmp[i++] = arr[begin2++]; }
} while (begin1 <= end1)
{ tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{ tmp[i++] = arr[begin2++];
}
当前范围内的数组排列完毕时，需要将临时数组的值传递给原数组，以便于下一次继续比较排序，
代码如下：
for (int i = left; i <= right; i++)
{ arr[i] = tmp[i];
}
left 和 right 分别对应数组左右临界，而left ~ right 中间的范围正是需要赋值的对象。
当D排序完毕后，系统会将其释放，此时来到B处，开始对右边数组开始递归，直至return，与左边递归类似，如图三所示：
图三：
当D中和E中的数组全部排列完毕，并且赋值给原数组时，此时会返回到B，对B中数组元素进行排列，，最后我们能够得到如下图所示的结果：
图四：
到B中函数排列完毕，并将临时数组中的值赋值给arr时，此时系统会将其空间释放，并返回到A中，开始递归右边部分函数，其过程如下图所示。
图五：
而对于右半部分的递归与左半部分相似，对于新人而言（我）注意其左临界值left的变化即可，其次通过上述过程不难发现，归并排序其实是一个后序遍历二叉树结点的过程，通过对左右子节点中的数组元素进行排列，最终在根节点处再次排列得到有序数组。
1.3：归并排序特性总结
时间复杂度：O(nlogn)
空间复杂度：O(n) —— 至于为什么是 n 而不是 logn 是因为以malloc 开辟了一块 n 大小的内存空间
2：计数排序
2.1：代码
void CountSort(int* arr, int n)
{ int max, min;max = min = arr[0];for (int i = 0; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int range = max - min + 1;int* tmp = (int*)malloc(sizeof(int) * range);assert(tmp);memset(tmp, 0, sizeof(int) * range);for (int i = 0; i < n; i++){tmp[arr[i] - min]++;}int index = 0;for (int i = 0; i < range; i++){while (tmp[i]--){arr[index++] = i + min;}}
} 2.2：思路
计数排序的思想：先找到数组中的最大值和最小值，定义 range (range = max - min +1) 个大小空间的数组 ,为了是大数据能够更好的存放进数组，同时又不会浪费太多空间。
我们需要把原数组的数据 - min 存放进新数组相应位置处，原数组中每重复一个数字，新数组相应位置处的大小就+1，这就意味着计数排序要求原数组中，各个数据相差不是很大，否则会造成空间的浪费。
计数排序的巧妙在于，我们不用去比较各个元素然后排序，而是统计原数组中，每个元素出现的次数，并将该元素 - min （这个差对应新数组下标）存入到数组中，如果两个值相差不大 ,得到的差会对应于新数组的一个下标，即新数组中，统计的是该元素在原数组中出现的次数，最后我们再进行排序时，以新数组元素个数为条件出发，同时新数组下标+min 又可以得到原数组中的元素，从而实现排列。
2.3：代码分析
下列代码我们开辟了一块 range 大小的空间区域
int max, min;max = min = arr[0];for (int i = 0; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int range = max - min + 1;int* tmp = (int*)malloc(sizeof(int) * range);assert(tmp);memset(tmp, 0, sizeof(int) * range);下列代码统计了原数组中，每个元素出现的次数，并存入到临时数组中
for (int i = 0; i < n; i++)
{tmp[arr[i] - min]++;
}最后对临时数组进行访问，以临时数组中元素个数为条件，临时数组下标地址 + min 得到原数组的值：
int index = 0;
for (int i = 0; i < range; i++)
{while (tmp[i]--){arr[index++] = i + min;}
} 2.4：图示上述过程：
初始时如图所示：
当进入第二个for循环时，开始统计原数组中的元素个数，当循环结束时，得到如下图所示变量关系：
当进入第三个for循环时，遍历tmp中各个元素，同时内层以各个元素的值作为条件，循环的将 i + min （原数组对应值） 赋值给原数组中，当外层 for 循环完成对数组的遍历时，此时原数组也得到了正确的顺序。
2.5：计数排序的特性
适用范围：数据范围比较集中时，效率很高
时间复杂度：O(N+range)
空间复杂度：O(range)
这篇关于归并排序/计数排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
