C++算法恢复训练之归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序数组分成两个子数组，然后对这两个子数组分别进行排序，最后将两个已排序的子数组合并成一个有序数组。归并排序是一种稳定的排序算法，具体体现在其时间复杂度上。

下面是使用 C++ 实现的归并排序算法：

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>using namespace std;void mergeSortImplementation(vector<int>& array, int left, int right)
{if (left == right){return;}const int mid = left + ((right - left) >> 1);mergeSortImplementation(array, left, mid);mergeSortImplementation(array, mid + 1, right);vector<int> temp(right - left + 1);int p1 = left;int p2 = mid + 1;for (unsigned int i = 0; i < temp.size(); ++i){if (p1 == mid + 1){temp[i] = array[p2++];continue;}if (p2 == right + 1){temp[i] = array[p1++];continue;}if (array[p1] < array[p2]){temp[i] = array[p1++];}else{temp[i] = array[p2++];}}for (unsigned int i = left; i < right + 1; ++i){array[i] = temp[i - left];}
}void mergeSort(vector<int>& array)
{if (array.size() < 2){return;}mergeSortImplementation(array, 0, array.size() - 1);
}int main(int argc, char* argv[])
{// Create an array to test sort methodvector<int> array = {2, 3, 4, 0, 7};cout << "Before sorting: ";for (int i = 0; i < array.size(); ++i){cout << array[i] << " ";}cout << endl;mergeSort(array);cout << "After sorting: ";for (int i = 0; i < array.size(); ++i){cout << array[i] << " ";}cout << endl;return 0;
}

归并排序的实现过程可以分为两个步骤：

• 分割子问题：将待排序数组分成两个子数组，分别对两个子数组进行排序。
• 合并解决方案：将两个已排序的子数组合并成一个有序数组。

具体来说，归并排序的分割子问题的实现可以使用递归算法，每次将待排序数组分成两个子数组，然后对两个子数组分别进行排序；合并解决方案的实现则需要额外的存储空间，将两个已排序的子数组合并成一个有序数组。

归并排序的时间复杂度为 $O(nlogn)$，其中 n 是待排序数组的长度。归并排序每次将待排序数组分成两个子数组，分别对两个子数组进行排序，然后再将两个已排序的子数组合并成一个有序数组。这个过程的时间复杂度可以表示为：

$T(n)=2T(n/2)+O(n)$

其中 T(n) 表示对长度为 n 的数组进行归并排序的时间复杂度。通过递归展开可以得到：

$$\begin{gathered} T(n)=2T(n/2)+O(n) \\ =2[2T(n/4)+O(n/2)]+O(n) \\ =4T(n/4)+2O(n) \\ =4[2T(n/8)+O(n/4)]+2O(n) \\ =8T(n/8)+3O(n) \\ =... \\ =nT(1)+lognO(n) \end{gathered}$$

故而其最终算法时间复杂度为$O(nlogn)$。