首页 > 代码库 > 算法学习笔记（四）：合并排序
算法学习笔记（四）：合并排序
算法思想：基本的思想为分治算法，也就是将一个问题分成多个更小的部分递归解决。具体到合并排序，就是将待排序序列分为小的序列，递归进行排序，然后合并。
步骤：
1、分解：将n个元素分成各含n/2个元素的子序列
2、解决：用合并排序对两个子序列递归排序
3、合并：合并两个已排序的子序列以得到排序结果
在对子序列排序时，其长度为1时递归结束。
算法复杂度：O(nlgn)
代码实现：
void divide_sort(int arr[],int p,int r){ if(p<r) { int q = (r + p) / 2; divide_sort(arr, p, q); divide_sort(arr, q + 1, r); merge_sort(arr, p, q, r); }}void merge_sort(int arr[],int p,int q,int r){ int n1 = q - p + 1; int n2 = r - q; int *L = new int[n1]; int *R = new int[n2]; memcpy(L, arr+p, n1*sizeof(int)); memcpy(R, arr+q + 1 , n2*sizeof(int)); int i, j; i = j = 0; int k = p; while (i!=n1&&j!=n2) { if(L[i]<=R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } while(i!=n1) { arr[k++] = L[i++]; } while(j!=n2) { arr[k++] = R[j++]; } delete[] L; delete[] R;}
算法学习笔记（四）：合并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。