归并排序算法的C++实现
2022/1/17 17:07:47
本文主要是介绍归并排序算法的C++实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
归并排序是一种常用的排序算法,其原理是将每一个数看作一个有序序列,然后不断地将两个相邻的有序序列合并成一个有序序列,最后剩下一个有序序列就是排序后的结果。用到的是递归和分治思想。
#include<iostream> #include<malloc.h> using namespace std; void merge(int arr[], int tempArr[], int left, int mid, int right){ int l_pos = left; //左半区第一个未排序的元素位置 int r_pos = mid+1; //右半区第一个未排序的元素位置 int pos = left; //存入临时数组时的元素位置 //进行归并排序的合并操作 while(l_pos<=mid && r_pos<=right){ if(arr[l_pos] < arr[r_pos]){ tempArr[pos++] = arr[l_pos++]; }else{ tempArr[pos++] = arr[r_pos++]; } } //左半区有剩余元素 while(l_pos <= mid){ tempArr[pos++] = arr[l_pos++]; } //右半区有剩余元素 while(r_pos <= right){ tempArr[pos++] = arr[r_pos++]; } //把合并好的临时数组复制回原始数组 pos = left; while(pos <= right){ arr[pos] = tempArr[pos]; pos++; } } void msort(int arr[], int tempArr[], int left, int right){ if(left < right){ // 有两个及以上的元素时进行划分 int mid = (right + left) / 2; // 找到中间的位置 msort(arr, tempArr, left, mid); // 递归划分arr数组的左半部分 msort(arr, tempArr, mid+1, right); // 递归划分arr数组的右半部分 merge(arr, tempArr, left, mid, right); // 合并已经排序的部分 } } // 归并排序入口 void MergeSort(int arr[], int n){ // 进行归并排序的原始数组arr, 数组长度n // 申请相同长度的临时数组空间 int *tempArr = (int*)malloc(n * sizeof(int)); if(tempArr){ cout << "Allocate Memory successfully" << endl; msort(arr, tempArr, 0, n-1); for(int i=0; i<n; i++){ cout << *(tempArr+i) << " "; } free(tempArr); }else{ cout << "error: failed to allocate memory!" << endl; } } int main(){ int arr[9] = {3, 56, 32, 11, 14, 20, 39, 45, 109}; MergeSort(arr, 9); return 0; }
这篇关于归并排序算法的C++实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-07fastcgi 是什么-icode9专业技术文章分享
- 2024-10-07fastcgi 的详细使用教程介绍-icode9专业技术文章分享
- 2024-10-07git如何更新单个文件到本地-icode9专业技术文章分享
- 2024-10-07如何使用ASM(Abstract Syntax Tree Manipulation)技术来修改第三方AAR依赖中的函数-icode9专业技术文章分享
- 2024-10-07Activity 跳转时间耗时很长怎么优化解决-icode9专业技术文章分享
- 2024-10-07Androud Toast 有哪些常用的第三方组件-icode9专业技术文章分享
- 2024-10-07在viewmodel中怎么使用 mmkv?-icode9专业技术文章分享
- 2024-10-07MMKV.defaultMMKV() 是单例模式吗?-icode9专业技术文章分享
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享