首页 > 代码库 > 算法之合并排序(mergeSort)
算法之合并排序(mergeSort)
合并排序算法在结构上是递归的，采用分治策略：就是将原有的问题划分为 n 个规模较小但结构与原问题相似的子问题，递归地解决这些子问题，然后合并其结果，就得到原问题的解。
合并排序的模式一般如下：
1.分解：将 n 个元素分解为各含 n/2 个元素的两个序列；
2.解决：用分治排序法对两个子序列递归地排序；
3.合并：合并两个已排好序的子序列得到排序结果。
在对子序列递归的过程中，当子序列元素数为1时，递归结束。
合并排序算法的时间复杂度为O(nlgn)
1 void merge(int* a, int p, int q, int r) 2 { 3 int i = 0; 4 int j = 0; 5 int k = 0; 6 int n1 = q - p + 1; 7 int n2 = r - q; 8 int* L = (int*)malloc((n1 + 1) * sizeof(int)); 9 int* R = (int*)malloc((n2 + 1) * sizeof(int));10 for(i = 0; i < n1; i++)11 {12 *(L + i) = a[p + i];13 }14 *(L + n1) = INT_MAX; //插入序列末标志15 16 for(i = 0; i < n2; i++)17 {18 *(R + i) = a[q + i + 1];19 }20 *(R + n2) = INT_MAX; //插入序列末标志21 22 i = 0;23 j = 0;24 k = 0;25 for(k = p; k < r + 1 ;k++)26 {27 if(*(L + i) > *(R + j))28 {29 *(a + k) = *(R + j);30 j++;31 }32 else33 {34 *(a + k) = *(L + i);35 i++;36 }37 } 38 }39 40 void mergeSort(int* a, int p, int r)41 {42 int q = 0;43 if(p < r)44 {45 q = (r + p) / 2;46 mergeSort(a, p, q);47 mergeSort(a, q + 1, r);48 merge(a, p, q, r);49 }50 }
注：1. mergeSort(int* a, int p, int r) 和 merge(int* a, int p, int q, int r)中的形参 p, q, r 都是序列 a 的索引，其中子序列 L = (a[p] ~ a[q])，其长度为 q - p + 1；子序列 R = (a[q + 1] ~ a[r])，其长度为 r - (q + 1) - 1 即 r - q；
2.在上述代码中都插入了 序列标志数，这个数默认为∞，但在实际应用中，该数有可能会出现在应用序列中，merge函数可改为如下：
1 void merge(int* array, int p, int q, int r) 2 { 3 int i = 0; 4 int j = 0; 5 int k = 0; 6 int n1 = q - p + 1; 7 int n2 = r - q; 8 int* L = (int*)malloc((n1) * sizeof(int)); 9 int* R = (int*)malloc((n2) * sizeof(int));10 for(i = 0; i < n1; i++)11 {12 *(L + i) = array[p + i];13 }14 //*(L + n1) = INT_MAX;15 16 for(j = 0; j < n2; j++)17 {18 *(R + j) = array[q + j + 1];19 }20 //*(R + n2) = INT_MAX;21 22 i = 0;23 j = 0;24 k = 0;25 for(k = p; k < r + 1 ;k++)26 {27 if(i > (n1 - 1))28 {29 *(array + k) = *(R + j);30 j++;31 }32 else if(j > (n2 - 1))33 {34 *(array + k) = *(L + i);35 i++;36 }37 else38 {39 if(*(L + i) > *(R + j))40 {41 *(array + k) = *(R + j);42 j++;43 }44 else45 {46 *(array + k) = *(L + i);47 i++;48 }49 }50 } 51 }
算法之合并排序(mergeSort)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。