Python排序和排序 - 列表清單是如何精確排序的？

在Python中使用的精確規則是什麼，以便對列表進行排序列表，其中的元素是列表？這可以表示爲'鑰匙'或'cmp'功能嗎？問題來自於要考慮的兩件事情：長度和它們的值的位置。Python排序和排序 - 列表清單是如何精確排序的？

sorted([ 
    [ 0, 1, 2, 3 ], # 1st line: longer list 
    [ 0, 1 ],  # 2nd line: shorter list 
    [ 0, 2 ]   # 3rd line: suspected last 
])

假設第二行會在第一行之前排序是否安全？假設第三行總是最後排序是否安全？

請注意，這是不是關於穩定性！上述具體情況如所述的那樣表現爲。但是，那裏的規則是否可以考慮爲一般？ python在這裏應用的準確規則是什麼？

依託以下定義Lexicographical Order（感謝Ashniwi）：

爲了比較不同長度的序列，較短序列通常填充在有足夠的「空白」的端部（一個特殊的符號，它被視爲小於A的每個元素）。字典中總是使用這種比較長度不同的序列的方法。然而，在組合學中，經常使用另一種約定，其中較短的序列總是小於較長的序列。這種字典順序的變體有時被稱爲shortlex 的順序。

Python是否使用'簡短訂單'。這個假設的證明在哪裏，超出了實際例子？

來源

2017-07-06 Frank-Rene Schäfer

您可以指定擁有規則使用'sorted'或'list.sort'中的'key'關鍵字參數對list中的列表進行排序。參數的值是一個函數，它接受單個參數（列表中的每個元素）並返回每個元素的排序值。您可以使用'len'作爲'key'來按列表中的列表長度進行排序。 – stamaimer

我認爲是......這是默認的列表排序，即按字典順序。 – Julien

可能有一個默認值，儘管最好在可能的情況下指定排序參數（在將來的發行版中爲默認更改）。請參閱stamaimer的評論。 – ChickenFeet

從docs引用：

特別地，元組和列表被比較相應的元件字典順序進行比較。這意味着爲了比較相等，每個元素必須比較相等，並且兩個序列必須是相同類型且具有相同長度的。

Lexicographical comparison between built-in collections works as follows：

對於兩個集合爲比較相等，它們必須是同一類型的，具有相同的長度，並且每一對對應的元件必須比較相等的（例如，[1,2] == (1,2)是假因爲類型不一樣）。

支持訂單比較的集合按與其第一個不相等元素相同的順序排列（例如，[1,2,x] <= [1,2,y]與x <= y的值相同）。如果相應的元素不存在，則首先對較短的集合進行排序（例如，[1,2] < [1,2,3]爲true）。

def cmp(list_1, list_2): 
    length_1 = len(list_1) 
    length_2 = len(list_2) 
    min_length = min(length_1, length_2) 

    # Compare individual items till there's a different item found 
    for i in xrange(min_length): 
     if list_1[i] > list_2[i]: 
      return 1 
     elif list_1[i] < list_2[i]: 
      return -1 

    # All items were same so far, let's compare sizes. 
    if length_1 > length_2: 
     return 1 
    elif length_1 < length_2: 
     return -1 
    elif length_1 == length_2: 
     return 0

演示：

>>> lst = [[ 0, 1, 2, 3 ], [ 0, 1 ], [ 0, 2 ]] 
>>> print sorted(lst) == sorted(lst, cmp=cmp) 
True

相關CPython code for reference：

對列表進行基本的比較可以使用此函數來表示

/* Search for the first index where items are different */ 
for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) { 
    int k = PyObject_RichCompareBool(vl->ob_item[i], 
            wl->ob_item[i], Py_EQ); 
    if (k < 0) 
     return NULL; 
    if (!k) 
     break; 
} 

if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) { 
    /* No more items to compare -- compare sizes */ 
    Py_ssize_t vs = Py_SIZE(vl); 
    Py_ssize_t ws = Py_SIZE(wl); 
    int cmp; 
    PyObject *res; 
    switch (op) { 
    case Py_LT: cmp = vs < ws; break; 
    case Py_LE: cmp = vs <= ws; break; 
    case Py_EQ: cmp = vs == ws; break; 
    case Py_NE: cmp = vs != ws; break; 
    case Py_GT: cmp = vs > ws; break; 
    case Py_GE: cmp = vs >= ws; break; 
    default: return NULL; /* cannot happen */ 
    } 
    if (cmp) 
     res = Py_True; 
    else 
     res = Py_False; 
    Py_INCREF(res); 
    return res; 
}

來源

2017-07-06 07:05:26

我會認爲你的答案是最合乎邏輯的。但是，我很難看到一個證明。你能詳細說明一下嗎？ –

@ Frank-ReneSchäfer證明在？你可以用'cmp'參數提供Python2的排序函數。 –

有人可能會使用你的'cmp'，是正確的。但是如果默認行爲是相同的，那麼它可能會更有效率。您提及的文檔對身份的評論不是按順序提供的。 –

默認情況下，sorted使用__lt__方法比較項目。根據Python文檔，按照字典順序對具有可比元素的列表進行比較。所以是的，該語言保證在較短的字符串中將被排序在較長的字符串之前。

來源

2017-07-06 06:59:29

Python排序和排序 - 列表清單是如何精確排序的？

回答

相關問題