C++ 归并排序实现(算法导论)
算法导论上的下标是从1开始的,但是为了和c++ STL的设计思想一致,所有函数的实现统一用左闭右开区间.中间修改了很多次,因为下标修改不是很容易就改掉的,需要始终维持循环不变式,稍微一个步骤出错就会使结果有些错误。
#include <iostream> #include <cstdio> #include <cstdlib> #include <ctime> using namespace std; void merge(int *A, int p, int q, int r) { //merge [p, r),左闭右开区间 int n1 = q - p, n2 = r - q; //注意数量的变化与书上的不同,使用左闭右开区间的优势就是统一数量的形式表示 int *L = new int[n1], *R = new int[n2]; for (int i = 0; i < n1; ++i) //L[0, n1) <== A[p, q) L[i] = A[p+i]; for (int i = 0; i < n2; ++i) //R[0, n2) <== A[q, r) R[i] = A[q+i]; //此处不是q+i+1 int i = 0, j = 0; int k = p; while (i < n1 && j < n2) { if (L[i] <= R[j]) A[k++] = L[i++]; else A[k++] = R[j++]; } while (i < n1) //由于没有了哨兵,需要添加多余元素 A[k++] = L[i++]; while (j < n2) A[k++] = R[j++]; delete [] L; delete [] R; } void merge_sort(int *a, int p, int r) { //调用接口 merge_sort(a, 0, len), 不是(a, 0, len-1)了 if (p < r - 1) { //此时不是p < r了,左闭右开区间当p>=r-1时子数组最多一个元素 int q = p + (r - p)/2; merge_sort(a, p, q); merge_sort(a, q, r); //注意接口统一了,这个不是(a, q+1, r)而是(a, q, r)了,左闭右开的好处 merge(a, p, q, r); } } int main() { srand(time(NULL)); int n; while (cin >> n) { int a[n]; for (int i = 0; i < n; ++i) a[i] = rand() % n; for (int i = 0; i < n; ++i) printf("%d ", a[i]); printf("\n"); merge_sort(a, 0, n); for (int i = 0; i < n; ++i) printf("%d ", a[i]); printf("\n"); } }
最后用了几万组测试数据,得出的结果均与stl里的sort结果一样, 基本说明这个代码是正确的。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。