Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我去,TLE了一万年,分治排序改成快排就过了

Posted by y454537653 at 2015-02-25 22:09:51 on Problem 3320
按说分治和快排都是O(nlogn)的复杂度,怎么一个就TLE一个是400ms,难道是我写的太烂了...求解,附代码
//分治排序
void merge(int A[], int p, int q, int r)
{
    int *L = (int*)malloc((q - p + 1) * sizeof(int));
    int *R = (int*)malloc((r - q) * sizeof(int));
    int i, j, k;
    for (i = 0; i < q - p + 1; i++) {
        L[i] = A[p + i];
    }
    for (i = 0; i < r - q; i++) {
        R[i] = A[q + i + 1];
    }
    i = j = 0;
    k = p;
    while (i < q - p + 1 && j < r - q) {
        if (L[i] < R[j]) {
            A[k++] = L[i++];
        }
        else {
            A[k++] = R[j++];
        }
    }
    while (i < q - p + 1) {
        A[k++] = L[i++];
    }
    while (j < r - q) {
        A[k++] = R[j++];
    }
    free(L);
    free(R);
    return;
}

void merge_sort(int A[], int p, int r)
{
    int q = (p + r) / 2;
    if (p < r) {
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
    return;
}

//快排
void quick_sort(int A[], int p, int r)
{
    int i, t, x = A[r], k = p;
    if (p >= r) {
        return;
    }
    for (i = p; i < r; i++) {
        if (A[i] < x) {
            t = A[k];
            A[k++] = A[i];
            A[i] = t;
        }
    }
    A[r] = A[k];
    A[k] = x;
    quick_sort(A, p, k - 1);
    quick_sort(A, k + 1, r);
    return;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator