N個數最少比較多少次才能保證知道大小順序?

01-04

這N個數沒有相等的.
"一次比較"是指從這些數里挑兩個,然後知道他們之間的大小關係.
這裡分作兩種情況:
1.可以通過前面的比較結果決定下一步挑哪兩個.
2.必須固定一個挑法,然後一口氣比較這麼多次,然後根據結果直接出結論.

先說第 1 種情況：

這個問題在 Donald Knuth 所著的 TAOCP 里有詳細的討論，中文好像譯為最少比較排序。

（當然應該有很多paper 討論過這個問題，但我只看過書）

首先有個下界很容易算，因為 n 個數排序最多有 n! 種可能，一次比較產生兩種結果，

所以至少需要 $log_2 n! = Theta(nlog n)$ 次比較，

但是這個比較次數是不一定能達到的。

目前比較次數的下確界還沒有一個通用的公式，據我所知好像只能暴力找。

當然任何一種基於比較的排序演算法的時間複雜度都可以提供下確界的一個上界，

一個比較好的上界就是隨機快速排序的期望比較次數： $(2n+2)sum_{k=1}^n frac{1}{k} - 4n$ ，

大概是之前所說的下界的 2 倍，還是有不小差距的。

==========================================================================

再說第 2 種情況：

要保證最後能排好序，一定需要 ${n choose 2} = frac{n(n-1)}{2}$ 次排序，

這是因為如果在排好序之後 a 和 b 是相鄰的，那麼它們的大小關係只能通過直接比較確定，

不可能通過和其他數的比較來確定它們的大小關係。

（事實上它們對於其他數的大小關係是完全一樣的，如果 a &> c，那麼也有 b &> c，反之亦然。所以不直接比較 a 和 b 是無法區分這兩個數的大小關係的。）

第一問其實就是排序演算法的最差情況嘛。歸併排序和堆排序都是O(nlogn)的。

關注這個問題其實是因為我們上課提到了一個實驗，當時想到了比較類似這個問題的問題，也一直在試著尋找答案。經過了挺久……現在可以把思考的東西分享一下了。以及……我比較啰嗦，還請見諒。

在實驗設計中，我們有時會遇到這樣一種情況：獲得n個對象的排序，以便於開展後續內容。這個排序不一定是簡單的大小排序，更普遍地，它是對對象關於某種性質的比較的排序。

我們最容易想到的、也是在實際中的確如此應用的是：通過兩兩比較獲得成對的關係信息，從而求得排序。不難想見的是，對於n個關係未知的對象，在不經過特殊處理、隨機配對比較的情況下，如果我們的運氣足夠好，最少可以通過n-1次比較獲得其排序，但如果運氣非常糟糕，就一定需要n*(n-1)/2次比較。也就是說，真正起作用的是那關鍵的n-1條信息，在完全的n*(n-1)/2條信息中，有相當一部分是冗餘的。這裡我用一個例子說明一下：

例1. 設有四個對象A,B,C,D(假定其強弱關係為A&>B&>C&>D)進行比較，完全的對比信息如下：①A&>B ②A&>C ③A&>D ④B&>C ⑤B&>D ⑥C&>D. 由於比較的傳遞性，我們可以發現，②可以由①④得出、③可以由①⑤或②⑥得出、 ⑤可以由④⑥得出，相對地，②③⑤所提供的信息就是「多餘」的。

* 值得注意的是，例1僅用於說明完全的比較信息有冗餘，並不能說明獲取ABCD的排序不需要②③⑤。

那麼至少需要多少次比較才可以保證獲得n個元素的關係順序？如此發問，就是假定了我們考慮的是最糟糕的情況。回到例1，實際上四個對象的排序至少需要5次比較才能確保獲得正確的結果。下面將用例2展示這個過程。

例2. 沿用例1的假設，首先對四個對象分組對比，不妨假設A與C一組、B與D一組，我們可以得到：①A&>C ②B&>D ；然後對①②中較大的數做比較，得到：③A&>B ；此時可知：A&>B&>D,A&>C ；然後我們需要在已知B&>D的基礎上得到B,C,D三者的關係，即至少要再進行兩次對比。綜上，即共需要進行5次比較才能確保四個對象的正確排序。

