我简直不敢相信它能排序
I Can't Believe It Can Sort

原始链接: https://yugen-tsuki.github.io/unbelievablesort.html

“我无法相信它能排序”是一种简单但低效的 O(n²) 排序算法,它在嵌套循环中反复比较并交换元素,只要 arr[i] < arr[j]。尽管它出乎意料地正确,但比快速排序或归并排序慢得多。附带的 Java 实现将此方法应用于整数数组。

Hacker News 帖子讨论一种许多人最初怀疑能否工作的简单排序算法。评论者澄清它不是冒泡排序:与冒泡排序不同,它反复比较所有位置,包括更早的位置,但仍然能排序。一篇链接的论文用三个定理证明其正确性,并将其描述为慢速 Θ(n²)、非稳定、不适合外部、在线或部分排序的输入、几乎无直观理解,但具有显著简洁性。用户将其与手动排序比较,提到 Matt Parker 的视频,并争论其机制,指出第一趟会把最小元素放到位置 0。一些人对 Grok 和 Gemini 的静态分析识别出它是排序算法感到印象深刻。其他人要求形式化证明,或把“<”运算符视为提示。总体来说,这是一种看起来荒谬但已被证明的 O(n²) 排序算法。
相关文章

原文

The I can't believe it can sort algorithm is a very simple but inefficient algorithm. The reason that it is named so is because if you were to look at the pseudocode, you won't think that it can actually sort but it does. Here is the pseudocode:


                            
for i = 1 to n do
    for j = 1 to n do
        if A[i] < A[j] then
            swap A[i] and A[j]
                            
                        

The pseudocode was lifted, verbatim, from the research paper  "Is this the simplest (and most surprising) sorting algorithm ever?" by Stanley P. Y. Fung. You can find the paper here.

As evidenced by the pseudocode, I Can't Believe It Can Sort is a simple and inefficient sorting algorithm that uses nested loops to repeatedly compare and swap elements until the array is sorted. This algorithm has a time complexity of O(n^2), making it much less efficient than well-known sorting algorithms like quicksort or mergesort, which have better average and worst-case performance.

Here is a java implementation of this algorithm:


                            
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 + " ");
    }
                                
}
                            
                        
联系我们 contact @ memedata.com