归并排序（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; }

运行结果：