如何僅使用7個比較對5個項目進行排序

我對僅使用7個比較對5個項目進行排序非常感興趣。我想我理解如何做到這一點的理論，但不幸的是我不能將它寫成代碼。 Here I found an example in LISP 如何僅使用7個比較對5個項目進行排序

我真的很想理解它，但在我看來，它並不工作。例如數字5,4,3,2,1。

有沒有人請給我一個示例代碼，但不是在LISP？我更喜歡Java或C/C++。這對我在學校真的很有幫助。

謝謝您提前

P.S.對不起，我的英語

編輯：在這裏，我添加了一些我用Java編寫的代碼。變量a，b，c，d，e僅用於我在代碼中更好的定位。我可以爲特定的輸入項目編寫特定的代碼，這沒有問題。但我不能寫一般的代碼。

public static void sort(int p[]) { 

    int a = 0; 
    int b = 1; 
    int c = 2; 
    int d = 3; 
    int e = 4; 


    if (p[a] > p[b]) { 
     swap(p,a,b); 
     } 
    if (p[c] > p[d]){ 
     swap(p,c,d); 

     } 

    if (p[b] > p[d]){ 
     swap(p,b,d); 

    } 

    if (p[e] < p[b]) { 

     if (p[e] < p[a]) { 

      swap(p,a,e); 
      swap(p,d,e); 
      //swap(p,b,d);//BLBE 
     }else{ 

      swap(p,b,e); 
      swap(p,d,e); 
     } 
    }else { 
     if (p[e] < p[d]) { 
      swap(p,d,e); 

     } 
    } 

    if (p[c] < p[b]) { 

     if (p[c] < p[a]) { 

      swap(p,a,c); 
      swap(p,b,c); 
     }else 
     { 

      swap(p,c,b); 
     } 
    }else { 
    if (p[c] > p[d]) { 

     swap(p,d,c); 
    } 
    } 

}

來源

2010-11-21 vojtak

+12

如果您瞭解理論，並且您已經嘗試自己編寫一些代碼，那麼我建議發佈您寫的內容並描述您遇到的具體問題。簡單地要求代碼的問題不可能在這裏得到很多答案。 – Grodriguez 2010-11-21 22:14:03

1.編寫一個程序，創建一個二叉樹，插入其中排序的所有數字。這是0 + 1 + 2 + 3 + 4 = 10的比較。 2.修改程序，以便在第四次插入之前，圖形在中間數字周圍平衡。這會給你0 + 1 + 2 + 2 + 3 = 8的比較。 3.修改程序，以便在第五次插入之前，根元素的較大子樹以與第二步中相同的方式進行平衡，這樣可以減少一次比較。 – 2010-11-21 23:10:28

@Rosh：這是答案，你爲什麼不把它作爲一個發佈？ – Daniel 2011-02-02 08:22:31

編寫一個通用的基於比較的排序算法需要O（n lg n）比較。如果我沒有弄錯，那麼所有的O（n lg n）排序算法將在大約7次比較中對5個項目進行排序。如果你幸運的話，可以使用Mergesort，Heapsort和Quicksort。

來源

2011-02-02 08:13:37

我相信你的意思是O（lg n！）= O（n lg n）？應該可以通過7次比較來做到這一點。 – templatetypedef 2011-02-02 08:16:14

@templatetypedef：感謝您的糾正，我錯了。我的文章已被編輯以反映這一點。 – 2011-02-02 22:50:02

如何僅使用7個比較對5個項目進行排序

回答

相關問題