剑指offer之归并排序
1 问题
是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法
2 分析过程
-
1 4 3 2 6 8 7 5
-
-
1 4 3 2 6 8 7 5
-
-
1 4 3 2 6 8 7 5
-
-
1 4 2 3 6 8 5 7
-
-
1 2 3 4 5 6 7 8
-
-
1 2 3 4 5 6 7 8
这里最关键的就是我们需要分析比如我们分治后变成了1 、4 和 2 、3这2部分数据，我们现在需要对这4个数排序，如果我们直接在这个数组里面操作下标对比，感觉分析起来很复杂，那我们可以借助辅助数组来分析，这个辅助数组的大小也是4，然后分别在2个数组1、4里面搞一个首指针，在2、3里面搞一个首指针，然后分别进行对比，然后小的数据放入辅助数组，哪个首指针插入辅助数组我么就向后移动，指导右一个手指针移动到尾巴，我们就结束比较，然后我们把右一个数组里面没有到尾巴的首指针再次移到尾巴，赋值给辅助数组就可以，然后我们辅助数组是排序好的元素，我们再把辅助元素里面的数据赋值给原数组。
-
1、 4 2、 3
-
-
i = start j = mid+1 end
对比数据时候循环终止条件
-
while (i != mid + 1 && j != end + 1)
-
-
{
-
-
}
-
3 代码实现
-
#include <stdio.h>
-
-
void merge(int* source, int* temp, int start, int mid, int end)
-
{
-
if (source == NULL || temp == NULL)
-
{
-
printf("merge source or temp is NULL\n");
-
return;
-
}
-
int i = start, j = mid + 1, k = start;
-
while (i != mid + 1 && j != end + 1)
-
{
-
if (source[i] > source[j])
-
temp[k++] = source[j++];
-
else
-
temp[k++] = source[i++];
-
}
-
while (i != mid + 1)
-
temp[k++] = source[i++];
-
while (j != end + 1)
-
temp[k++] = source[j++];
-
for(int h = start; h <= end; ++h)
-
{
-
source[h] = temp[h];
-
}
-
}
-
-
void mergeSort(int* source, int* temp, int start, int end)
-
{
-
if (source == NULL || temp == NULL)
-
{
-
printf("mergeSort source or temp is NULL\n");
-
return;
-
}
-
if (start < end)
-
{
-
int mid = start + (end - start) / 2;
-
mergeSort(source, temp, start, mid);
-
mergeSort(source, temp, mid + 1, end);
-
merge(source, temp, start, mid, end);
-
}
-
}
-
-
int main(void) {
-
int source[] = {2, 3, 1, 5, 4, 9, 8, 6, 7};
-
int length = sizeof(source) / sizeof(int);
-
int temp[9];
-
mergeSort(source, temp, 0, length - 1);
-
for (int i = 0; i < length; ++i)
-
{
-
printf("%d\t", temp[i]);
-
}
-
return 0;
-
}
4 运行结果
1 2 3 4 5 6 7 8 9
5 总结
归并排序，我们需要对数组里面的几个子数组元素进行对比然后移动下标操作，感觉非常复杂，这个时候我们应该借助辅助数组来实现，不就是对比2个数组里面的数据吗？我们把辅助数组的大小设置2个数组元素大小之和，然后搞2个首指针，对比，然后哪个数据小，就插入到辅助数组，然后移动相应的指针就行，然后有一个数组里面的数据肯定都会插入到辅助数组，我们再把另外一个数组里面剩余的元素插入辅助数组，辅助数组就排序好了，然后我们再把辅助数组辅助给原数组就ok了。
1 、4 和 2 、3
辅助数组里面的值变化
-
1 * * *
-
-
1 2 * *
-
-
1 2 3 *
-
-
1 2 3 4
归并排序用到了辅助数组和2首指针思想，等辅助数组排序好了再赋值给原数组，打死也不要忘记。
这个问题的本质我们需要知道两个排序的数组，如果能移动里面的数据，确保两个数组的数据依次是都是排序的，比如我们数组如下
int source[] = {2, 6, 1, 4, 5, 9, 3, 7, 8};
现在我们把这个数组里面的部分原始分割成2部分，列如第一个元素2和第二个元素6是一个子数组，第三个元素1和第四个元素4是一个子数组，每个子数组排序都好了，我们现在需要把这个2个子数组里面的数据进行排序，也就是2个子数组的起始下标是0~1 2~3排序好了后把原数组变成
1 2 4 6 5 9 3 7 8
我们实现标准的通用代码如下
-
#include <stdio.h>
-
-
void printDatas(int* datas, int len)
-
{
-
for (int i = 0; i < len; ++i)
-
{
-
printf("%d\t", datas[i]);
-
}
-
printf("\n");
-
}
-
-
void sort(int* datas, int start1, int end1, int start2, int end2)
-
{
-
if (datas == NULL)
-
{
-
printf("datas is NULL\n");
-
return;
-
}
-
if (start1 > end1 || start2 > end2)
-
{
-
printf("start1 > end1 || start2 > end2\n");
-
return;
-
}
-
int length = end1 - start1 + end2 - start2 + 2;
-
int copy[length];
-
int i = start1, j = end1, k = start2, h = end2, m = 0, n = 0;
-
//用2个指针把指向的值进行对比，然后向右移动，这里需要要求2个数组都是排序好的，
-
while (i != j + 1 && k != h + 1)
-
{
-
if (datas[i] > datas[k])
-
{
-
copy[m++] = datas[k++];
-
}
-
else
-
{
-
copy[m++] = datas[i++];
-
}
-
}
-
//把剩余的一个数组里面的值赋值给我们的copy数组
-
while (i != j + 1)
-
copy[m++] = datas[i++];
-
while (k != h + 1)
-
copy[m++] = datas[k++];
-
//把copy数组再赋值给原数组
-
printDatas(copy, length);
-
i = start1;
-
k = start2;
-
for (; n <= end1 - start1; ++n)
-
{
-
datas[i++] = copy[n];
-
}
-
for (; n < length; ++n)
-
{
-
datas[k++] = copy[n];
-
}
-
}
-
-
int main(void) {
-
int source[] = {2, 6, 1, 4, 5, 9, 3, 7, 8};
-
int length = sizeof(source) / sizeof(int) ;
-
printDatas(source, length);
-
int temp[9];
-
sort(source, 0, 1, 2, 3);
-
printDatas(source, length);
-
return 0;
-
}
-
-
运行结果如下
1 2 4 6 5 9 3 7 8
现在如果我的2个子数组的起始下标不是0~1和2~3，是0~1和6~8，我们把上面的函数
sort(source, 0, 1, 6, 8);
我们再看运行结果
2 3 1 4 5 9 6 7 8
注意我们这这个sort函数（void sort(int* datas, int start1, int end1, int start2, int end2)），不满足两个子数组数据有交叉的情况，但是对于两个数组的长度没有限制（在合法情况），而且这个两个数组可以不连续， 原始的5个数组是1 2 3 7 8 现在变成了2 3 6 7 8，说明没毛病
然后我们归并排序里面，只不过我们的end1就是mid值，然后start2的值是mid + 1的值，两个子数组是连续的，然后长度也是一致，属于上面的特殊情况。
归并排序是稳定排序算法，适合子数组序列排好序。
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/102752448
- 点赞
- 收藏
- 关注作者
评论（0）