- 用 https://www.luogu.com.cn/paste/nzx555us 中代码
- 在此题运行
- 时限 \(\tt 1s\)，空间限制 \(\tt 256MB\)。
| 插入排序 | 冒泡排序 | 选择排序 | 希尔排序 | 快速排序 | 归并排序 | 堆排序 | 计数排序 | 桶排序 | 基数排序 | |
|---|---|---|---|---|---|---|---|---|---|---|
| \(n=10^3\) 随机数据 \(a_i \le 10^5\) | \(\tt 4ms\) | \(\tt 7ms\) | \(\tt 6ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) |
| \(n=10^3\) 完全正序 \(a_i \le 10^5\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) |
| \(n=10^3\) 完全倒序 \(a_i \le 10^5\) | \(\tt 4ms\) | \(\tt 8ms\) | \(\tt 8ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) | \(\tt 4ms\) |
| \(n=10^4\) 随机数据 \(a_i \le 10^5\) | \(\tt 80ms\) | \(\tt 373ms\) | \(\tt 200ms\) | \(\tt 7ms\) | \(\tt 6ms\) | \(\tt 6ms\) | \(\tt 7ms\) | \(\tt 5ms\) | \(\tt 8ms\) | \(\tt 5ms\) |
| \(n=10^4\) 随机数据 \(a_i \le 10^5\) | \(\tt 80ms\) | \(\tt 372ms\) | \(\tt 198ms\) | \(\tt 7ms\) | \(\tt 5ms\) | \(\tt 6ms\) | \(\tt 7ms\) | \(\tt 5ms\) | \(\tt 7ms\) | \(\tt 5ms\) |
| \(n=10^4\) 完全正序 \(a_i \le 10^5\) | \(\tt 79ms\) | \(\tt 5ms\) | \(\tt 4ms\) | \(\tt 5ms\) | \(\tt 5ms\) | \(\tt 6ms\) | \(\tt 6ms\) | \(\tt 5ms\) | \(\tt 7ms\) | \(\tt 5ms\) |
| \(n=10^4\) 完全倒序 \(a_i \le 10^5\) | \(\tt 101ms\) | \(\tt 407ms\) | \(\tt 394ms\) | \(\tt 5ms\) | \(\tt 5ms\) | \(\tt 5ms\) | \(\tt 7ms\) | \(\tt 5ms\) | \(\tt 7ms\) | \(\tt 5ms\) |
| \(n=10^5\) 随机数据 \(a_i \le 10^6\) | TLE | TLE | TLE | \(\tt 52ms\) | \(\tt 28ms\) | \(\tt 29ms\) | \(\tt 40ms\) | \(\tt 19ms\) | \(\tt 44ms\) | \(\tt 22ms\) |
| \(n=10^6\) 随机数据 \(a_i \le 10^7\) | TLE | TLE | TLE | \(\tt 683ms\) | \(\tt 275ms\) | \(\tt 294ms\) | \(\tt 438ms\) | \(\tt 174ms\) | \(\tt 517ms\) | \(\tt 216ms\) |
| \(n=10^6\) 随机数据 \(a_i \le 10^8\) | TLE | TLE | TLE | \(\tt 726ms\) | \(\tt 290ms\) | \(\tt 311ms\) | \(\tt 456ms\) | MLE | \(\tt 610ms\) | \(\tt 244ms\) |
| 总时间 | \(\tt 352ms + 3 \times \tt TLE\) | $\tt 1176ms + 3 \times \tt TLE $ | \(\tt 814ms + 3 \times \tt TLE\) | \(\tt 1497 ms\) | \(\tt 626ms\) | \(\tt 669ms\) | \(\tt 973ms\) | \(\tt 225ms + \tt MLE\) | \(\tt 1212ms\) | \(\tt 514ms\) |
总结：当值域较小时，计数排序无疑是最佳选择，在所有 AC 的算法中时间的比较：
基数排序 \(<\) 快速排序 \(<\) 归并排序 \(<\) 堆排序 \(<\) 桶排序 \(<\) 希尔排序。
标签：10,4ms,5ms,tt,算法,le,各类,TLE,排序 From： https://www.cnblogs.com/LByte/p/16601967.html