python2.7的sort函數默認採用什麼排序演算法，適用於怎樣的數列的排序？

剛學python，想請教一下，默認的函數會不會影響運行效率。

python中的sorted排序，真的是高大上，用的Timsort演算法。

什麼是Timsort，請看 wiki的解釋：http://en.wikipedia.org/wiki/Timsort

另外，國內有一個文檔，適當翻譯：Timsort原理介紹 - Data Analytics - 博客頻道 - CSDN.NET，

從時間複雜度來看，Timsort是威武的。

從空間複雜度來講，需要的開銷在數量大的時候會增大。

綜上，可以看出，就一般情況，使用sorted足以能夠完成排序的要求，並且是穩定的。

當然，python中也有其它一些排序模塊，都可以直接拿過來使用。

FROM: qiwsir/algorithm

引用自http://zhidao.baidu.com/link?url=wZD_oY7zrVdYLP6uvO1qUaiBRYvidsbw2e3xFYJf_sq-8lckxoQh7m5RJmTV6ZTveb_jHA_AzNqT_I8dR1Wnk_

@曹曉山

最近也在學習python，推薦《Python基礎教程》，雖然我只看了這本書……其中第二版40頁也詳細說明了高級排序的內容，使用的就是sort函數，當然下面的回答也是非常全面的。剛剛發現這是我的知乎首答，真是社會敗類啊，默默在知乎上混了好幾年……

———————————————————————————————————————————

Python中的sort()函數是序列的內部函數，函數原型：

L.sort(cmp=None, key=None, reverse=False)


函數作用：它是把L原地排序，也就是使用後並不是返回一個有序的序列副本，而是把當前序列變得有序。

Python中sort()參數說明：

(1) cmp參數

cmp接受一個函數，拿整形舉例，形式為：

def f(a,b):
return a-b


如果排序的元素是其他類型的，如果a邏輯小於b，函數返回負數；a邏輯等於b，函數返回0；a邏輯大於b，函數返回正數就行了。

(2) key參數

key也是接受一個函數，不同的是，這個函數只接受一個元素，形式如下：

def f(a):
return len(a)


key接受的函數返回值，表示此元素的權值，sort將按照權值大小進行排序

(3) reverse參數

接受False 或者True 表示是否逆序

Python中sort()函數舉例：

(1)按照元素長度排序

L = [{1:5,3:4},{1:3,6:3},{1:1,2:4,5:6},{1:9}]
def f(x):
return len(x)
sort(key=f)
print L
//輸出：
//[{1: 9}, {1: 5, 3: 4}, {1: 3, 6: 3}, {1: 1, 2: 4, 5: 6}]


(2)按照每個字典元素裡面key為1的元素的值排序

L = [{1:5,3:4},{1:3,6:3},{1:1,2:4,5:6},{1:9}]
def f2(a,b):
return a[1]-b[1]
L.sort(cmp=f2)
print L
//輸出：
//[{1: 1, 2: 4, 5: 6}, {1: 3, 6: 3}, {1: 5, 3: 4}, {1: 9}]