Dorado's host
首页
日常
追番
随笔
工作
技术杂项
开源项目
学习
java基础
mit 6.S081
算法
写题目
学知识
友链
留言
关于我
登录
首页
日常
追番
随笔
工作
技术杂项
开源项目
学习
java基础
mit 6.S081
算法
写题目
学知识
首页
›
学知识
›
归并排序
归并排序
2022-02-07 14:00
861
0
## 思想 归并排序本质上也是一个分治算法,其大致步骤如下: 1. 确定分界点,`mid = (l + r) / 2` 2. 递归排序左边和右边的序列 3. 默认左右两边都是有序的,**归并左右序列合二为一** ## 归并 ``` TEST DATA 5 3 4 2 1 5 ``` ### 双指针法 我们用两个指针,分别指向两个有序队列的首部,同时新开数组`temp[r - l]` 来已经存好的数据 ``` Arr : [3, 4, 2, 1, 5] mid : 2 leftArr : [3, 4] p rightArr : [1, 5] p tempArr : [] ``` 接下来比较两个指针指向的数,取出小的数存在`tempArr`中,同时将存在小的数的数组指针向前移动一位 ``` leftArr : [3, 4] p rightArr : [1, 5] p tempArr : [1] ``` 然后循环重复上一个过程,直到其中指针指到数组的长度+1的位置,循环结束 ``` leftArr : [3, 4] P rightArr : [1, 5] p tempArr : [1, 3, 4] ``` 之后判断未空的数组,将未遍历完的数组按照顺序插入到`tempArr`中 ``` leftArr : [3, 4] P rightArr : [1, 5] p tempArr : [1, 3, 4, 5] ``` ## 实例代码 ``` #include
using namespace std; const int N = 1e6 + 10; int q[N]; int temp[N]; void mergeSort(int nums[], int l, int r) { if(l >= r) return; int mid = (l + r) / 2; mergeSort(nums, l, mid); mergeSort(nums, mid + 1, r); int lIndex = l, rIndex = mid + 1, index = l; while (true) { if(lIndex > mid || rIndex > r) break; if(nums[lIndex] > nums[rIndex]) { temp[index++] = nums[rIndex++]; }else { temp[index++] = nums[lIndex++]; } } while(lIndex <= mid) { temp[index++] = nums[lIndex++]; } while(rIndex <= r) { temp[index++] = nums[rIndex++]; } for(int i = l; i <= r; i++) { nums[i] = temp[i]; } } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } mergeSort(q, 0, n - 1); for(int i = 0; i < n; i++) { printf("%d ", q[i]); } } ``` ## 例题 ``` https://www.acwing.com/problem/content/789/ ```
相关文章
评论
(暂无评论)
取消回复
发表评论
dorado
一个平平无奇的打工人
17
文章
1
评论
12
栏目
热门文章
寻找两个正序数组的中位数
0 评论
ubutnu下的git常用命令
0 评论
IDEA快捷键一览(转)
0 评论
每日一报自动点击脚本
0 评论
端口查询
0 评论
更多