数据结构 ——— 归并排序算法的实现

归并排序的思想

归并排序算法的实现

归并排序的思想

将已经有序的子序列合并，得到完全有序的序列，即先使每个子序列有序后，再使子序列段间有序
若将两个有序表合并成一个有序表，称为二路归并

归并排序步骤示意图：

由此可以看出归并排序是需要递归分治解决的，把原数组分治成各个子序列，要先让各个子序列有序，最后才能让整个数组有序

让子序列有序的步骤是：取小的尾插

举例说明：

走到最后一步时，有两个子序列：[1,6,7,10] 和 [2,3,4,9]

这两个子序列都被分解归并为有序了，只要将这两个子序列再次归并，就能有序

所以需要两个指针，指向这两个子序列的开头，找到比较小的那个值，进行尾插

那么尾插就不能在原数组上尾插，因为会覆盖数据

所以要在最开始定义一个和待排序的数据等长的 tmp 数组，来进行尾插

最后再把 tmp 数组中的内容拷贝到原数组，这样，原数组才算完成了排序

归并排序算法的实现

代码演示：

static void _MergeSort(int* tmp, int* a, int begin, int end)
{/*结束条件*/ if (begin == end)return;/*分解*/ int mid = (begin + end) / 2;// [begin,mid] [mid+1,end]_MergeSort(tmp, a, begin, mid);_MergeSort(tmp, a, mid + 1, end);/*归并*/// 第一段子区间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++];}}while (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 size)
{int* tmp = (int*)malloc(sizeof(int) * size);// 判断是否开辟成功if (tmp == NULL){perror("malloc fail");return;}// 归并排序子函数_MergeSort(tmp, a, 0, size - 1);free(tmp);
}

代码解析：

MergeSort 函数用来接收指向待排序数组首元素的指针，和数组长度

要利用 tmp 数组来接收数组 a 排好后的数据

所以不能直接利用 MergeSort 函数来递归，否则每次递归都会定义一个 tmp 函数

在 MergeSort 函数中再定义一个子函数 _MergeSort 函数，利用 _MergeSort 函数递归完成归并排序

由归并排序的思想得出，要先找出中间值，分割成两个子序列

也就是 [begin,mid] [mid+1,end] 这两个区间

所以可以得出递归的结束条件是当区间只有一个值时，就返回

当 begin == end 时，说明此时区间只有一个值

再利用 _MergeSort 函数进行递归两个子序列

然后再归并两个子序列，第一个 while 循环是把序列中小的值尾插到 tmp 中，第二、三个 while 循环是把没有走完的那个序列直接尾插到 tmp 数组后面

最后再将 tmp 数组内的有效数据个数拷贝到 a 数组相对应的位置