1樓：
並不是，在不考慮空間複雜度的情況下，排序是可以提速到O(N)的時間複雜度的。
來想象乙個最簡單的場景：給定乙個元素個數為N的陣列，且每個元素的權重都可以用乙個唯一的數值（id）來表示，這些id之間可以比較，但是即不連續，也非偏序，接下來我們進行排序
第一次遍歷，我們只取整個陣列中id最大的兩個值，之後根據該值構造乙個等長度空陣列（中間容器）。
之後，我們再次遍歷這個陣列，將每個元素放入到中間容器下標等於元素id的位置
最後，我們遍歷中間容器構造鍊錶，並且過濾掉其中初始值為空的部分。
這時，我們就通過３次遍歷，完成了乙個陣列的排序。
然而這個中間容器的尺寸是未知的：如果原陣列中的id最大值過大的話，那麼這個中間容器的分配和初始化實際上是沒有「工程意義」的。
O(NlogN)的時間複雜度一般都會附加乙個前提，就是空間複雜度同樣在O(NlogN)的程度上（例如歸併排序），而快速排序之所以是經典演算法，重點就在於其O(NlogN)的平均時間複雜度同時還只有O(N)的空間複雜度
2樓：窗戶
基於比較的排序演算法，最快只能做到到O(nlogn)時間複雜度。
這樣來看吧，我們把演算法中按照時間順序比較結果作為乙個bool序列，把n個數的排列作為結果。
那麼這個bool序列等同於對1,2,3,...n的排列的編碼1...n的排序的資訊量為log(n!)
而O(log(n!)=O(nlogn)
bool序列是一樣的資訊量，且不大於時間複雜度(我們認為每當產生乙個比較結果花費的時間代價為O(1))
3樓：人可玉
直接設計ASIC，硬體平行計算，比你cpu慢慢爬，能快多少個數量級，取決於你願意花多大的電路成本。
GPU有類似的電路結構，如果軟體工程師沒有ASIC可用，可以呼叫相應的GPU資源。但是GPU的資源不一定匹配你的應用需求，還有很大的電路延遲，加速效果是比較有限的。
4樓：智商稅
12.8修改：糾正表述為基於比較的排序演算法。「比較」是資訊源，是基石。
基數排序的時間複雜度也是最好 ，最壞 。下面以基數排序為例說明「比較」資訊如何起作用。
使用有限個取值的關鍵碼（設數量為M，一般不大），整數的子集自然有序。對關鍵碼進行二分查詢比對的時候，獲取的資訊量是常數（被常數 控制，但更多的時候被視為 ；「＜」是一次比較，又可以視為使用「是」和「否」兩個關鍵碼）找到後就把元素接在關鍵碼所屬的桶之後，這樣的接桶鑄成了順序。而N個不同的數，至少需要有 個關鍵碼，即M進製的0~N數字寫法，來將它們相互區分；最多就是占有 個不同的關鍵碼。
即使數值高度趨同，類似於聚點，演算法也能把「眾人一致」的無效的關鍵碼盡可能剔除，比如接桶的時候記錄振幅 W←W or (a[0] xor a[i])；但此時人們可能更應該考慮傳統比較整個實數比如3.1415926<3.1415927的時候注入的資訊量是不是1了。
這樣算下來最好的比較次數能被控制於 。因為大O表示法是對係數不敏感的，所以換底公式的影響之下對數之底也不甚重要，基數排序的時間複雜度就把對數的底一拋，寫成 。
容易算出，基於比較的排序的時間複雜度就是O(N log N)。
事實上，等概率出現的定域粒子群，兩次試驗之間所進行的，正是無數次的交換。換句話說，狀態轉移是通過交換實現的。N粒子系統，粒子甲出現在位置A的概率正是 。
事實上出現在任何位置的概率都是這樣。定域子系統是有N個位置的。
根據統計系綜的精神，分子均的熵值須是：概率值的負對數的均值。
均值的演算法是 :=\sum_^\infty p_i X_i" eeimg="1"/>
=-k\sum_^\infty p_i \ln p_i" eeimg="1"/>
現在有且只有N個非零概率值為 ，代入就是
每個粒子的平均熵值是 ，所以整個系統的總熵值就是
根據熵的資訊意義：
假設我們每次能獲得1bit資料，就至少需要獲得（nlogn）bit資料才能取消資訊的不確定性。
時間複雜度正是假設「每次獲取資訊量是定值」，即獲取資訊的程度正比於用時，所以時間複雜度會正比於熵值。
5樓：Joseph
從程式角度看，簡單的說n個輸入元素可以有n!種排列方式，假設基於比較的排序演算法需要一共k次比較，比較結果記為 ，這種比較結果一共有 種(每次比較有兩種可能). 如果< n!
, 這必然說明基於比較的演算法對至少2個完全不同的輸入產生了完全一樣的比較結果，這是不可能的，說明程式必然有錯，所以如果程式正確 , 所以 , 所以基於比較的排序演算法下限是 (程式執行時間 ，c是常量)
6樓：
這是比較排序演算法的下界，非比較排序演算法可參考radix sort (https://
en.wikipedia.org/wiki/Radix_sort)
7樓：
當你有n個元素要排序，你可能會有n！的排序結果。
你可以把所有結果放在一棵樹下，把排序當成在這棵樹裡面找到乙個節點。
log(n!)
接下來，n!總是小於
所以 log(n!)
教授講的哈，畢竟剛上個intro的課
8樓：科技方子春
說起來我想到過乙個非常鬼畜的排序方法，要求被排序的是整數step1,準備一張非常大的質數表
step2,把待排序的陣列，比如有乙個整數是3，就轉化成第三個質數，然後乘起來
step3,從1開始遍歷那個質數表，比如第三個質數能被那個數整除，就寫下3，然後把那個數除以三繼續，直到那個數變成1就排好啦
我也不知道複雜度多少……………………
9樓：葫蘆屯王大力
所有基於比較的排序演算法的比較次數下限都是. 證明：
個數一共有種排列，在大小的搜尋空間內找到某個特定排列的過程就是在一顆二叉決策樹中從根節點遍歷到葉子節點的過程（每個節點代表一次比較，之所以選擇二叉樹是因為的比較結果只有兩種，搜尋空間的最佳剪枝策略就是每次比較砍掉一半的樹枝/可能性，也就是說每次比較出現兩種結果的可能性都是等概率的才能最快速度的縮小搜尋空間）。的下界就是.證明如下：
參考文獻：
1. 資料結構與演算法分析——C++描述英文原版 pp.297-299
10樓：Belleve
n 個元素有 n! 種排列，每次比較可以獲取 1b 的資訊量，因此獲得足夠的用於比較的資訊量需要的次數是 。
當然了還有乙個最低的下界，你總得把輸入讀完，不是麼？
11樓：
首先，所有基於比較的排序演算法，都是以決策樹模型作為依據的。
對於待排序的 n 個元素，其所有可能的排序種數為 n! ，其決策樹高度為 h （即為排序演算法比較的次數）
高度為 h 的決策樹，最多有葉子節點 個，所以就有 =n!" eeimg="1"/>
=log(n!)" eeimg="1"/>由斯特林近似公式：
得 =\frac log(2\pi)+\fraclog(n)+nlog(n)-nlog(e)+log(1+\Theta (\frac))
" eeimg="1"/>
其中，故，的漸近下界為
12樓：
Introduction to Algorithms上說過，基於比較的排序最快的演算法（快排）相當於構建二叉樹，樹的高度是logn，總的時間複雜度就是O(Logn)。然後又講了乙個非比較排序，就是計數排序，發明這個演算法的人就是IBM創始者。計數排序的複雜度為O(n)
13樓：Milo Yip
這是比較排序的序列演算法下界。
如果是並行的話，可以用硬體空間換取時間，例如 Bitonic sorter 和 Batcher odd-even mergesort的並行延時都是。
14樓：曾加
當被排序的數有一些性質的時候（比如是整數，比如有一定的範圍），排序演算法的複雜度是可以小於的。
比如計數排序複雜度要求：被排序的數是0~k範圍內的整數
基數排序複雜度要求：d位數，每個數字有k個取值
桶排序複雜度 （平均） 要求：被排序數在某個範圍內，並且服從均勻分布
但是，當被排序的數不具有任何性質的時候，排序的複雜度的下限必須是。
證明：
當被排序的數不具有任何性質的時候，我們只能用相互比較的方法來排序。比較排序可以被抽象成一課決策樹，它是一顆完全二叉樹。
設待排序陣列共有n個數，我們不知道這個被排序陣列的任何性質，所以它的順序有n!種可能。而每一次排序都是二分的，假設經過k次排序，可以將這 n! 種可能區分開來，由抽屜原理，必有，於是
由斯特靈公式
15樓：舒自均
這就是比較排序演算法的極限.
從數學的角度來看,
1.n個不同的元素,可能的大小順序一共有n!種
2.抽兩個元素a,b,要麼a比b大,要麼a比b小,兩種情況包含的可能性一共種,所以至少有一種包含了種可能性,假設每次都運氣不好,留下了多的那部分
3.再抽另兩個元素來比較,在剩下種可能性中,又會有少於一半的可能性被排除,於是兩次比較,可能的順序種類從下降到了(大於等於)
4.每比較一次,可能的順序種類最多下降一半,於是要想讓可能的順序種類減到1(也就是排序完成),需要x次,那麼必須至少有n!" eeimg="1"/>
換一種說法,x次比較最多能得出2^x個不同的結果,它必須比n!大,才能區分所有的情況
當然如果允許元素之間相等,那就是把底數的2改成3,取對數以後差乙個常數倍數
於是log_(n!) " eeimg="1"/>
後者用斯特林公式
自然就會得到x的下限和是同階的.n很大時最多相差乙個常數的倍數
快排堆排和歸併,差別就在這個倍數上.但是都沒有達到理論上的最優.如果人來做排序,可以比快排更快.
解釋最後一句
這裡"人來做"的意思是,人和機器一樣不能一下知道全部數的大小,需要每次挑兩個來比較
但是人比機器優越的一點在於,人腦的"記憶體"管理/定址過於強大,所以人可以用(例如)二分插入這樣的東西來做.
16樓：陶百百
同上，劉誠同學所說，這是基於比較排序的極限了，演算法導論上好像給了證明，同時這裡有一篇好文，微軟亞洲研究院的劉未鵬寫的，可以看看，比較深入淺出
數學之美番外篇：快排為什麼那樣快
然後就有不是基於比較的排序了，比如計數排序(O(n)，記憶體夠用的情況下)，基數排序（O(m*n)），桶排序(O(n)，輸入資料分布均勻的情況下)，這幾個排序在演算法導論上都有介紹，
還有就是位排序，好像學術上並不承認，本人覺得位排序實質上就是在特殊的輸入下面，經過優化的計數排序，(O(n)，但是位排序的空間大概是計數排序的1/（比較關鍵字的記憶體大小）（這裡假定是32位整型，就優化為1/32）)
有沒有比較新穎的排序演算法和分類演算法？
Alex 有，我今天上午剛發明了乙個。intFindMin inta,intArrySize returnj 這個演算法的目的是，在乙個陣列中，找到乙個最小的沒出現過的正整數。例如 在陣列中沒有出現過的最小的正整數就是1。這是2018年408的一道真題，做完以後發現我這個比答案還漂亮，更短 更快 更...
你們用排序演算法排序八百萬個數的最快時間是多少？
現在沒電腦，大略說一下我原來做過的測試吧。具體的資料規模已經忘了，只記得最快的是stdsort和mergesort，然後是qsort和heapsort 具體哪個快忘了，但是手寫的mergesort居然壓過了手寫的qsort，而且前面幾樓也沒提過mergesort。 肖進 來乙個C 的單執行緒基數排序...
關於快速排序演算法的穩定性？
網際網路民工 重點在第二步 這個放是採用交換的形式，還是插入的形式 如果是交換，則不穩定，如果是插入則穩定 不過陣列的插入本身效率低 比特曼 按照題主的這個補充，快排可以是穩定的，取決於具體的快排演算法。常用的比較好的快排演算法 比如高讚回答的 應用這種補充不會讓他變得穩定。但其他版本的快排 比如快...