分治归并排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了分治归并排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1613字，纯文字阅读大概需要3分钟。
内容图文
1
void Solution::devideConquerSort(vector<int>& vec)
2{
3int left = 0;
4int right = vec.size() - 1;
5 mergeSort(vec, left, right);
6}
7 8void Solution::mergeSort(vector<int>& vec, int left, int right)
9{
10if(left < right)
11 {
12int mid = (left+right) / 2;
13 mergeSort(vec, left, mid);
14 mergeSort(vec, mid+1, right);
15 merge(vec, left, mid, right);
16 }
17}
1819void Solution::merge(vector<int>& vec, int left, int mid, int right)
20{
21int leftnums = mid - left + 1;
22int rightnums = right - mid;
2324int leftarr[leftnums+1], rightarr[rightnums+1];
25int j = left;
26int i = 0;
27for(i = 0; i < leftnums; i++)
28 {
29 leftarr[i] = vec[j];
30 j++;
31 }
32 leftarr[i] = INT_MAX; // 足够大的数作为哨兵3334 j = mid + 1;
35for(i = 0; i < rightnums; i++)
36 {
37 rightarr[i] = vec[j];
38 j++;
39 }
40 rightarr[i] = INT_MAX;
4142 i = 0;
43 j = 0;
44for(int k = left; k < right + 1; k++)
45 {
46if(leftarr[i] <= rightarr[j])
47 {
48if(leftarr[i] == INT_MAX)
49 {
50// 如果此时leftarr[i]为INT_MAX
51// 说明此时rightarr的元素也全为INT_MAX
52// 为了防止下标i溢出53for(k; k < right + 1; k++)
54 {
55 vec[k] = INT_MAX;
56 }
57break;
58 }
59 vec[k] = leftarr[i];
60 i++;
61 } else62 {
63 vec[k] = rightarr[j];
64 j++;
65 }
66 }
67 }
分治模式在每层递归时都有三个步骤：
一：分解原问题为若干子问题，这些子问题都是原问题的规模较小的实例
二：解决这些子问题，递归地求解各个子问题。
三：合并这些子问题的解，使成为原问题的解
比如上述算法，将对一个数组排序的问题不断切分为更小的排序问题，直到最后(left<right)，此时所有实例都是有序的，因为只有一个元素,如果有不理解的地方画一画图就很清晰了
归并排序：
一：分解-待排序的n个元素的序列各具n/2个元素的两个子序列
二：解决-使用归并排序递归地排序两个子序列
三：合并-合并两个已排序的子序列以产生已排序的答案
因为就我而言，我已经大致理解了，所以没有过多解释说明备注，如果有需要的话，请留言。
原文：https://www.cnblogs.com/cccv/p/algorithm_002.html
内容总结
以上是互联网集市为您收集整理的分治归并排序全部内容，希望文章能够帮你解决分治归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。