3607. 选择排序(构造)

单测试点时限: 60.0 秒

内存限制: 1024 MB

一般来说,选择排序是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

那么核心代码就应该是类似于:

for (int i = 0; i < a.length - 1; i++) {
            minIndex = i; // 无序区的最小数据数组下标
            for (int j = i + 1; j < a.length; j++)
                // 在无序区中找到最小数据并保存其数组下标
                if (a[j] < a[minIndex])
                    minIndex = j;
            int t = a[i];
            a[i] = a[minIndex];
            a[minIndex] = t;
        }

然而,jxtxzzw喜欢把选择排序写成:

for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j)
            if (a[i] > a[j]) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
            }

很显然,这样的写法也是正确的。

但是,jxtxzzw的这种写法,虽然写起来方便,但是效率会比较低。

请你自行分析效率低的原因,并验证。

输出

没有输入。

你需要构造一组测试数据,来证明jxtxzzw的选择排序效率比较差。

你需要输出 行。

行是一个正整数 ,表示待排序的数字个数。

必须是正整数,且必须是 范围。

行是 个整数,表示 个待排序的数字。

可以是正整数、负整数或 ,但必须在 int 范围,数字与数字之间用空格分隔。

你构造的数据需要保证:

  • 能够使一般的选择排序在 秒内得到正确的结果;

  • 但是jxtxzzw的选择排序需要大于 秒的时间才能得到正确的结果。

例如,一种合法的输出是:

10
1 2 3 -1 3 2 1 -1 -1 -1

但这组数据就连jxtxzzw的选择排序也能够在 秒钟内得到结果。

注意你构造的排序规模不能太大,否则可能连一般的选择排序都没法在 秒钟之内得到结果,但也不能太小,否则连jxtxzzw的选择排序都可以在 秒钟之内得到结果。

你可能需要在巧妙地进行数据的分布和排列,而不是一味研究数据规模。

提示

判题程序首先会读入你构造的数据,然后进行一般的选择排序。

如果一般选择排序能够在 秒内得到结果,判题程序会继续用原始数据进行jxtxzzw的选择排序,否则反馈错误

如果jxtxzzw的选择排序得到答案的时间大于 秒,则反馈正确,否则反馈错误

如果你需要更详细的判题结果[判决书],你可以在[Problem3607]提交,并花费EMB购买判决书,我们给每一个错误结果都输出了详细的信息,由此你可以知道自己构造的数据究竟还有哪里需要改善。

另外,考虑到判题机的性能,如果运行结果在5000毫秒边界值,建议你多试几次。

32 人解决,60 已尝试。

49 份提交通过,共有 991 份提交。

7.9 EMB 奖励。

创建: 6 月,1 周前.

修改: 5 月前.

最后提交: 1 天前.

来源: 数据结构上机实践课程(2018年秋)

标签