排序【归并排序和计数排序】

1.归并排序

1.1 基本思想

并归排序：是建立在归并操作上的一种有效的算法>排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
在这里插入图片描述

1.2 递归法：

也就是说，我们在得到有序列之前，要保证俩个子集有序（左区间和右区间），但子集又要分成俩个小子集来使子集有序，小子集又能分出俩个更小的子集，直到子集无法在分，也就是子集仅剩一个元素。

由于我们不能太早的修改原数组的内容，所以我们需要开辟一块新空间（tmp）来暂时存放内容，等内容全部排好序，再将tmp拷贝给原数组。

由于是递归，如果在开辟空间的函数递归，就会一直开辟空间、释放空间，这样会有效率低下的问题，所以我们用一个子函数来完成排序的部分。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void _MergeSort(int* a, int* tmp, int begin, int end);
//归并排序
void MergeSort(int* a, int n)
{//开辟的空间int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//排序主体_MergeSort(a, tmp, 0, n-1);free(tmp);tmp = NULL;
}void TestMergeSort()
{int a[] = { 9,8,6,2,3,4,5,1,7,10 };MergeSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}

1.2.1 子函数

void _MergeSort(int* a, int* tmp, int begin, int end);

我们先将数组进行分割，分割点就为中间点（mid），分割出 $[b e g in, mi d] [mi d + 1, e n d]$ ，然后当集合只剩下一个元素的时候就跳出递归。

void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);
}

1.2.2 排序主体

然后我们就来完成排序的主体部分，因为我们是用区间来分割数组，所以我们需要四个变量来记录俩个区间的开始和结束。
除此之外，我们还需要一个下标变量来记录元素的所在位置，那么我们给下标初始化就不能给0，而是要给相对位置begin。

我们判断俩个区间哪个值更小（更大），将较小的值存放到tmp数组里，然后让较小的begin++，直到俩个区间中的任意一个区间没有值（begin == end），就跳出循环，然后将有值区间内的剩余值放到tmp数组，最后将tmp数组的值拷贝给原数组。

void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//左区间int begin1 = begin, end1 = mid;//右区间int begin2 = mid+1, end2 = end;//下标int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//拷贝memcpy(a+begin, tmp+begin, (end - begin + 1) * sizeof(int));
}

这个方法与二叉树的后序遍历很相似，先排序后左区间，在排序右区间，最后在将左右区间结合。

完整代码：

用例：int a1[] = { 9, 8, 6, 2, 11, 3, 4, 5, 1, 10, 7 }; 长度为11

#include<stdio.h>
#include<string.h>
#include<stdlib.h>void PrintArray(int* a, size_t n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end){return;}int mid = (begin + end) / 2;_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//左区间int begin1 = begin, end1 = mid;//右区间int begin2 = mid+1, end2 = end;//下标int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//拷贝memcpy(a+begin, tmp+begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, tmp, 0, n-1);free(tmp);tmp = NULL;
}

在这里插入图片描述

1.3 非递归方法：

出发点并不是先排序一个区间再排序另一个区间这样的深度优先遍历（DFS），而是一层一层排序的广度优先遍历（BFS）

类似下图👇：
在这里插入图片描述

1.3.1 初版

由于我们不是递归，所以我们不会用分割，而是用分组，确定每组的元素个数，再进行排序。

我们使用gap来代表每组的个数，然后两组两组的归并，归并一轮后增加gap的数量，直到gap大于大于数组长度，当然也是要将tmp的值拷贝给原数组。

//循环版
void MergeSort2(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//分组 , gap为每组有多少个元素int gap = 1;while (gap < n){for (int i = 0; i < n; i += gap * 2){//左区间int begin1 = i, end1 = i + gap - 1;//右区间int begin2 = i + gap, end2 = i + gap * 2 - 1;//下标int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}gap *= 2;}free(tmp);tmp = NULL;
}

在这里插入图片描述
可以看到运行成功了，但是，这个算法>排序算法仅仅支持长度为2的次方倍的数组，因为gap是以2的倍数增长，那么当这个数组长度不是2的次方倍的话，就一定会越界访问。

举例：int a2[] = { 9,8,6,2,3,4,5,1,10,7 };
在这里插入图片描述
可以看到报错了

1.3.2 优化

