归并排序-模板
作者:
dreambear
,
2022-07-04 13:13:56
,
所有人可见
,
阅读 185
void merge(int lo, int mi, int hi)
{
int* A = a + lo;
int lb = mi - lo; int *B = new int[lb];
for (int i = 0; i < lb; i++) B[i] = A[i];
int lc = hi - mi; int *C = a + mi;
for (int i = 0, j = 0, k = 0; j < lb;)
{
if ((k < lc) && (C[k] < B[j])) A[i ++ ] = C[k ++ ];
if ((lc <= k) || (B[j] <= C[k])) A[i ++ ] = B[j ++ ];
}
delete []B;
}
void mergesort(int lo, int hi) // [lo, hi)
{
if (hi - lo < 2) return ;
int mi = (lo + hi) >> 1;
mergesort(lo, mi);
mergesort(mi, hi);
merge(lo, mi, hi);
}