算法学习笔记（四）：合并排序
浏览数：20 /
时间：2015年06月08日
算法思想：基本的思想为分治算法，也就是将一个问题分成多个更小的部分递归解决。具体到合并排序，就是将待排序序列分为小的序列，递归进行排序，然后合并。
步骤：
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; }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
