首页 > 代码库 > 归并排序
归并排序
归并排序重点在治,即合并两个有序数组:
1 void merge(int A[], int p, int q, int r) 2 { 3 int i = 0, j = 0, k = p; 4 int m = q - p + 1; 5 int n = r - q; 6 int *S = new int[m]; 7 int *T = new int[n]; 8 for (i = 0; i < m; i++) 9 S[i] = A[p + i]; 10 for (j = 0; j < n; j++)11 T[j] = A[q + j + 1]; 12 13 i = j = 0;14 while ((i < m) && (j < n)) 15 if (S[i] < T[j])16 A[k++] = S[i++];17 else18 A[k++] = T[j++];19 while (i < m)20 A[k++] = S[i++];21 while (j < n)22 A[k++] = T[j++];23 24 delete[] S;25 delete[] T;26 }
有了合并以后,merge sort就很简单了。
void merge_sort(int A[], int p, int r){ int q; if (p < r) { q = (p + r) / 2; merge_sort(A, p, q); merge_sort(A, q + 1, r); merge(A, p, q, r); }}
归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。