當時我想到這裡的時候……在一篇博客( http://blog.csdn.net/fisher_jiang/article/details/2442486)上看到了關於5個數排序的方法，我把它整理成了便於同本篇其他部分結合理解的格式，依然作為引用：

H.B.Demuth 曾思考過5個對象的情況，並於1956年在他的博士論文中提出了一種解決方法，例3將展示這種方法：
例3：設有五個對象A,B,C,D,E進行比較，前兩步與例2相同。首先比較A,B，接著C,D，然後把每對的較大者拿來比較，這就產生了A&>B&>D和 C&>D，這3次比較，可以找到如下有序關係 (以下圖中所有連線均表示左下元素比右上元素小)：
B—D
/ /
A C E
這時,我們把第5個元素E插入到{A,B,D}當中的適當位置，只需比較兩次，首先同B進行比較，而後同A或D進行比較，就有如下所示的四種情況：
B—D E—B—D B—E—D B—D—E
/ / / / / / / /
E—A—C A C A C A C
對以上任意一種情況，總可以通過兩次比較將C調整入由ABDE構成的有序隊中。這樣處理後總共需要比較3+2+2=7次。

那麼總結例2、例3，可以發現一種有規律的比較方法：先通過3次比較獲得四個對象的兩組強弱關係(如A&>B&>D和 C&>D)，然後通過二分思想進行插空。對於不同的n，我們可以列出下表觀察規律，表中加了下劃線的位置代表在該位置對C進行插空。

觀察該表可以得出，由於除以2並取整，C在奇偶位置進行插空得到的比較次數不同，這個變化幅度為1。當對象數目增大時，這個影響相對越來越小，可以被忽略。

因此我們可以規定在最後一個位置對C進行插空，這樣可以得到比較次數為：

$3+sum_{i=4}^n |frac{n}{2}|+|frac{n-1}{2}|$

(「||」表示向下取整)

然後！對，我去找了老師聊這個問題，老師說計算機領域已經有很多排序演算法啦！你了解一下吧！然後我就去聽了兩三節排序演算法的公開課。這裡我覺得比較有意義提到的是「歸併排序」，它貌似是目前已知的排序演算法中性能最好的了，速度快、也很穩定。

課程中所講解的是「二分歸併」(嗯對其實我鼓搗了一個三分歸併，然而對於在計算機上應用來說這個效率改進不算改進)，也是利用二分法思想進行遞歸的，可以用下面這個圖表示：

在這種方法中所需的比較次數為：

$sum_{i=1}^{log_{2} n} (2^i-1)frac{n}{2^i}=nlog_{2} n-n+1$

----從邏輯上看似乎需要一個分割線----

那麼到這兒為止所提到的這兩種方法，在演算法中都是很經典的，前者是插入排序、複雜度為 $O(n^2)$ ，後者歸併排序的複雜度為 $O(nlog_{2}n)$ (為什麼是這樣的……沒有演算法基礎的朋友們可以查一下時間複雜度有關的知識點，我就不解釋啦)

最後我們來對比一下在實際的實驗操作中，完全比較、二分插入、二分歸併所需比較次數的差距：

歸併排序的優勢實在是很突出……

----從邏輯上看似乎需要一個分割線----

嗯？寫了太久都有點混亂……到這兒似乎其實就，說完了？嗯大概就是這樣吧。

回過頭看題主的問題，想起還有個「第一種情況」。嗯排序演算法中還有一個方法叫做「堆排序」，這個方法也很巧妙，但比較碰運氣，在實際中運用的話比較難保證快速確定結果，選擇什麼樣的比較方案對得到結果的速度影響還是挺大的。

總之就是……知識真的好廣闊，感覺自己好渺小……以及……條條大路通CS真不是吹的 [笑哭]

最後以及，紀念我第一次這麼用心寫一條回答，也是第一次正式意義上分享我學習到的知識。時間到了，去上課了~

最少比較次數不太清楚，是不是只能暴力來找了。不過大致的時間複雜度是有的。

基於比較的排序演算法時間複雜度下界是n*logn，證明好複雜，我也沒記住(?_?)。當然可以給出額外的信息（數的範圍）使用桶排序讓下界達到n，不過這個就不是基於比較的了。

如果不用排序，而是找順序統計量（就是n個數中第k大的數）的話時間複雜度為n。這個也是基於比較的。

兩種方法的本質都是比較排序的複雜度下限問題，是 $O(nlg n)$ 的

n個數排序。

1，理論上，排序總共需要比較n(n-1)/2次。

2，分組後，可以減少比較次數。

n=2，f(2)=1。

n=3，f(3)=3。

n=4，f(3)+2=5，2f(2)+2+1=5，f(4)=5。

n=5，f(4)+3=8。其他方法，

A＞B，C＞D，第三次比較B和D

如果B＞D，則有A＞B＞D，C＞D；

如果D＞B，則有C＞D＞B，A＞B；

兩種情況等效，以第一種來討論，將E插入A、B、D中排序，需要2次；

如果E最小，C最多和AB比較2次就完成排序；3+2+2=7

如果D最小，C從ABE中間一個比較，最多2次就完成排序。3+2+2=7。

所以，f(5)=7。

n=6，最優演算法，f(6)=10。

n=7，最優演算法，f(7)=14。

n=8，最優演算法，f(8)=17。

n足夠大時，找到一個數去比較，分成大小不同的組，應該最快。

比如2n分成2個n，分組需要2n次，每組排序最多n(n-1)/2次，則總共不超過n(n+1)次。

可以利用差值的不同分多個組，進一步減少比較次數。

運氣爆棚，n-1次

0次。

使用哈希思想進行桶排序，把待排序的數與數組的下表構成映射。

比如原數組a[5 6 1 3 8 1]

哈希數組[0 2 0 1 0 1 1 0 1]

0 1 2 3 4 5 6 7 8

分別對應下標↑↑↑↑↑↑↑↑

整個過程完全不用比較。

中學生一枚，表示前一個回答的內容太深奧已經超出理解範圍了…說一下自己膚淺的認識，如果太不沾邊就請把我摺疊吧。

個人認為，當已經存在排好序的n-1項(n&>1)數列時插新的一項形成排好序的n項數列時，總會存在著這一項在與這n-1項數列中的所有項全都比較一遍才能夠確定其位置的情況。所以為保證排序，最多需要試驗的次數是1+2+…+(n-1)，即n(n-1)/2次。

啊還有第一種情況？抱歉不小心看漏了，我再去想想。