目录

归并排序原理复杂度分析归并排序代码1.递归版本代码2.非递归版本代码 测试及结果测试结果

归并排序原理

归并排序(Merge Sort)是指将两个(或两个以上)有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列，如果合并的表的个数是二，那么就是二路归并排序，下面讲的都是二路归并排序。 归并排序主要思想是分治，先将要排序的元素分成两个子集，先将这两个子集排列成有序，然后将这两个有序的序列归并为一个有序的序列。 由此可知，归并排序的主要步骤是： 1.分解原始序列：将原始的序列分成两个序列，即求合适的分裂点。 2.求解子序列：对两个子序列递归的进行归并排序，递归结束的条件是子序列的个数是一。 3.合并子序列：将排好序的序列进行合并，将两个有序序列合并成一个有序序列。

复杂度分析

最优时间复杂度、最坏时间复杂度与平均时间复杂度都是O(nlogn)空间复杂度O(n)归并排序是一种稳定的排序方法

归并排序代码

由上面的分析不难写出代码。

1.递归版本代码

void MySort::MergeSort(std::vector<int>& nums)//归并排序 { int first = 0, last = nums.size() - 1; MSort(nums, first, last); } void MSort(std::vector<int>& nums, int first, int last) { if (first < last)//递归结束条件，当序列中只有一个点时不再递归 { int mid = first + (last - first) / 2; MSort(nums, first, mid);//左边有序 MSort(nums, mid + 1, last);//右边有序 merge(nums, first, mid, last);//将两个有序序列进行融合 } }

上面的代码最难理解的部分就是用于合并两个有序序列的merge函数。

void merge(std::vector<int>& nums, int first, int mid, int last) { std::vector<int> tmp(last - first + 1, 0); int left = first; int right = mid + 1; int k = 0; while (left <= mid && right <= last) { if (nums[left] < nums[right]) tmp[k++] = nums[left++]; else tmp[k++] = nums[right++]; } while (left <= mid) { tmp[k++] = nums[left++]; } while (right <= last) { tmp[k++] = nums[right++]; } for (int i = 0; i < k; i++) { nums[first + i] = tmp[i]; } }

可以看出合并有序数列的效率是比较高的，可以达到O(n)。

2.非递归版本代码

void MySort::MergeSortNotR(std::vector<int>& nums)//归并排序递归 { int size = nums.size(); MSortNotR(nums, size); } void MSortNotR(std::vector<int>& nums, int n)//参数和递归略不同，n代表数组中元素个数，即数组最大下标是n-1 {//非递归实现 int size = 1, low, mid, high; while (size <= n - 1) { low = 0; while (low + size <= n - 1) { mid = low + size - 1; high = mid + size; if (high > n - 1)//第二个序列个数不足size high = n - 1; merge(nums, low, mid, high);//调用归并子函数 low = high + 1;//下一次归并时序列的下界 } size *= 2;//范围扩大一倍 } }

merge函数和之前递归版本的代码是一样的。

测试及结果

测试

int main() { srand((int)time(NULL));//随机种子 vector<int> nums,nums1,nums2; print_data printTest; MySort sortTest; for (int i = 0; i < 9; i++) { nums.push_back(rand() % 100);//生成0-99之间的随机数 } nums1 = nums; nums2 = nums; vector<int> numsk = nums; vector<int> numskNotR = nums; vector<int> numsM = nums; vector<int> numsMNotR = nums; cout << "归并排序递归：" << endl; //归并排序 printTest.printVector(numsM); sortTest.MergeSort(numsM); printTest.printVector(numsM); cout << "归并排序非递归：" << endl; //归并排序 printTest.printVector(numsMNotR); sortTest.MergeSortNotR(numsMNotR); printTest.printVector(numsMNotR); system("pause"); return 0; }

结果