(声明:文章全部图片均来自 传智播客 教师课件)归并排序是一种空间换时间的做法,排序的速度当然会提高很多,归并排序中会产生一个临时数组,这个临时数组用来把不断拆分到最后的有序数据进行合并,最后再把合并后的数据重新赋值给原数组,这样就实现了排序。主要分为以下三个步骤:
1、把原数组无限拆分到最少元素(直至剩余一个)如下图表示:
2、把拆分的两组数据合并到临时数组,如下图表示:
3、最后把临时数组中的值覆盖掉原始数组的值,整个过程就是下图这样的:
【实现代码】
#include <stdio.h> void mergeArray(int arr[], int first, int mid, int last, int temp[]) { // 两个有序序列合并后的长度 int length = 0; // 记录拆分后左侧起始下标 int i = first; // 记录拆分后右侧起始下标 int j = mid + 1; // 判断两个有序序列的下标是否到最后一个元素了 while (i <= mid && j <= last) { // 判断值哪个值小 if (arr[i] <= arr[j]) { // 把小的值放到 temp 临时数组中 temp[length] = arr[i]; // 把小的数组的值下标向后移动 i++; } else { // 同上 temp[length] = arr[j]; j++; } // 每放进去一个值,记录temp数组长度的下标值就要+1 length++; } // 当上面循环结束时,一定还有一个数组没有遍历完,一个已经全部遍历完了 // 我们要把那个没有遍历完的数据剩下的元素放到临时数组中 while (i <= mid) { // 如果i的下标还没到最最后的位置,那么就循环把值赋给临时数组 temp[length] = arr[i]; length++; i++; } while (j <= mid) { // 如果j的下标还没到最最后的位置,那么就循环把值赋给临时数组 temp[length] = arr[j]; length++; j++; } for (i = 0; i < length; i++) { // 有可能是从数组的中间位置开始拷贝的,这取决于传递进函数的参数 arr[first + i] = temp[i]; } } void mergeSort(int arr[], int first, int last, int temp[]) { if (first < last) { // 将数据分割成两份 int mid = (first + last) / 2; // 一次递归把两份左侧的数据和右侧的数据再次拆分 mergeSort(arr, first, mid, temp); mergeSort(arr, mid + 1, last, temp); // 把拆分的数据进行排序(递归中,是从拆分到最后的2个或3个数进行排序) mergeArray(arr, first, mid, last, temp); } } int main(int argc, char* argv[]) { int arr[11] = { 1, 21, 91, 284, 74, 57, 10, 38, 292, 28, 71 }; int temp[11]; mergeSort(arr, 0, 11 - 1, temp); for (int i = 0; i < 11 - 1; i++) { printf("%d ", arr[i]); } return 0; }