动静图结合详解: 归并排序 ，计数排序
每博一文案
我们常常会遇到各种各样的坎坷和困境，当我们被现实压得喘不过气时，
总希望能有人能帮我们一把，但现实是，当我们有难时，不仅没人帮，
就连那些昔日的好友，也都消失了，半年已过，慢慢的明白了一个道理：
困难要自己扛，眼泪要自己擦。因为靠山，山会倒，靠人，人会跑，
靠来靠去，你就发现了，最后唯一能靠的是你自己。
就像季羡林先生在，悲喜自度中说的那样，在人生的道路上，每个人都是孤独的旅客。
人间万千光景，苦乐喜忧，跌撞起伏，除了自度。他人爱莫能助，人生如逆旅，道阻且长。
有些困难只能自己杠，眼泪只有自己擦。
当我们想要求得到别人的帮助时，发现人人都有门前的雪，家家都有一本难念的经，
经历过生活的起起伏伏后，才明白没有谁是永远的避风港，只有自己才是避风躲雨的屋檐。
—————— 一禅心灵庙语
文章目录
归并排序的基本思想
归并排序(merge sort) 是利用 归并 的思想实现的排序方法，该算法采用经典的 分治 (divide-and-conquer) 策略:
- 分(divide)：将问题分成一些小的问题，然后递归求解
- 治 (conquer): 将分的阶段得到的各个答案[修补] 在一起
即：分而治之
归并排序 就是利用 归并 的思想实现的排序方法。它的原理是假设初始序列含有 n 个记录，则可以看成是 n 个有序的子序列，每个序列的长度为 1， 然后两两归并，三三归并 … 直到所有数值都归并了，就有序了。
归并排序,升序
归并排序,升序的步骤
- 首先我们需要开辟一个大小和原数组一样的的临时数组，用于存放排序好的数值。
- 我们需要将(原数组)序列分组，分序列
- 一直分序到只有一个元素或是没有元素时，就说明该部分的序列已经有序了，分解就结束了
- 分解结束了，开始合并，这里是升序，通过比较分序列好的，数值，将比较小的赋值到临时数组中，所有排序好的数值都赋值到了临时数组中去。
- 最后将数值排序好的临时数组中的内容，拷贝,覆盖到原数组中去，然后释放临时数组的空间.
归并排序,动图如下
- 分：的过程只是为了分解
- 治：分组完成后，开始对每组进行排序，然后合并成一个有序的序列，直到最后将所有分组合并成一个有序序列。
可以看大这种结构很像一颗 完全二叉树 ，本文的归并排序我们采用 递归实现 (也可采用迭代循环的方式实现)。分的阶段 可以理解为就是递归拆分，得到子序列的过程。
归并排序静态的详细图示步骤
- 首先需要一个无需的数组
- 将序列分解，直到 只有一个数值或者，不存再的序列
每次以 除以 2 的倍数,分其序列
- 再分半
- 再分半
- 一一归并
将分解到最后一个数值后，归并起来
6 < 10 6 先归并入临时数组, 1 < 7 1 先归并入临时数组 3 < 9 , 2 < 4
- 再两两归并
6,10 和 1,7 归并为 第一组为 1,6,7,10
3,9 和 2,4 归并为 第二组为 2,3,4,9
- 最后四四归并，临时数组有序了
- 归并排序的最后一次合并 升序
[begin1] = 1 < 2 = [begin2] ,升序，小的先入临时数组, 1 填入临时数组中，并且 begin1 ++ 右移
[begin2] = 2 < 6 = [begin1], 2 填入临时数组中，并且 begin2++ 右移
[begin2] = 3 < 6 = [begin1], 3 填入临时数组中,并且 begin2++ 右移
[begin2] = 4 < 6 = [beign1], 4 填入临时数组中,并且 begin2++,右移
[begin1] = 6 < 9 = [begin2], 6 填入临时数组中，并且 begin1++,右移
[begin1] = 7 < 9 = [begin2], 7 填入临时数组中，并且 begin1++,右移
[begin2] = 9 < 10 = [begin1], 9 填入临时数组中，并且 begin2++,右移
右序列结束了，将左序列剩余的没有填入到 tmp临时数组中数值，全部填入进去
左序列 只剩下一个 10 了,填入到临时数组 tmp 中去
最后，将临时数组中排序好的数值，按照下标顺序，一次将全部数值拷贝到 原数组 中去
如图所示：这是最后一次的合并(归并) 操作，是两个有序序列
- 从有序序列开始挨个比较，这里比较 1 和 2，1 < 2 ,那么 1 进入临时数组中，并且将自己的指针右移动一位
- 由于上一次 2 大于 1，指针并为移动，然后是 2 和 3 对比， 2 < 3 ,2 进入到临时数组中，并且将自己的指针右移动一位。
- …
- 如果某一组的数值已经全部进入临时数组，那么剩余的一组的剩余有序序列直接追加到临时数组中去。
- 将
temp临时数组的内容拷贝到原数组中去，完成排序 - 最后，将临时数组的空间，释放掉
具体归并排序,升序的代码如下:
// 打印数组
void printArray(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 归并排序,升序，分解,归并
void _mergeSortAsc(int* arr, int left, int right, int* tmp) // tmp 临时数组
{
if (left >= right) // 递归结束条件,当序列中只有一个数值(left == right)或者不存在该序列(left > right)时,就返回,
{
return;
}
int mid = (left + right) >> 1; // 分组,分解
// 假设 [left, mid] [mid+1, right] 有序,那么我们就可以归并了
_mergeSortAsc(arr, left, mid, tmp); // 左区间 递归分解
_mergeSortAsc(arr, mid + 1, right, tmp); // 右区间 递归分解
int begin1 = left, end1 = mid; // 左区间的范围下标,保存
int begin2 = mid + 1, end2 = right; // 右区间的范围下标,保存
int index = left; // 数组的起始位置,保存
while (begin1 <= end1 && begin2 <= end2)
{ // 只要有一个序列排序完了,就跳出,将剩下的归并到一起
if (arr[begin1] < arr[begin2])
{ // begin1 小,填入临时数组中
tmp[index++] = arr[begin1++];
}
else // begin2 小,填入临时数组中
{
tmp[index++] = arr[begin2++];
}
}
// 跳出循环,将剩下没有填入到临时数组中的数值,归并到临时数组中
while (begin1 <= end1)
{ // 左区间序列没有归并完
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
// 右区间序列,没有归并完,
tmp[index++] = arr[begin2++];
}
// 将临时数组排序好的,拷贝覆盖到原数组中去
for (int i = left; i <= right; ++i)
{
arr[i] = tmp[i];
}
}
// 归并排序升序的主函数
void mergeSortAsc(int* arr, int n)
{
// 堆区上开辟空间,作为临时数组使用
int* tmp = (int*)malloc(sizeof(int) * n);
if (NULL == tmp)
{
perror("malloc error"); // 提示错误
exit(-1);
}
_mergeSortAsc(arr, 0, n - 1, tmp);
free(tmp); // 释放 tmp 的空间
tmp = NULL; // 置为 NULL, 防止空指针访问
}
上述代码解析:
if (left >= right)：递归结束条件,当 左右序列分解到只有一个数值时left == right返回，
left > right序列不存在，递归结束，返回
int mid = (left + right) >> 1;除以 2 ，中间下标，分解[left, mid] [mid+1, right]：[left, mid] 左序列范围的，[mid+1,right] 右序列范围的while (begin1 <= end1 && begin2 <= end2)：表示当左右序列中存在一个序列归并入临时数组完了，跳出循环，将剩余一个没有结束的，剩下的全部数值填入到数组中去
while (begin1 <= end1)左序列没有完，将其数值全部填入数组中去。- 后置 ++ ，
归并排序,降序
归并排序的降序，只需要将归并时，把比较大的先填入临时数组中就可以了。
将 if (arr[begin1] < arr[begin2]) 改为 if (arr[begin1] > arr[begin2]) 大于号，大的填入临时数组中去。
具体代码实现如下:
// 打印数组
void printArray(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 归并排序,降序
void _mergeSortDesc(int* arr, int left, int right, int* tmp) // tmp 临时数组
{
if (left >= right) // 递归结束条件:只有一个数值或者序列不存在
{
return;
}
int mid = (left + right) >> 1;
// [left, mid] [mid+1, right]
_mergeSortDesc(arr, left, mid, tmp); // 左区间范围,分解归并
_mergeSortDesc(arr, mid + 1, right, tmp); // 右区间范围,分解归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left; // 保存数组起始位置
while (begin1 <= end1 && begin2 <= end2) // 其中一个结束了,跳出循环
{
if (arr[begin1] > arr[begin2]) // begin2 大，填入临时数组中
{
tmp[index++] = arr[begin1++];
}
else // begin2 大，填入临时数组中
{
tmp[index++] = arr[begin2++];
}
}
// 跳出循环,临时将没有结束的数组的内容填入到临时数组中
while (begin1 <= end1)
{ // begin1 左边序列没有结束
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{ // begin2 右边序列没有结束
tmp[index++] = arr[begin2++];
}
// 将临时数组排序好的内容,拷贝覆盖到原数组中
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
// 归并排序,降序,主函数
void mergeSortDesc(int* arr, int n)
{
// 内存堆区上开辟空间, 用作临时数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (NULL == tmp)
{
perror("malloc error"); // 提示错误
exit(-1); // 程序非正常结束
}
_mergeSortDesc(arr, 0, n - 1, tmp); // 归并排序
free(tmp); // 释放tmp 空间
tmp = NULL; // 置为NULL,防止非法访问
}
非递归实现,归并排序,升序
递归深度太深，程序是没有错的，但是栈的空间不不够用。
递归的缺陷: 栈帧深度太深，栈空间不够用，可能会溢出
递归改非递归的方式有两种
- 直接改循环，如(斐波那契数列)
- 借助自己或库中的栈，模拟递归的过程，入栈出栈
这里我们使用 循环来代替 递归，归并排序的非递归算法并不需要借助栈来完成，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序：如下示图：
上述情况是一种非常理想的情况，但是事实上，这种可能情况的可能性，比较少。
为了，保证，其排序的完整性。我们需要考虑其他的情况。具体如下：三种情况
第一种情况:
当最后一个小组进行合并时，倒数第一个小区间存在，但是该区间元素个数不够 gap 分时，我们需要在合并序列时，将对倒数第一个区间存在但不够的问题的，进行边界上的调整控制，防止数组越界，访问了 。可以调整为数组的最后一个下标位置 n-1 ; 如下图示:
第二种情况:
当最后一个小组进行合并时，倒数第一个右小区间 不存在，此时便不需要对该不存的右小区间进行合并了，因为不存在吗 ， 我们直接退出就可以了，因为前面的左区间上的数值已经排序好了。如下图示:
第三种情况:
进行最后一个小组进行合并时，倒数第二个小区间不存在，并且倒数第 一个 小区间的元素个数不够 gap 分组，此时也不需要对该小区间进行合并，（与 第一种情况一样处理）。
我们只要把上述三种情况处理了，就可以写成完整的 非递归，归并排序
具体代码实现如下:
// 归并排序,非递归实现，合并
void _mergerSortNonrAsc(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
{
int index = begin1; // 保存,用于,合并,
int i = begin1;
while (begin1 <= end1 && begin2 <= end2) // 存在一个序列,排序完,就结束，把剩下的那个没有结束的归并上
{
if (arr[begin1] < arr[begin2]) // begin1 < begin2 将小于的填入临时表中
{
tmp[index++] = arr[begin1++];
}
else // begin2 小 填入临时表中
{
tmp[index++] = arr[begin2++];
}
}
// 跳出循环,将剩下的没有填入临时数组的,填入
while (begin1 <= end1)
{ // begin1 没有结束
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2) // begin2 没有结束
{
tmp[index++] = arr[begin2++];
}
for (int j = i; j <= end2; j++)
{
arr[j] = tmp[j];
}
}
// 归并排序,非递归实现
void mergeSortNonrAsc(int* arr, int n)
{
// 堆区上开辟空间,用于临时数组,大小和原数组一样大
int* tmp = (int*)malloc(sizeof(int) * n);
if (NULL == tmp)
{
perror("malloc error");
exit(-1);
}
int gap = 1; // 每组数据个数,从 1 开始分组
while (gap < n) // 每次分组时不可以大于 n(数组大小)
{
for (int i = 0; i < n; i += 2 * gap ) // 2*gap 每次分组扩大2倍
{
// [i, i+gap-1], [i+gap,i+2*gap-1]
int begin1 = i, end1 = i + gap - 1; // 左半区间范围
int begin2 = i + gap, end2 = i + 2 * gap - 1; // 右半区间范围
// 归并过程中右半区间可能不存在
if (begin2 >= n)
{
break; // 跳出循环
}
// 归并过程中右半区间算多了,或者倒数第二个区间少了,修正一下
if (end2 >= n)
{
end2 = n - 1; // 数组最后一个下标位置
}
_mergerSortNonrAsc(arr, begin1, end1, begin2, end2, tmp); // 合并两个有序数列
}
gap *= 2; // 分组 2倍扩容
}
free(tmp);
tmp = NULL;
}
上述代码解析及其注意事项
int gap = 1;以1个数值分组，while (gap < n)分组的大小不可以超过 数组的大小n[i, i+gap-1], [i+gap,i+2*gap-1]假定该序列有序[i, i+gap-1] : 左区间的范围，[i+gap, i+2*gap-1] ：右区间的范围
if (begin2 >= n)第二种情况，归并或者分解时右区间不存在。直接退出，就可以了，前面的区间我们已经排序好了，不用再动了
if (end2 >= n)第一种情况和第三种情况，归并或者分解的时候，右小区间少了，或者第二个区间少了数值，进行一个修正，修正为
end2 = n - 1;数组的最后一个下标位置。
gap *= 2分组扩展一下，继续分解以及归并while (begin1 <= end1 && begin2 <= end2)当左右序列中存在一个序列所有数值归并到了临时数组中，跳出循环，将剩余一个序列的数值没有全部归并到临时数组，的数值归并进入临时数组中
if (arr[begin1] < arr[begin2])升序，将较小的数值，率先归并到临时数组中去
for (int j = i; j <= end2; j++)所有数值归并完了，以后，将临时数组归并排序好的数值，全部拷贝，赋值到原数组中去。
非递归实现,归并排序,降序
同样归并排序，非递归实现的降序，将较大的数值，率先归并到临时数组中就可以了。
如将 if (arr[begin1] < arr[begin2]) 改为 if (arr[begin1] > arr[begin2]) 就可以实现降序了。
具体代码实现如下:
// 归并两个有序的数列,降序
void _mergerSortNonrDesc(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
{
int index = begin1;
int j = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] > arr[begin2]) // begin1 较大，率先填入临时数组中
{
tmp[index++] = arr[begin1++];
}
else // begin2 较小,率先填入临时数组中
{
tmp[index++] = arr[begin2++];
}
}
// 跳出循环,将剩余没有填入的临时数组的数值填入
while (begin1 <= end1)
{ // begin1 没有结束
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
// begin2 没有结束
tmp[index++] = arr[begin2++];
}
//全部数值填入到了临时数组中了,将临时数组排序好的数值，拷贝,赋值到原数组中
for (; j <= end2; j++)
{
arr[j] = tmp[j];
}
}
// 归并排序,降序
void mergerSortNonrDesc(int* arr, int n)
{
// 堆区上开辟空间,用于临时数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (NULL == tmp)
{
perror("malloc error"); // 提示错误
exit(-1); // 程序非正常结束
}
int gap = 1; // 分组标准开始以 1 个元素分组序列
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//[i,i+gap-1] [i+gap, i+2*gap-1]
int begin1 = i, end1 = i + gap - 1; // 左区间的范围保存
int begin2 = i + gap, end2 = i + 2 * gap - 1; // 右区间的范围保存
if (begin2 >= n) // 右区间不存在
{
break;
}
if (end2 >= n) // 右区间少了数值，倒数第二个区间少了数值,修正
{
end2 = n - 1; // 修正数组的最后一个数值下标位置
}
_mergerSortNonrDesc(arr, begin1, end1, begin2, end2, tmp); // 降序归并两个有序序列
}
gap = gap * 2; // 分组扩大 2倍
}
}
归并排序重要思想扩展
归并排序，也叫外排序
内排序: 数据量相对少一些，可以放到内存中进行排序。
外排序 ：数据量较大，内存中放不下，数据只能放到磁盘文件中，排序
对于数据量庞大的序列，排序的话，内排序 是无法实现了，因为内存空间不够存放，而 外排序 其中的归并排序可以胜任这种海量的数据的排序。
例如：
假设我们有 10G 的数据文件放到了硬盘中，需要我们排序一下。可是，我们的内存只有 1G 可以使用。
这里我们就可以使用归并排序的思想：
10G 的文件，我们将其切分成 10 个 1G 的文件，并且让 10 个 1G 的文件有序。
- 每次从
10G的文件中读取一个1G的文件到内存中进行排序（内排序），并将排序好的结果写入到一个临时文件中(就是上面归并排序的临时数组中去)，再继续下一个1G的文件的数据的排序，不断重复这个过程。最终会生成10个各自有序的小文件。每个文件1G的大小 - 将生成的
10个1G的文件进行归并处理，先是归并成 5个2G的文件 ——> 再将 5 个2G的文件，归并成 两个4G和 一个2G的文件 ——> 再将 其归并为一个8G和 一个2G的文件 ——> 最后 归并为了 一个有序的10G文件 。
注意: 这里将两个文件进行 一一归并(合并) ,并不是先将两个文件读入到内存中，然后进行归并的，这时不行的，内存只有 1G 是不够的。这里的 一一归并(合并) 是利用文件输入输出函数，从两个文件中各自读取一个数据，然后进行比较，将比较小的数据写入到一个新的(临时文件) 中去，然后再读取，再比较，再写入，最终将两个文件中的数据全部写入到另外一个文件(临时文件) 中去，此时这个文件的内容就是有序的了。
这就是归并排序的思想：将一个一个无序的数据，分解成一个一个有序的数据，再一一归并成一个大的有序数据 分而治之 。
计数排序的基本思想
计数排序 是一个非基于比较的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的数值决定的。该算法于 1945年 由 Harold H. Seware 提出。它的优势在于对一定的范围内的整数排序时，它的时间赋值度为 O(n+k) k 表示的是该整数的范围，该排序快于任何比较排序算法。当然，这也是存在一定缺陷的，需要牺牲空间换取时间的做法，而且当 O(k) > O(nlogn) 的时候，效率反而不如基本比较排序，因为基本比较排序的时间复杂度在理论上的下限是 O(nlogn)
计数排序: 名副其实，就是根据 ”计数“ 的方式来进行排序的，而所谓的 计数: 就是统计每个元素数值出现的次数。
再根据统计到的数值次数，进行一个映射的排序 。存在着两种 映射 方式
- 绝对映射
开辟的空间大小是序列中对应的最大数值的大小。如下图:
存在较大的空间上的浪费，如，该序列 [100,101,102,103,101,105,107] ，我们只有 5 个数值需要排序，但是我们却要开辟 100个空间，其中 100 个空间没有用上，浪费了，如下图：
- 相对映射
开辟的空间大小是 数组中最大值 - 数组的最小值 +1 大小的空间。[0~9] 的数组大小为 ; 9-0+1= 10; 进可能上节省了空间。 再通过数值 - 数组中的最小值 映射到对应的数组下标位置。再通过 数组下标 + 数组最小值还原回去，同样是序列 :[100,101,102,103,101,105,107] 只需要开辟: 107 - 100 +1 = 7 ，7 个大小的空间。
如下图：
计数排序"，名副其实，就是根据"计数"的方式来进行排序，所谓"计数"，就是统计每个元素重复出现的次数。
计数排序,升序
计数排序，升序的基本思想
- 这里我们使用 相对映射的方式 ,统计数值出现的个数
- 需要使用 相对映射的方式 的话，我们需要首先找到该数组中的 最大值和最小值 ，通过 计算出
数组的 最大值 - 最小值 +1的 的数值大小，根据该数值开辟临时数组空间（用于统计数组中所有数值出现的个数）因为是 相对映射 ，所以需要 实际数值 - min(数组的最小值) 映射到对应数组的下标位置上去。
- 最后通过统计到的数值个数，进行排序，注意需要将 结果 +
min恢复原来的数值大小 - 释放临时开辟的空间，防止非法访问。
代码具体实现如下:
// 计数排序,升序
void countSortAsc(int* arr, int n)
{
int max = arr[0]; // 数组中的最大值
int min = arr[0]; // 数组中的最小值
for (int i = 0; i < n; i++)
{
// 找数组中的最小值
if (min > arr[i])
{
min = arr[i];
}
// 找数组中的最大值
if (max < arr[i])
{
max = arr[i];
}
}
int range = max - min + 1; // 数组的范围大小 + 1
// 根据计算得到的 数组大小 range 堆区上开辟临时数组，用于统计数值出现的个数
int* count = (int*)malloc(sizeof(int) * range);
// 判断空间开辟是否成功
if (NULL == count)
{
perror("malloc error"); // 错误提醒
exit(-1); // 程序非正常退出
}
memset(count, 0, sizeof(int) * range); // 临时数组元素全部初始化为 0
// 统计原数组中全部数值出现的个数
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++; // 相对映射
}
for (int i = 0, j = 0; i < range; i++)
{
// 根据统计的数值次数，排序
while (count[i]--)
{
arr[j++] = i + min; // 相对映射,+min 将数值还原回去
}
}
free(count); // 释放空间
count = NULL; // 置为 NULL,防止非法访问
}
上述代码解析及其注意事项:
int max = arr[0];int min = arr[0];默认初始的数组中的最大值和最小值是数组中下标为 0 的的数值，防止找到错误的最大最小值
int range = max - min + 1求数组的实际大小，需要 额外 +1 ,如 [0~9] 实际数组的大小是 9-0+1 = 10 ，因为数组是从 0 下标开始的memset(count, 0, sizeof(int) * range);初始化临时数组，将其全部元素初始化为 0count[arr[i] - min]++;相对映射统计，数组中所有数值出现的个数，实际数值 - min(最小值)，注意: 实际赋值排序的时候，需要加回去
+min
arr[j++] = i + min;根据统计到的数值个数，赋值排序，i+min恢复到原来的实际数值。再赋值到原数组中去。
free(count);count = NULL;释放开辟的空间，手动置为 NULL,防止非法访问。
计数排序,降序
计数排序的降序，只需要将最后一步中的，统计的数值个数，赋值排序到原来的数组中时，把统计到的数值个数，从后往前，把统计到的后面的数值，放到原数组的前面就可以了。调换一下赋值顺序，for (int i = 0, j = 0; i < range; i++) 改为 for (int i = range-1, j = 0; i <= 0; i--)其他不变。
具体代码实现如下:
// 计数排序,降序
void countSortDesc(int* arr, int n)
{
int max = arr[0]; // 默认数组中的最大值和最小值为数组下标 0 的是数值
int min = arr[0];
for (int i = 0; i < n; i++)
{
// 找最小值
if (min > arr[i])
{
min = arr[i];
}
// 找最大值
if (max < arr[i])
{
max = arr[i];
}
}
int range = max - min + 1; // 数组的大小 [0~9] = 9-0+1=10;
// 堆区上开辟空间，临时数组计数
int* count = (int*)malloc(sizeof(int) * range);
// 判断堆区上开辟的空间是否成功
if (NULL == count)
{
perror("malloc error");
exit(-1);
}
memset(count, 0, sizeof(int) * range); // 将临时数组中所有的元素初始化为 0
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++; // 相对映射,统计实际数值个数
}
for (int i = range-1, j = 0; i>= 0; i--) // range -1 实际数组最后一个下标位置
{ // j= 0 赋值到原数组的开头开始
while (count[i]--)
{
arr[j++] = i + min; // 恢复到原来的数值大小,赋值给原来的数组中去
}
}
}
计数排序的特别说明
虽然计数排序看上去很强大，但是它存在两大局限性：
- 当数列最大值与最小值差距过大时，并不适用于计数排序
比如：给定 20 个随机整数，范围在 0 到 1亿之间，此时如果使用 计数排序 的话，就需要创建长度为 1 亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。
- 当数列元素不是整数时，并不适用于计数排序
如果数列中的元素都是小数，比如：3.1415926, 或者是 0.00000001 这样的，则无法创建对应的统计数组，这样显然无法进行计数排序。
正是，由于这两个局限性，才使得计数排序不像，快速排序，归并排序那样被人们广泛的使用。
非递归归并排序 与 递归归并排序 性能上的测试
将排序开始之前的时间点 - 排序结束之后的时间点 = 排序的效率了
具体代码实现如下:
// 归并非递归，递归性能测试
void testTop()
{
srand(time(0)); // 时间种子
const int N = 1000000; // 100w
int* a = (int*)malloc(sizeof(int) * N);
int* b = (int*)malloc(sizeof(int) * N);
if (NULL == a || NULL == b)
{
perror("malloc error");
exit(-1);
}
for (int i = 0; i < N; i++)
{
a[i] = rand(); // 产生随机值
b[i] = a[i];
}
int begin1 = clock(); // 非递归归并排序开始之前的时间点
mergeSortNonrAsc(a, N); // 归并排序非递归实现,升序
int end1 = clock(); // 非递归归并排序结束之后的时间点
int begin2 = clock(); // 递归归并排序开始之前的时间点
mergeSortAsc(b, N); // 归并排序递归实现,升序
int end2 = clock(); // 递归归并排序结束之后的时间点
/*
* 排序的效率 = 排序结束之后的时间点 end - begin 排序开始之前的时间点
*/
printf("非递归归并排序：%d\n", end1 - begin1);
printf("递归归并排序：%d\n", end2 - begin2);
free(a);
a = NULL;
free(b);
b = NULL;
}
归并排序，计数排序的完整代码:
下面是有关归并排序，计数排序完整代码的实现，大家可以直接复制，粘贴就可以运行使用了，大家可以运行看看
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
// 打印数组
void printArray(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// 归并排序,升序，分解,归并
void _mergeSortAsc(int* arr, int left, int right, int* tmp) // tmp 临时数组
{
if (left >= right) // 递归结束条件,当序列中只有一个数值(left == right)或者不存在该序列(left > right)时,就返回,
{
return;
}
int mid = (left + right) >> 1; // 分组,分解
// 假设 [left, mid] [mid+1, right] 有序,那么我们就可以归并了
_mergeSortAsc(arr, left, mid, tmp); // 左区间 递归分解
_mergeSortAsc(arr, mid + 1, right, tmp); // 右区间 递归分解
int begin1 = left, end1 = mid; // 左区间的范围下标,保存
int begin2 = mid + 1, end2 = right; // 右区间的范围下标,保存
int index = left; // 数组的起始位置,保存
while (begin1 <= end1 && begin2 <= end2)
{ // 只要有一个序列排序完了,就跳出,将剩下的归并到一起
if (arr[begin1] < arr[begin2])
{ // begin1 小,填入临时数组中
tmp[index++] = arr[begin1++];
}
else // begin2 小,填入临时数组中
{
tmp[index++] = arr[begin2++];
}
}
// 跳出循环,将剩下没有填入到临时数组中的数值,归并到临时数组中
while (begin1 <= end1)
{ // 左区间序列没有归并完
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
// 右区间序列,没有归并完,
tmp[index++] = arr[begin2++];
}
// 将临时数组排序好的,拷贝覆盖到原数组中去
for (int i = left; i <= right; ++i)
{
arr[i] = tmp[i];
}
}
// 归并排序升序的主函数
void mergeSortAsc(int* arr, int n)
{
// 堆区上开辟空间,作为临时数组使用
int* tmp = (int*)malloc(sizeof(int) * n);
if (NULL == tmp)
{
perror("malloc error"); // 提示错误
exit(-1);
}
_mergeSortAsc(arr, 0, n - 1, tmp);
free(tmp); // 释放 tmp 的空间
tmp = NULL; // 置为 NULL, 防止空指针访问
}
// 归并排序,降序
void _mergeSortDesc(int* arr, int left, int right, int* tmp) // tmp 临时数组
{
if (left >= right) // 递归结束条件:只有一个数值或者序列不存在
{
return;
}
int mid = (left + right) >> 1;
// [left, mid] [mid+1, right]
_mergeSortDesc(arr, left, mid, tmp); // 左区间范围,分解归并
_mergeSortDesc(arr, mid + 1, right, tmp); // 右区间范围,分解归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left; // 保存数组起始位置
while (begin1 <= end1 && begin2 <= end2) // 其中一个结束了,跳出循环
{
if (arr[begin1] > arr[begin2]) // begin2 大，填入临时数组中
{
tmp[index++] = arr[begin1++];
}
else // begin2 大，填入临时数组中
{
tmp[index++] = arr[begin2++];
}
}
// 跳出循环,临时将没有结束的数组的内容填入到临时数组中
while (begin1 <= end1)
{ // begin1 左边序列没有结束
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{ // begin2 右边序列没有结束
tmp[index++] = arr[begin2++];
}
// 将临时数组排序好的内容,拷贝覆盖到原数组中
for (int i = left; i <= right; i++)
{
arr[i] = tmp[i];
}
}
// 归并排序,降序,主函数
void mergeSortDesc(int* arr, int n)
{
// 内存堆区上开辟空间, 用作临时数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (NULL == tmp)
{
perror("malloc error"); // 提示错误
exit(-1); // 程序非正常结束
}
_mergeSortDesc(arr, 0, n - 1, tmp); // 归并排序
free(tmp); // 释放tmp 空间
tmp = NULL; // 置为NULL,防止非法访问
}
// 归并排序,非递归实现，合并
void _mergerSortNonrAsc(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
{
int index = begin1; // 保存,用于,合并,
int i = begin1;
while (begin1 <= end1 && begin2 <= end2) // 存在一个序列,排序完,就结束，把剩下的那个没有结束的归并上
{
if (arr[begin1] < arr[begin2]) // begin1 < begin2 将小于的填入临时表中
{
tmp[index++] = arr[begin1++];
}
else // begin2 小 填入临时表中
{
tmp[index++] = arr[begin2++];
}
}
// 跳出循环,将剩下的没有填入临时数组的,填入
while (begin1 <= end1)
{ // begin1 没有结束
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2) // begin2 没有结束
{
tmp[index++] = arr[begin2++];
}
for (int j = i; j <= end2; j++)
{
arr[j] = tmp[j];
}
}
// 归并排序,非递归实现
void mergeSortNonrAsc(int* arr, int n)
{
// 堆区上开辟空间,用于临时数组,大小和原数组一样大
int* tmp = (int*)malloc(sizeof(int) * n);
if (NULL == tmp)
{
perror("malloc error");
exit(-1);
}
int gap = 1; // 每组数据个数,从 1 开始分组
while (gap < n) // 每次分组时不可以大于 n(数组大小)
{
for (int i = 0; i < n; i += 2 * gap ) // 2*gap 每次分组扩大2倍
{
// [i, i+gap-1], [i+gap,i+2*gap-1]
int begin1 = i, end1 = i + gap - 1; // 左半区间范围
int begin2 = i + gap, end2 = i + 2 * gap - 1; // 右半区间范围
// 归并过程中右半区间可能不存在
if (begin2 >= n)
{
break; // 跳出循环
}
// 归并过程中右半区间算多了,或者第二个区间少了,修正一下
if (end2 >= n)
{
end2 = n - 1; // 数组最后一个下标位置
}
_mergerSortNonrAsc(arr, begin1, end1, begin2, end2, tmp); // 合并两个有序数列
}
gap *= 2; // 分组 2倍扩容
}
free(tmp);
tmp = NULL;
}
// 归并两个有序的数列,降序
void _mergerSortNonrDesc(int* arr, int begin1, int end1, int begin2, int end2, int* tmp)
{
int index = begin1;
int j = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] > arr[begin2]) // begin1 较大，率先填入临时数组中
{
tmp[index++] = arr[begin1++];
}
else // begin2 较小,率先填入临时数组中
{
tmp[index++] = arr[begin2++];
}
}
// 跳出循环,将剩余没有填入的临时数组的数值填入
while (begin1 <= end1)
{ // begin1 没有结束
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
// begin2 没有结束
tmp[index++] = arr[begin2++];
}
//全部数值填入到了临时数组中了,将临时数组排序好的数值，拷贝,赋值到原数组中
for (; j <= end2; j++)
{
arr[j] = tmp[j];
}
}
// 归并排序,降序
void mergerSortNonrDesc(int* arr, int n)
{
// 堆区上开辟空间,用于临时数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (NULL == tmp)
{
perror("malloc error"); // 提示错误
exit(-1); // 程序非正常结束
}
int gap = 1; // 分组标准开始以 1 个元素分组序列
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
//[i,i+gap-1] [i+gap, i+2*gap-1]
int begin1 = i, end1 = i + gap - 1; // 左区间的范围保存
int begin2 = i + gap, end2 = i + 2 * gap - 1; // 右区间的范围保存
if (begin2 >= n) // 右区间不存在
{
break;
}
if (end2 >= n) // 右区间少了数值，倒数第二个区间少了数值,修正
{
end2 = n - 1; // 修正数组的最后一个数值下标位置
}
_mergerSortNonrDesc(arr, begin1, end1, begin2, end2, tmp); // 降序归并两个有序序列
}
gap = gap * 2; // 分组扩大 2倍
}
}
// 计数排序,升序
void countSortAsc(int* arr, int n)
{
int max = arr[0]; // 数组中的最大值
int min = arr[0]; // 数组中的最小值
for (int i = 0; i < n; i++)
{
// 找数组中的最小值
if (min > arr[i])
{
min = arr[i];
}
// 找数组中的最大值
if (max < arr[i])
{
max = arr[i];
}
}
int range = max - min + 1; // 数组的范围大小 + 1
// 根据计算得到的 数组大小 range 堆区上开辟临时数组，用于统计数值出现的个数
int* count = (int*)malloc(sizeof(int) * range);
// 判断空间开辟是否成功
if (NULL == count)
{
perror("malloc error"); // 错误提醒
exit(-1); // 程序非正常退出
}
memset(count, 0, sizeof(int) * range); // 临时数组元素全部初始化为 0
// 统计原数组中全部数值出现的个数
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++; // 相对映射
}
for (int i = 0, j = 0; i < range; i++)
{
// 根据统计的数值次数，排序
while (count[i]--)
{
arr[j++] = i + min; // 相对映射,+min 将数值还原回去
}
}
free(count); // 释放空间
count = NULL; // 置为 NULL,防止非法访问
}
// 计数排序,降序
void countSortDesc(int* arr, int n)
{
int max = arr[0]; // 默认数组中的最大值和最小值为数组下标 0 的是数值
int min = arr[0];
for (int i = 0; i < n; i++)
{
// 找最小值
if (min > arr[i])
{
min = arr[i];
}
// 找最大值
if (max < arr[i])
{
max = arr[i];
}
}
int range = max - min + 1; // 数组的大小 [0~9] = 9-0+1=10;
// 堆区上开辟空间，临时数组计数
int* count = (int*)malloc(sizeof(int) * range);
// 判断堆区上开辟的空间是否成功
if (NULL == count)
{
perror("malloc error");
exit(-1);
}
memset(count, 0, sizeof(int) * range); // 将临时数组中所有的元素初始化为 0
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++; // 相对映射,统计实际数值个数
}
for (int i = range-1, j = 0; i>= 0; i--) // range -1 实际数组最后一个下标位置
{ // j= 0 赋值到原数组的开头开始
while (count[i]--)
{
arr[j++] = i + min; // 恢复到原来的数值大小,赋值给原来的数组中去
}
}
}
void sortTest()
{
int arr[] = { 10,6,7,1,3,9,4,2 };
countSortDesc(arr, sizeof(arr) / sizeof(int)); // 计数排序,降序
// countSortAsc(arr, sizeof(arr) / sizeof(int)); // 计数排序,升序
//mergerSortNonrDesc(arr, sizeof(arr) / sizeof(int)); // 归并排序,非递归实现,降序
//mergeSortNonrAsc(arr, sizeof(arr) / sizeof(int)); // 归并排序,非递归实现,升序
//mergeSortDesc(arr, sizeof(arr) / sizeof(int)); // 归并排序,递归实现,降序
//mergeSortAsc(arr, sizeof(arr) / sizeof(int)); // 归并排序,递归实现,升序
printArray(arr, sizeof(arr) / sizeof(int));
/*
* sizeof(arr)/sizeof(int) : 表示数组的大小
* sizeof(arr): 表示数组所占空间的大小,单位字节
* sizeof(int) : 表示数组元素所占空间的大小,单位字节
*/
}
// 归并非递归，递归性能测试
void testTop()
{
srand(time(0)); // 时间种子
const int N = 1000000; // 100w
int* a = (int*)malloc(sizeof(int) * N);
int* b = (int*)malloc(sizeof(int) * N);
if (NULL == a || NULL == b)
{
perror("malloc error");
exit(-1);
}
for (int i = 0; i < N; i++)
{
a[i] = rand(); // 产生随机值
b[i] = a[i];
}
int begin1 = clock(); // 非递归归并排序开始之前的时间点
mergeSortNonrAsc(a, N); // 归并排序非递归实现,升序
int end1 = clock(); // 非递归归并排序结束之后的时间点
int begin2 = clock(); // 递归归并排序开始之前的时间点
mergeSortAsc(b, N); // 归并排序递归实现,升序
int end2 = clock(); // 递归归并排序结束之后的时间点
/*
* 排序的效率 = 排序结束之后的时间点 end - begin 排序开始之前的时间点
*/
printf("非递归归并排序：%d\n", end1 - begin1);
printf("递归归并排序：%d\n", end2 - begin2);
free(a);
a = NULL;
free(b);
b = NULL;
}
int main()
{
//sortTest();
testTop();
return 0;
}
最后:
限于自身水平，其中存在的错误，希望大家可以给予指教，韩信点兵——多多益善，谢谢大家，后会有期，江湖再见 !!!
