个人主页：秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 系列专栏：《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482
目录
归并排序
代码实现（递归）
代码实现（非递归）
计数排序（非比较排序）
代码实现
排序算法的复杂度及稳定性
前言
hello! 各位铁子们大家好哇。
今日更新了归并，计数排序的内容 欢迎大家关注点赞收藏⭐️留言
归并排序
归并过程如下：
代码实现（递归）
//时间复杂度：O(N*logN)
//空间复杂度：O(N)
void _MergeSort(int* a,int begin, int end,int* tmp)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
//[begin,mid][mid+1,end]
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid+1, end, tmp);
//[begin,mid][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, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}
分析：因为是使用递归实现，开始时需要创建一个新的数组，且递归需要一个区间，因此我们要另外定义一个函数来实现递归。递归的过程跟二叉树的后序遍历类似，应当注意递归的取值范围和结束条件。归并时，我们把左右两个区间的数从头开始比较，小的就放到tmp数组中。第一个while循环的结束条件是直到某一边的数全部放到tmp就结束。然后就把另一个区间的数，全部依次放入tmp数组中，最后再把tmp的数复制给原数组。
代码实现（非递归）
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i+gap, end2 = i +2* gap-1;
//[begin1,end1][begin2,end2]归并
if (end1 >= n || begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
int j = begin1;
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);
}
分析：gap表示每组数的个数。非递归的实现是，开始每组一个数，两两合一，后面比较的过程和递归一样。不过需要注意越界的问题，当end1或者begin2>=n时，就已经越界，这时候就结束循环。当只是end2>=n时，前面数据没有越界，只需要把end2改成n-1即可。一趟归并结束后，gap变为2倍，进行后面的归并，直到gap>=n就停止。
计数排序（非比较排序）
代码实现
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
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 i = 0;
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
}
分析：计数排序主要有两步：
统计相同元素出现的次数根据统计的结果将序列回收到原来的序列中
计数排序需要我们新创建一个统计数组，按理来说，数组下标就可以用来当作统计的数，该位置就来存放该数出现的次数。但是，如果要排序的数是从一千多开始的，这样前面的空间就全部浪费了。所以我们采用相对映射的方法。即用待排序的数中，最大的数-最小的数+1就可以得到范围，从而减少空间浪费。接着用原数组的数减去最小值，将该值作为count数组的下标，即相对映射。最后进行排序，记得加回最小值min，这样数据才不会被改变。
排序算法的复杂度及稳定性
稳定性：指的是相同的数，在排序之后的相对位置没有改变。
分析：
时间 空间
直接插入：明显的等差数列 无新空间开辟希尔：前面文章已分析 无 选择：参考动图 无堆排序：前面文章已分析 无冒泡：等差数列 无快排：二分的思维 看递归深度归并：二分的思维 开辟新的数组
稳定性通过假设来确定，只要有特例是不稳定的，那就是不稳定的。
推荐阅读
您阅读本篇文章共花了：
发表评论