归并排序

时间复杂度O(N*logN)

如果两个序列有序,通过归并,可以让两个序列合并后也有序,变成一个有序的新数组

对于一个数组,如果他的左右区间都有序,就可以进行归并了

归并的方法

将数组的左右两个有序区间比较,每次都取出一个最小的,然后放入临时数组(不能在原数组上修改,因为修改原数组需要挪动数据,时间复杂度高)

但是对于任意一个数组而言,他的左右区间并不有序,如果想要使用归并排序,就要想办法取出数组的有序区间

这里可以使用递归拆分数组,当数组足够小(每一个区间都只有一个数据时),该区间就一定有序,就可以使用归并排序了

可以设置一个temp数组,用来存储分解的区间并进行排序,归并排序完成后再将temp拷贝回原数组的对应区间,直到递归完全结束(原数组有序)

代码

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin == end)return;int mid = (begin + end) / 2;//开始递归_MergeSort(a, begin, mid, tmp);_MergeSort(a, 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 (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//判断哪个区间全部放入tmp,再将另一个区间全部放入tmpwhile (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);//释放tmpfree(tmp);tmp = NULL;
}

归并排序的非递归方法

归并排序需要将递归改为循环

不方便使用栈来实现,因为不同于快速排序类似前序遍历,归并排序的递归类似于二叉树的后序遍历

问题核心

归并排序需要两个区间进行归并,

而如果使用栈,则当取到需要归并的两个区间的第二个时

第一个区间就已经被pop出栈了,无法知道哪个区间需要和当前区间归并

解决方法

可以将数组看作一个一个数(一个数就是一个区间),然后每两个就进行归并

将归并后的两个数再看作一个区间,再与其他区间进行归并

即直接从叶子节点向前走(回溯)

可以设置gap = 2^n来归并每组数据

设置每个区间的首尾为b n(begin n),e n(end n)

eg.

由图可知,e1 = b1 + gap - 1,b2 = b1 + gap

后续同理

基础代码框架(存在问题)

根据当前的思路,可以写出大概的代码

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 j = 0; j < n; j += 2 * gap)//保证每一个区间都被取到{int begin1 = j, end1 = j + gap - 1;int begin2 = j + gap, end2 = begin2 + gap - 1;int i = j;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//判断哪个区间全部放入tmp,再将另一个区间全部放入tmpwhile (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + j, tmp + j, sizeof(int) * 2 * gap);}gap *= 2;}free(tmp);tmp == NULL;
}

代码问题(数组越界)

当前代码可能存在数组的越界访问

理论上来讲,除了begin1 = j < n外,其他的begin2, end1, end2都可能越界

因此需要分开处理这些问题

1.end1越界

end1越界(end1后面就没有数据了)说明当前没有第二组数据,而第一组只有一部分,且有序

因此当前这一组就不需要再进行归并了,直接让这一组准备下一层归并

2.begin2越界

begin2越界也不用归并,原因与end1越界相同

3.end2越界

end2越界需要归并,因为在begin2与end2中还存在部分有序数据,因此需要归并组成新区间

但是想要归并就需要修正end2,保证end2不再越界

4.修改后的代码

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 j = 0; j < n; j += 2 * gap)//保证每一个区间都被取到{int begin1 = j, end1 = j + gap - 1;int begin2 = j + gap, end2 = begin2 + gap - 1;int i = j;if (end1 >= n || begin2 >= n)//end1和begin2越界,跳出当前循环,不归并{break;}if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//判断哪个区间全部放入tmp,再将另一个区间全部放入tmpwhile (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));//使用修正后的区间长度}gap *= 2;}free(tmp);tmp == NULL;
}