我们先来看看左右区间的下标（原数组的长度是10，最后一个元素的下标为9）
在这里插入图片描述
我们可以看到画红线的就是越界了的
我们可以这样解决：当begin2越界，就代表end2肯定也是越界的，那么这次就不排序，直接退出，如果只有end2越界，那我们就将end2修正成 $n - 1$ ，也就是最后一个元素的下标。
这样可以不需要管end1越界的情况，因为end1越界了，begin2肯定也越界了，就会直接退出。

			//左区间int begin1 = i, end1 = i + gap - 1;//右区间int begin2 = i + gap, end2 = i + gap * 2 - 1;if (begin2 > n){break;}if (end2 > n){end2 = n - 1;}

这样我们就不用管这个数组是不是2的倍数，是不是偶数，因为会将end2修正为n-1，归并并没有规定排序规定两个子集的长度是一样的，所以我们可以把一部分已经排好序但是begin2越界的组留下来，等到最后排序（中途也有可能排序）

完整代码：

用例：int a2[] = { 9,8,6,2,11,3,4,5,1,10,7 }; 长度为11

//循环版
void MergeSort2(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//分组 , gap为每组有多少个元素int gap = 1;while (gap < n){for (int i = 0; i < n; i += gap * 2){//左区间int begin1 = i, end1 = i + gap - 1;//右区间int begin2 = i + gap, end2 = i + gap * 2 - 1;//printf("[%d][%d] [%d][%d]  ", begin1, end1, begin2, end2);//begin2越界，就代表这个区间不存在if (begin2 >= n){break;}//只有end2越界，修正if (end2 >= n){end2 = n - 1;}//下标int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a+i, tmp+i, sizeof(int) * (end2-i+1));}gap *= 2;}free(tmp);tmp = NULL;
}

在这里插入图片描述

1.4 特性总结

归并的缺点就在于需要 $O (N)$ 的空间复杂度，归并排序主要是解决数据在磁盘（固态硬盘）中的外排序问题。
时间复杂度： $O (N * l o g N)$
空间复杂度： $O (N)$
稳定性：稳定

2. 计数排序

计数排序其实是一种非比较排序，是不需要进行数据之间比较大小的排序。
操作步骤：

统计相同元素出现的次数
根据统计的结果，将序列回收到原来的序列中

2.1 操作讲解：

我们既然要统计次数，那么就需要建立一个tmp数组（要将tmp数组里的元素都初始化成0）。

在这里插入图片描述
然后我们遍历一遍a数组，计算a数组下标元素出现的次数，拿a[0]也就是9来举例。
当a数组遍历到9的时候，那么tmp数组中下标为9的元素就+1，换成代码就是++tmp[a[i]]，将a[i]作为tmp的下标。

在这里插入图片描述
这样依次类推，直到遍历完a数值，然后再遍历一遍tmp数组，将tmp数组中非零值的下标依次拷贝到原数组中。

但是，我们这里使用的绝对位置，如果这些数是从100开头，然后只排序10个数（101到110），那么我们真正会利用到的也就是一百以后的空间，前100个空间就就浪费了，所以我们要用相对位置。

2.2 相对位置

我们要在上文的遍历a数组和开辟tmp前，先遍历一遍a数组，找到其中的最大值和最小值，然后让他们相减再加一，就是我们需要的范围了(int range = max - min + 1;)，就拿上文中a数组的0~9来说吧，先遍历一遍，找到min = 0, max = 9，那么我们再根据range的公式得出 range = 10，再用range来开辟tmp数组。

void CountSort(int* a, int n)
{int min = a[0];int max = a[0];//通过遍历来获取max和min的值for (int i = 0; i < n; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}//计算得出range的值并开空间int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");return;}//排序……
}

然后再进行上文的操作，但到了回收的时候就要注意了，这时就不能是直接让tmp下标赋值给a数组，而是a[i++] = j + min(i为a数组的下标，j为tmp数组的下标)。

2.3 完整代码

用例：int a1[] = { 9, 8, 6, -2, -11, 3, 4, 5, 1, 10, 7,10,7 ,9, 8, 6, 3, 4, 5, 1, 7, 7, 8, 6, -2, -11, 5, 1 };

void CountSort(int* a, int n)
{int min = a[0];int max = a[0];//通过遍历来获取max和min的值for (int i = 0; i < n; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}//计算得出range的值并开空间int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");return;}//排序主体//计数for (int i = 0; i < n; i++){count[a[i] - min]++;}//回收int j = 0;for (int i = 0; i < range; i++){while (count[i]){a[j++] = i + min;--count[i];}}free(count);count = NULL;
}