我简直不敢相信它能排序

Hacker News Top 论文

摘要

介绍了一个看似不可能排序但确实能排序的极简低效排序算法,源自 arXiv 论文《Is this the simplest (and most surprising) sorting algorithm ever?》,并附带 Java 实现,时间复杂度为 O(n²)。

暂无内容
查看原文
查看缓存全文

缓存时间: 2026/11/16 11:14

# 我不敢相信它能排序! 来源:https://yugen-tsuki.github.io/unbelievablesort.html "我不敢相信它能排序"算法是一种非常简单但效率低下的算法。它之所以得名,是因为如果你看了伪代码,你不会觉得它真的能排序,但它确实可以。以下是伪代码: `` for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j] `` 该伪代码逐字摘自 Stanley P\. Y\. Fung 的研究论文"Is this the simplest \(and most surprising\) sorting algorithm ever?"。你可以在[此处](https://arxiv.org/pdf/2110.01111.pdf)找到该论文。 从伪代码可以看出,"我不敢相信它能排序"是一种简单但效率低下的排序算法,它使用嵌套循环反复比较和交换元素,直到数组有序为止。该算法的时间复杂度为 O\(n^2\),因此效率远低于 quicksort 或 mergesort 等著名排序算法,后两者的平均和最坏情况性能都更优。 以下是该算法的 Java 实现: `` import java.util.*; import java.lang.*; class ICantBelieveItCanSort{ public static void iCantBelieveItCanSort(int[] arr){ int n = arr.length; for(int i=0; i<n; i++){ for(int j=0;j <n;j++){ if(arr[i]<arr[j]){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } } public static void main(String[] args){ int[] arr = {1,3,5,3,67,7,2,8,9,34,54,22,65,21}; iCantBelieveItCanSort(arr); for(int i : arr) System.out.print(i + " "); } } ``

相似文章

你的代码很快——如果你运气好的话

Hacker News Top

本文介绍了一种使用排序网络的无分支快速排序实现,并探讨了现代编译器(特别是Clang)如何在代码以恰当风格编写时,利用无分支指令来优化循环。

并行 O(√n) 开销 LSD 基数排序

Lobsters Hottest

本文介绍 Radsort,一种具有 O(√n) 开销的并行 LSD 基数排序算法,该算法稳定、易于实现,并且对于大数组优于传统方法。

对370,103个单词进行排序、哈希和草图计算

Hacker News Top

一篇技术博客文章,探索在包含370,103个英文单词的数据集上的排序、哈希和草图算法,衡量时间和内存成本,重点关注二分查找、快速排序和HyperLogLog等实际实现。

无分支快速排序:性能超越 std::sort 和 pdqsort,提供 C 和 C++ API

Hacker News Top

一种新的无分支快速排序实现(blqsort)借助排序网络技术,在 Apple M1 和 AMD Ryzen 系统上的性能超越了 std::sort 和 pdqsort,以单头文件形式提供 C 和 C++ 库。其性能提升得益于无分支分区、中位数之中位数枢轴选择以及针对小数组的自定义排序网络。