文章目录
一、什么是归并排序
归并排序是建立在归并操作上的一种有效，稳定的排序算法。该算法是采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
二、代码及过程
时间复杂度O（N*logN)
空间复杂度O(N）
稳定性：好
递归实现
void MergeSort(int* a, int n)//归并排序
{
int* tmp =(int*) malloc(sizeof(int) * n);//malloc一个同a数组一样的空间的数组
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, 0,n-1,tmp );// 套用递归
free(tmp);
tmp = NULL;
}
// 递归实现 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);//[begin,mid]进去 _MergeSort(a, mid + 1, end, tmp);//[mid+1,end]进去 //归并（最小情况两个元素到这，此时begin=mid,mid+1=end） int begin1 = begin; int end1 = mid; int begin2 = mid + 1; int end2 = end; int i = begin; //归并 while (begin1 <= end1 && begin2 <= end2)//取小的元素尾插到tmp { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } if (begin1 <= end1)//若出现一边未尾插完则到这往后尾插 { tmp[i++] = a[begin1++]; } if (begin2 <= end2) { tmp[i++] = a[begin2++]; } //把tmp数组copy到原数组//这里是全部排序完才copy回原数组 memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); }
非递归实现
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)
{
//gap个数据归并
for (int j=0; j < n; j += 2 * gap)
{
int begin1 = j; int end1 = j + gap - 1;
int begin2 = j + gap; int end2 = j + 2 * gap - 1;
//
if (end1 > n)//第一组越界-只有一种情况-一个一个数都没有--n=0
{
break;
}
if (begin2 > n)
//第二组全部越界-此时第一组已经归并完成并打印到a数组上了-直接break
{
break;
}
if (end2 > n)//第二组部分越界-只需要把界限改为最后的元素即可
{
end2 = n - 1;
}
int i = j;
while (begin1 <= end1 && begin2 <= end2)//取小的元素尾插到tmp
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
if (begin1 <= end1)//若出现一边未尾插完则到这往后尾插
{
tmp[i++] = a[begin1++];
}
if (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//把tmp数组copy到原数组
memcpy(a + j, tmp + j, sizeof(int) * (end2 -j+ 1));
}
gap *= 2;
printf("\n");
}
free(tmp);
tmp = NULL;
}