【算法】归并排序
2022/2/28 17:23:36
本文主要是介绍【算法】归并排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<bits/stdc++.h> using namespace std; //归并过程 void merge(int arr[], int l, int mid, int r){ int help[r-l+1];//辅助数组 int i = 0; int lIndex = l; int rIndex = mid+1; while(lIndex <= mid && rIndex <= r){ help[i++] = arr[lIndex] < arr[rIndex] ? arr[lIndex++]:arr[rIndex++]; } //左边和右边肯定有一边到头了,不可能同时,因为每次只移动一边 while(lIndex <= mid){ help[i++] = arr[lIndex++]; } while(rIndex <= r){ help[i++] = arr[rIndex++]; } //将排好序的辅助数组赋值给原始数组,不需要返回值 for(i = 0; i < r-l+1; i++){ arr[l+i] = help[i]; } } //递归 static void mergeSort(int arr[], int l, int r){ if(l == r){ return; } int mid = (l + r) / 2; //左半部分归并排序 mergeSort(arr, l, mid); //右半部分归并排序 mergeSort(arr, mid+1, r); //左右部分归并 merge(arr, l, mid, r); } //归并排序整个数组 void mergeSort(int arr[], int n){ //如果数组为空或只有一个元素,不需要排序 if(arr == NULL || n < 2){ return; } mergeSort(arr,0,n-1); } int main(){ int n; while(cin >> n){ int arr[n]; for(int i = 0; i < n; i++) cin >> arr[i]; mergeSort(arr, n); for(int i = 0; i < n; i++){ cout << arr[i] << " "; } cout << endl; } return 0; }
这篇关于【算法】归并排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding