排序算法 归并排序 MergeSort -- C语言实现
归并排序
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
- 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
- 自下而上的迭代;
用途
速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列.
也常用于外排序实现.
算法步骤
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
- 重复步骤 3 直到某一指针达到序列尾;
- 将另一序列剩下的所有元素直接复制到合并序列尾。
递归实现
//递归归并排序分三步
/*
* 1、递归
* 2、合并
* 3、拷贝
*/
/* 时间复杂度分析
归并算法中比较耗时的是归并操作,也就是把两个子数组合并为大数组
* 每一层都要归并n个数,一共logN层,所以O(N*logN)
*/
void _MergeSort(int *a , int begin , int end ,int *tmp)
{
//返回条件:只有一个的时候返回
if (begin >= end)
{
return;
}
//区间
int mid = (begin + end) / 2;
//类后序遍历,递归让子区间有序
_MergeSort(a, begin, mid , tmp);//另一种时mid+1
_MergeSort(a, mid+1, end , tmp);
//合并
int begin1 = begin; int begin2 = mid + 1; //左右数组最小下标(升序要从小开始比较)
int end1 = mid; int end2 = end;
int i = begin; //tmp起始位置
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[i] = a[begin1++];
}
else
{
tmp[i] = a[begin2++];
}
i++;
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//拷贝回去原数组
/*
1、一个一个交换
2、字符函数mem系列
*/
memcpy(a + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}
void MergeSort(int*a, int begin1)
{
int *tmp = (int *)malloc( begin1 * sizeof(int));
if (!tmp)
{
perror("malloc fail");
exit(1);
}
_MergeSort(a, 0, begin1 - 1, tmp);
free(tmp);
}
//当递归到只有一个数时,就相当于有序了,一个即有序,所以直接返回
非递归实现
void MergeSortNonR(int *a, int n)
{
//range = 范围、区间。layer = 层数
// 第一个结束下标是第二个起始下标-1
// 每个起始位置可以由循环次数控制 ---- 设一个循环次数i ---- 要循环多少次?
// 结束条件是:range == n
// 下一轮区间变大可以由层数控制 ---- 设一个层数控制N
// 合并时需要两组 ,两组区间一轮循环---- 设两组起始和结束下标
int *tmp = (int*)malloc(n*sizeof(int));
if (!tmp)
{
perror("malloc fail");
exit(-1);
}
int begin1 = 0; int begin2 = 0;
int end1 = 0; int end2 = 0;
//int i = 0;
int rangeN = 1;//一个begin到end 的范围
while (rangeN < n)
{
int j = 0;
//控制变量让其进入下一轮
for (int i = 0; 2 * rangeN * i < n; i++)
{ //范围:2、4、8、16 --- 2^rangeN == range=range*2
//[0,1][2,3][4,5]...到[0,1,2,3][4,5,6,7][8,9,10,11]
begin1 = 2 * rangeN * i; // 0 ,2 ,4 / 0 ,4 ,8 / 0 , 8 ,16 , 24 /
begin2 = begin1 + rangeN ; // 1 ,3 ,5 / 2 ,6 ,10 / 4 , 12, 20 , 28
end1 = begin1 + rangeN - 1;
end2 = begin2 + rangeN - 1;
//修正
if (end1 >= n-1)
{
end1 = n - 1;
// 不存在区间
begin2 = n; //随便写
end2 = n - 1;//小于begin2就行
}
//else if (end1 == n-1)
//{
// // 不存在区间
// begin2 = n;
// end2 = n - 1;
//}
else if (end2 > n-1) //必须要if,否则就是end1 < n-1 => 可能出现end2 也小于n-1
{
end2 = n - 1;
}
//归并
/*
1、一组一组拷贝:比较一组完拷贝到tmp后,就拷贝回原数组,
2、一轮一轮拷贝:比较完一轮所有组后,再拷贝回原数组
*/
j = 2 * rangeN * i;//起始位置
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j] = a[begin1++];
}
else
{
tmp[j] = a[begin2++];
}
j++;
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++]; //只能一个一个拷,或memcpy
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
//归并完一组就拷贝回一组
//memcpy(a + 2 * rangeN * i, tmp + 2 * rangeN * i, (end2 - 2 * rangeN * i + 1) * sizeof(int));
}
memcpy(a, tmp, (n)*sizeof(int));
rangeN *= 2;
}
}
本文来自博客园,作者:HJfjfK,原文链接:https://www.cnblogs.com/DSCL-ing/p/18345466
热门相关:绝天武帝 我真不是学神 极品明君 与你相恋的小时光 呆萌配腹黑:绝宠小冤家