最近心血来潮，又想看一些常用算法的知识点，反正之前也写过一篇简单的算法整理，算是开了个头，但是就没有后续了，今天就来整一个归并排序吧，随心而更。。。
归并排序算法遵循分治法的思想，就是首先将一个问题进行分解，然后逐个对这些子问题进行递归排序，最后合并结果，每当排序的序列长度为1时，递归开始回落，此时长度为1的这些序列都是排好序的，然后我们进行比较合并就行。
下面我写了一个简单的C++的实现例子，这只是一个测试用例，代码的安全性肯定是不够高，目的只是用来说明一下归并排序的思路，对于初学者简单的理解还是没问题的。
#include"MergeSort.h" void merge(int* OriginalArray, int start_index, int temp_index, int final_index) { int left = temp_index - start_index + 1;//左边分支的数据个数 int right = final_index - temp_index;//右边分支的数据个数 int* left_array = nullptr; left_array = new int[left + 1];//此处应该用异常处理判断是否申请内存成功 int* right_array = nullptr; right_array = new int[right + 1];//此处应该用异常处理判断是否申请内存成功 int i = 0; for (; i < left; ++i) { left_array[i] = OriginalArray[start_index + i]; } int j = 0; for (; j < right; ++j) { right_array[j] = OriginalArray[temp_index + j + 1]; } //max 用来控制比较，作用相当于一个标志，意味着某一个分支已经比较到最后一个元素 left_array[left] = INT_MAX; right_array[right] = INT_MAX; i = 0; j = 0; for (int k = start_index; k <= final_index; ++k) { //此处会发生合并，分别进行比较，总共比较k次，复杂度O(k) if (left_array[i] <= right_array[j]) { OriginalArray[k] = left_array[i]; i = i + 1; } else { OriginalArray[k] = right_array[j]; j = j + 1; } } } void mergesort(int* OriginalArray,int start_index,int final_index) { if (start_index < final_index) { int temp = (start_index + final_index)/2; //开始递归 mergesort(OriginalArray, start_index, temp); //关于传参temp + 1 如果start和final之间的差为1，则直接对两个数进行排序 mergesort(OriginalArray, temp + 1, final_index); merge(OriginalArray, start_index, temp, final_index); } } int main() { int OriginalNumber[] = { 4,1,5,2,7,3,8,6,0,9 }; mergesort(OriginalNumber, 0, 9); for (auto i : OriginalNumber) { cout << i << endl; } return 0; }
“流水不争先，争的是滔滔不绝”—《一点就到家》电影台词
参考书籍：算法导论(第三版)
