数据结构与算法：归并排序

归并排序的基本思想

归并排序的特性总结

代码

归并排序的非递归版

归并排序的基本思想

归并排序是建立在归并操作上的一种有效的排序算法。改算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，在使子序列段间有序。若将两个有序表合并症一个有序表，称为二路归并。

归并排序的基本思想是将两个或两个以上的有序有序表合并成一个新的有序表。这个思想可以递归地应用于子序列的排序，最终使得整个序列有序。

具体来说，归并排序可以分为两个主要步骤：分解和合并。

分解步骤是将待排序的序列不断分解成两个子序列，直到子序列的长度为1。这个过程可以通过递归实现，每次递归都将当前序列的中间点作为分割点，将序列分成左右两个子序列。由于子序列的长度为1，因此它们本身就被视为有序序列。

合并步骤是将两个有序子序列合并成一个新的有序序列。这个过程可以通过迭代实现，每次迭代都去两个子序列中的第一个元素，比较它们的大小，将小的元素添加到新序列中，并将其从原序列中移除。这个过程一直持续到一个子序列为空，然后将另一个子序列中剩余的元素全部添加到新的序列中。

归并排序的特性总结

时间复杂度： $O(N*logN)$
空间复杂度： $O(N)$
稳定性：稳定

归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序过程中不会改变。

归并排序的时间复杂度为O(nlogn)，其中n是待排序数据的数量。这意味着无论数据是已经部分排序还是完全无序，归并排序都能保持较高的效率。

归并排序的空间复杂度为O(n)，因为它需要额外的空间来合并两个已排序的子数组。这意味着在内存有限的情况下，使用归并排序可能需要额外的考虑。然而，在大多数情况下，这种空间消耗是可以接受的，因为归并排序的高效性和稳定性往往能够抵消其空间复杂度的不足。

代码

void MergeSort(int* a, int n)
{//有几个数 开多少空间int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(1);}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;//分组_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//合并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){//小的进tmpif (a[begin1] < a[begin2])tmp[i++] = a[begin1++];elsetmp[i++] = a[begin2++];}//出循环后，如果右边的已经进tmp了while (begin1 <= end1)tmp[i++] = a[begin1++];//左边的已经全进,将右边全进入while (begin2 <= end2)tmp[i++] = a[begin2++];//将tmp拷贝给amemcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

_MergeSort 函数是核心函数，用于实现归并排序的递归过程。首先判断递归结束的条件，即如果 begin 和 end 相等，则只有一个元素，不需要排序。然后找到中间位置 mid ，将原数组分成两个子数组并分别调用 _MergeSort 函数进行排序。

接下来是合并过程，使用四个 begin1、begin2、end1和end2 分别指向两个子数组的起始和结束位置。然后使用一个 i 遍历临时数组 tmp 。比较两个子数组的元素大小，将较小的元素放入 tmp 数组中，并将对应的下标向后移动。直到有一个子数组遍历完毕，将另一个子数组中的剩余元素依次放入 tmp 数组。

最后，使用 memcoy 函数将临时数组 tmp 中的元素拷贝回原数组 a 中，完成排序。

归并排序的非递归版

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 i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;//begin2 大于等于n 发生越界，不需要归并if (begin2 >= n)break;//begin2没有越界 但是end2越界 则代表数据超过if (end2 >= n)end2 = n - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[j++] = a[begin1++];elsetmp[j++] = a[begin2++];}while (begin1 <= end1)tmp[j++] = a[begin1++];while (begin2 <= end2)tmp[j++] = a[begin2++];memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);tmp = NULL;
}

i 代表每组归并的起始位置

在代码中，首先创建一个临时数组 tmp，用来在合并过程中暂存排序后的结果。然后定义一个变量gap作为当前的步长，初始时为1.通过一个循环，每次将gap乘以2，知道gap大于等于n。在循环中，通过两个内嵌的循环，将数组分成若干个子数组，并进行两两合并。

内层循环中，先计算出两个待合并的子数组的起始和结束位置，然后对这两个子数组进行合并操作。合并过程中，比较两个子数组中的元素，将较小的元素放入临时数组 tmp 中，并移动对应子数的下标。最后将tmp中的结果拷贝回原始数组a中。