我要评论
一、归并排序（递归版）
void _mergesort(int* a, int left, int right, int* tmp)
{
//当区间中只有一个数时就不用再对其进行排序
if (left >= right)
return;
//每次将其区间折半划分为左区间和右区间
int mid = (left + right) / 2;
//再重复划分，直到它的左右区间只剩下一个数，那么再返回
//对其排序
_mergesort(a, left, mid, tmp);
_mergesort(a, mid + 1, right, tmp);
//将其小区间排好序后再排它的大区间
//小区间有序之后大区间排过来也就是有序的了
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int begin = left;
//将左右区间合并为一个区间
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] > a[begin2])
{
tmp[begin++] = a[begin2++];
}
else
{
tmp[begin++] = a[begin1++];
}
}
//两个区间中还剩余数据的那个区间直接尾插到tmp数组后面
while (begin1 <= end1)
{
tmp[begin++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[begin++] = a[begin2++];
}
//最后将排好序的区间拷贝回原来的数组
memcpy(a + left, tmp+left, sizeof(int)*(right - left + 1));
}
void mergesort(int* a, int n)
{
//开一个临时数组用来存放小区间排序后的数据
//最后再将排序后的数组拷贝回原数组中
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == null)
{
perror("malloc fail\n");
return;
}
//归并排序分两区间进行
_mergesort(a, 0, n - 1, tmp);
free(tmp);
}
二、归并排序（非递归版）
当数组长度不是gap倍数时，要注意控制边界。
那这个边界如何控制？
** 将tmp中内容拷贝回原数组**
将间隔为gap的小区间归并后的内容整体拷贝回原数组
void mergesort1(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == null)
{
perror("malloc fail\n");
return;
}
int gap = 1;
while (gap < n)
{
//小区间由gap控制，且每次都是前一个区间和后一个区间
//归并为一个大的有序区间，所以每次i需要加上gap的2倍，
//一次跳过两个区间
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;
int j = i;//由于两个小区间要合并为一个区间，
//然后存放到数组tmp中，合并后数组tmp长度大小
//为两个小区间长度大小之和，然后下次在开始合并时，
//从合并后的右端下标开始赋值，所以tmp下标起始由i
//决定
if (end1 >= n)
{
end1 = n - 1;
begin2 = n ;
end2 = n-1;
}
else if (begin2 >= n)
{
begin2 = n ;
end2 = n-1;
}
else if(end2 >=n )
{
end2 = n - 1;
}
//两个区间中小的数尾插到tmp数组中
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++];
}
}
//将间隔为gap小区间合并后的数组tmp里的内容全部拷贝回原数组中
memcpy(a, tmp, sizeof(int) * n);
gap *= 2;//最后gap变为原来的2倍
}
free(tmp);
}
将间隔为gap的小区间一段一段的拷贝回原数组
void mergesort2(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == null)
{
perror("malloc fail\n");
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;
int j = i;
//由于gap使其分区间块化有序，此时前一个区间的右端
//或者后一个区间的左端超出数组长度了，那么直接
//拷贝到原数组后面
if (end1 >= n || begin1 >= n)
{
break;
}
else if (end2 >= n)
{
end2 = n - 1;
}
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++];
}
//每一次区间间隔为gap的两个区间合并后就将其拷贝到
//原数组中
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
gap *= 2;
}
free(tmp);
}
归并排序将两个有序的区间归并为一个有序的区间
发表评论