提交记录 18673


用户 题目 状态 得分 用时 内存 语言 代码长度
Steven_Zheng 1001. 测测你的排序 Time Limit Exceeded 0 5 s 390636 KB C 1.18 KB
提交时间 评测时间
2022-11-20 17:44:59 2022-11-20 17:45:08

void quick_sort(unsigned int a[], int first, int last)
{
    int i, j;
    unsigned int t;
    if(last - first <= 40)
    {
        for(i = first + 1; i <= last; i++)
        {
            t = a[i];
            for(j = i - 1; j >= first && t < a[j]; j--)
                a[j + 1] = a[j];
            a[j + 1] = t;
        }
        return;
    }

    t = a[first];  //第一个元素与中间元素交换
    a[first] = a[first + last >> 1];
    a[first + last >> 1] = t;
    unsigned int stdd = a[first];
    i = first + 1;
    j = last;

    for(;;)
    {
        while(i <= last && a[i] < stdd)
            i++;
        while(j > first && a[j] > stdd)
            j--;
        if(i > j)
            break;
#if 1  //测试证明,这种写法比另一种效率高
        t = a[i];
        a[i++] = a[j];
        a[j--] = t;
#elif 1
        t = a[i];
        a[i] = a[j];
        a[j] = t;
        i++;
        j--;
#endif

    }  //把数组分成>=stdd和<=stdd两部分。即便两个元素相等,也要进行交换。
    /**
    * 把a[i] < stdd、a[j] > stdd改成a[i] <= stdd、a[j] >= stdd虽然正确,
    * 但是当元素全都相同时,会引起两边的元素数量极其不平衡,使得递归深度增加、耗时增加。
    */
    a[first] = a[j];
    a[j] = stdd;

    quick_sort(a, first, j - 1);
    quick_sort(a, j + 1, last);
}

void sort(unsigned *a, int n) {
	quick_sort(a, 0, n);
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #15 s381 MB + 492 KBTime Limit ExceededScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2022-12-04 02:58:24 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用