我们之前写的排序是不完全的，所以我们现在来进行适当的补充。
一.归并排序非递归版
之前我们写过递归版的，代码如下：
//归并排序
void _Mergesort(int* arr, int begin, int end, int* tmp)
{
if (begin >= end)
return;
//先递归
int mid = (begin + end) / 2;
_Mergesort(arr, begin, mid, tmp);
_Mergesort(arr, mid + 1, end,tmp);
//并
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
memcpy(arr + begin, tmp + begin, (end - begin + 1)*sizeof(int));
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
//检查
if (tmp == NULL)
{
perror(tmp);
return;
}
_Mergesort(arr, 0, n-1, tmp);
free(tmp);
tmp = NULL;
}现在我们来实现非递归版，这个时候大家可能会想到用模拟思想，是啊，我们在快排非递归部分是用了栈来实现的，但是如果我们仔细思考就会发现，在归并排序这里，如果用栈来实现，根本不是像快排那样的前序思想，现在归并是后序，所以肯定不是简单的栈来解决的
那么我们该如何实现呢？
参考递归版本，我们想，如果我们能够用递归的逆思路，就会简单解决问题，即：我们先一个个排，在两个归并，再4个归并，直到完成全部，当然，也可能是奇数个数，所以大家参考注释，好好理解下我写的代码。
//归并非递归版本
void MergesortNone(int* arr, int n)
{
//第一步：开辟空间
int* tmp = (int*)malloc(sizeof(int) * n);
//检查
if (tmp == NULL)
return;
//第二步：确定间隔
int gap = 1;
while (gap < n)//注意：gap要小于n（元素个数），因为这样才能使正好全部归并，可以画图验证
{
for (int i = 0; i < n; i += 2 * gap)//两组归并到一起后，到下一组
{
//第四步：开始确立区间
int begin1 = i;
int end1 = i + gap - 1;//[begin1,end1]
int begin2 = i + gap;
int end2 = i + gap * 2 - 1;//[begin2,end2]
//如：最开始：[0,0]和[1,1]归并到一起变成两个元素[0,1]
//第五步：检查溢出情况
//我们经过验算发现，只有begin1不会溢出
//当是end1和begin2溢出时，说明后面该区间是有序的
if (begin2 >= n || end1 >= n)
break;
else if (end2 >= n)
end2 = n - 1;
//第六步：大体和递归相同，就是重新排序
int j = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[j++] = arr[begin1++];
}
else
{
tmp[j++]=arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = arr[begin2++];
}
//第七步：拷贝回原数组，注意拷贝的数目
memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
//第八步：改变gap的值，注意是1变2,2变4，……
gap *= 2;
}
free(tmp);
tmp = NULL;
}归并排序的特性总结：
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
补充：我们通常将排序分为以下两种，一种是外排序，一种是内排序
外排序：是指在磁盘等外部设备中进行排序
内排序：是指在内存中进行排序
二.计数排序
数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
当然，如果你现在还没学过哈希表的话，这是一个非常不错的提前预习。
该排序主要就以下两步：
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中
下面我们来实现吧！
void Countsort(int* arr, int n)
{
//第一步：找到最大最小值，好处：便于开辟空间较小，同时加快排序速度
int min = arr[0];
int max = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
//第二步：开辟空间
int range = max - min + 1;
int* count = (int*)calloc(range,sizeof(int));//注意：一定要将开辟的空间初始化为0，否者随机值会影响数据统计
//记住：calloc可以空间初始化为0，malloc不行
//检查
if (count == NULL)
return;
//第三步：统计数目
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//第四步：排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[j++] = i + min;
}
}
//第五步：释放空间
free(count);
count = NULL;
}计数排序的特性总结：
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4.稳定性：稳定
三.桶排序
桶排序思想：简单理解就是将元素按照一定的规律放入几个不同的桶中，在对桶里的元素进行单独排序，最后依次取出桶中元素放入原数组进行覆盖即得到新数组。
代码实现如下：
//桶排序
void Bucketsort(int* arr, int n)
{
//第一步：建桶,我们这里就建5个桶来排序0-19
int bucket[5][10];//建桶，桶最多放十个元素
int bucketsize[5] = { 0 };//对五个桶进行记数并且初始化为0
memset(bucket, 0, 50);
//第二步：将元素放入对应的桶中
for (int i = 0; i < n; i++)
{
bucket[arr[i] / 5][bucketsize[arr[i] / 5]++] = arr[i];
}
//第三步：进行桶内排序
for (int i = 0; i < 5; i++)
{
//由于元素较少，我们利用插入排序
Insertsort(&bucket[i], bucketsize[i]);
}
//第四步：取出放回原数组中
int j = 0;
for (int i = 0; i < 5; i++)
{
int a = 0;
while (bucketsize[i]--)
{
arr[j++] = bucket[i][a++];
}
}
}注意：我们是根据需要建桶的，这和之前不一样，例如我的用例如下：
int main()
{
int arr[] = { 3, 2, 6,19,14,2,7,10,0,2,6, 8, 4, 6, 0, 9, 5, 7, 1 };
Bucketsort(arr, sizeof(arr) / sizeof(arr[0]));
Print(arr, sizeof(arr) / sizeof(arr[0]));
return 0;
}所以我是建5个桶，每个桶放间隔为5的区间元素，你当然可以建更大或更小的桶，要根据需要来即可
最后，感谢大家的支持，我们一起加油！
