傳遞函數來排序功能

的關鍵我有一個列表傳遞函數來排序功能

lis = [ [0, 1], [1, -1], [1, 0] ]

我想根據特定條件來排序。我想使用一個邏輯，只要lis[i][0]等於lis[i + 1][0]，交換元素。類似於

在上面的列表中，第二個和第三個元素是[1, -1]和[1, 0]，其中lis[i][0] == lis[i + 1][0]。所以，我會掉它，使得我的新名單變得

lis = [ [0, 1], [1, 0], [1, -1] ]

這是我的函數：

def sortList(lis3): 
    for i in range(0, len(lis3) - 1): 
     for j in range(i + 1, len(lis3)): 
      if lis3[i][0] == lis3[j][0]: 
       lis3[i], lis3[j] = lis3[j], lis3[i]

我想這個函數傳遞給列表的sort方法，使得其根據本排序邏輯：

我想這樣做，但不工作：

lis.sort(key=sortList)

^h我可以讓這個功能在sort方法中工作嗎？

來源

2017-07-14 Souvik Ray

這與排序不一樣...排序必須是全局屬性，而不是直接依賴於鄰居。（如何使用合併排序？或其他排序算法？結果將如何？[python使用[timsort]（https://en.wikipedia.org/wiki/Timsort）]）。 –

@hiroprotagonist那麼有沒有另一種方法可以做到這一點？ –

這個問題並沒有很好的定義......'lst = [（0,0），（0,1），（0,2）]'：結果是什麼？您在列表中迭代的次數和次數？你什麼時候完成？ –

正如在其他答案中已經說過，它不可能（或至少不平凡），使其與sorted工作。然而，你可以不用任何的排序，只是基於第一個元素收集指標：

from collections import defaultdict 

lis = [[0, 1], [1, -1], [1, 0]] 

d_idx = defaultdict(list) 

for idx, item in enumerate(lis): 
    d_idx[item[0]].append(idx)

然後創建一個「結果」列表中，只是扭轉具有相同的第一元素中的所有元素的索引：

res = [None]*len(lis) 

for _, value in d_idx.items(): 
    for orig_idx, target_idx in zip(value, reversed(value)): 
     res[target_idx] = lis[orig_idx]

其中給出的res：

>>> res 
[[0, 1], [1, 0], [1, -1]]

注意：它可能不是所期望的行爲，以「反向」與相同的第一元素中的元素。因爲@hiro protagonist noted in the comments：

這個問題沒有很好的定義...... lst = [(0,0), (0,1), (0,2)]：結果是什麼？您在列表中迭代的次數和次數？你什麼時候完成？

的情況下，你需要一個不同的行爲哪些元素應該被分配到哪個位置，你（可能）只需要更改for orig_idx, target_idx in zip(value, reversed(value)):線，有應用所需的操作。

進一步的優點是，這種方法只具有O(n)運行時行爲而sort具有O(n*log(n))（平均）運行時。所以它可能會更快。

來源

2017-07-14 14:02:15 MSeifert

cool！所以我最好不要使用排序功能，並嘗試以你的方式做到這一點:) –

python排序方法將對列表進行排序，僅使用項目之間的<比較。您必須傳遞一個函數，將每個元素映射到可能與其他映射元素進行比較的某個元素，以便「小於」關係提供所需的結果。

但是，您的規則並未定義任何類型的關係，可以根據元素a，b的a < b來描述。它只是定義相鄰元素之間的關係，它甚至不是一個穩定的關係：如果a < b因此您交換這兩個項目，那麼它立即成爲b < a的情況。

簡而言之，lis.sort()是完全不適合這項任務。

來源

2017-07-14 13:28:06 Duncan

您不能使它與list.sort或sorted可靠地工作。問題在於這些函數背後的排序算法並不能保證哪些元素被比較或者沒有（它只是說結果將被排序）。對於list.sort或sorted可以可靠地工作，您需要key的total ordering relation，這是您的功能不提供的。

此外key應該是一個功能，將一個元素轉換爲「應該比較的屬性」，它確實將列表的每個元素傳遞給key函數而不是總列表（事實上在CPython中列表爲空而你sort它，所以它根本無法工作）。執行此排序

來源

2017-07-14 13:28:39 MSeifert

的一種方法是使用cmp參數sorted（使用functools.cmp_to_key爲Python 3）和返回-1時在兩個子列表的索引0的項目比較等於或否則爲0。這是假設的項目是在對和是連續的，所以它不是一個真正的詳盡的梳理，只有一個的hackish的方式來交換你的項目：

lis = [ [0, 1], [1, -1], [1, 0], [2, 5], [2, 6]] 

print sorted(lis, cmp=lambda x, y: -1 if x[0]==y[0] else 0) 
# [[0, 1], [1, 0], [1, -1], [2, 6], [2, 5]]

然而，分揀變得曖昧當兩個以上的項目在索引0處具有相同的值，或者項目不是連續的。

OTOH，您可以循環訪問您的列表並交換符合條件的成對連續項目。無需應用分類！

來源

2017-07-14 13:34:55

，並不保證所有項目都是相互比較的。所以它可能工作或不工作取決於哪些項目進行比較。 – MSeifert

@Moses你可以在python 3中顯示相同的實現嗎？我嘗試使用functools.cmp_to_key但彈出錯誤。 –

@SouvikRay'sorted（lis，key = functools.cmp_to_key（lambda x，y：-1 if x [0] == y [0] else 0））' –

傳遞函數來排序功能

回答

相關問題