归并排序（C# C++）

1 归并排序的基本概念

2 算法步骤

2-1 分解阶段

2-2 合并阶段

3 代码实现

3-1 C#代码示例（该代码在unity环境下）

3-2 C++代码示例

1 归并排序的基本概念

归并排序（Merge Sort）是一种经典的分治算法，由约翰・冯・诺伊曼在 1945 年提出。它的核心思想是将一个大问题分解为多个相似的小问题，然后分别解决这些小问题，最后将小问题的解合并起来得到原问题的解。

2 算法步骤

归并排序主要分为两个阶段：分解阶段和合并阶段。

2-1 分解阶段

分解过程：从数组的中间位置将数组分成两个子数组，不断递归地对这两个子数组进行同样的分解操作，直到每个子数组中只有一个元素（因为单个元素的数组本身就是有序的）。
示例：假设有数组 [8, 4, 5, 7, 1, 3, 6, 2]，首先将其从中间分成 [8, 4, 5, 7] 和 [1, 3, 6, 2]，然后对这两个子数组继续分解，如 [8, 4, 5, 7] 会被分解为 [8, 4] 和 [5, 7]，依此类推，直到每个子数组只有一个元素。

2-2 合并阶段

合并过程：将两个有序的子数组合并成一个有序的数组。比较两个子数组的第一个元素，将较小的元素放入新数组，然后移动该子数组的指针，继续比较，直到其中一个子数组的元素全部放入新数组，最后将另一个子数组剩余的元素依次放入新数组。
示例：假设有两个有序子数组 [4, 8] 和 [5, 7]，比较 4 和 5，将 4 放入新数组，然后比较 8 和 5，将 5 放入新数组，接着比较 8 和 7，将 7 放入新数组，最后将 8 放入新数组，得到合并后的有序数组 [4, 5, 7, 8]。

3 代码实现

3-1 C#代码示例（该代码在unity环境下）

        private int GetAndIncrement(int[] arr, ref int index){int value = arr[index];index++;return value;}private int[] Sort(int[] left, int[] right){//先准备一个新数组var array = new int[left.Length + right.Length];var leftIndex = 0;var rightIndex = 0;for (var i = 0; i < array.Length; i++){//左侧放完了，直接放对面if (leftIndex >= left.Length)array[i] = GetAndIncrement(right, ref rightIndex);else if (rightIndex >= right.Length) array[i] = GetAndIncrement(left, ref leftIndex);else if (left[leftIndex] < right[rightIndex])array[i] = GetAndIncrement(left, ref leftIndex);else array[i] = GetAndIncrement(right, ref rightIndex);}return array;}private int[] Merge(int[] array){if (array.Length < 2) return array;int mid = array.Length / 2;int[] left = new int[mid];int[] right = new int[array.Length - mid];for (int i = 0; i < array.Length; i++){if (i < mid) left[i] = array[i];else right[i - mid] = array[i];}return Sort(Merge(left), Merge(right));}

测试程序

3-2 C++代码示例

#include <iostream>
#include <vector>int GetAndIncrement(const std::vector<int>& arr, int& index) {int value = arr[index];index++;return value;
}std::vector<int> Sort(const std::vector<int>& left, const std::vector<int>& right) {std::vector<int> array(left.size() + right.size());int leftIndex = 0;int rightIndex = 0;for (size_t i = 0; i < array.size(); ++i) {if (leftIndex >= left.size()) {array[i] = GetAndIncrement(right, rightIndex);} else if (rightIndex >= right.size()) {array[i] = GetAndIncrement(left, leftIndex);} else if (left[leftIndex] < right[rightIndex]) {array[i] = GetAndIncrement(left, leftIndex);} else {array[i] = GetAndIncrement(right, rightIndex);}}return array;
}std::vector<int> Merge(const std::vector<int>& array) {if (array.size() < 2) {return array;}size_t mid = array.size() / 2;std::vector<int> left(array.begin(), array.begin() + mid);std::vector<int> right(array.begin() + mid, array.end());return Sort(Merge(left), Merge(right));
}int main() {std::vector<int> array = {12, 34, 54, 2, 3};std::cout << "排序前的数组: ";for (int num : array) {std::cout << num << " ";}std::cout << std::endl;std::vector<int> sortedArray = Merge(array);std::cout << "排序后的数组: ";for (int num : sortedArray) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

运行结果：