Примеры различных способов сортировать списки на языке питон.

Способы разобраны на примере задачи о «непрерывном рюкзаке»: у нас есть n мешков с золотым песком, i-ый мешок стоит cost[i] денег и содержит weight[i] песка.
Нужно вывести номера мешков в порядке, в котором нужно их «жадно» засыпать в свой рюкзак, чтобы получить как можно большую общую стоимость.

Чтение и инициализация данных.

n = int(input())
cost = [int(x) for x in input().split()]
weight = [int(x) for x in input().split()]
# We will sort indices!

1 способ: сортируем кортежи (tuples)

# Way 1: wrap our data in tuples, sort, extract data from tuples.
indexed_unit_weight = [(cost[i] / weight[i], i) for i in range(n)]
indexed_unit_weight.sort(reverse=True) # Instead of reverse we could use -cost[i] / weight[i] above.
indices = [p[1] for p in indexed_unit_weight]
print(indices)
indices = [i for (uw, i) in indexed_unit_weight]
print(indices)

2 способ: именной параметр key у функции list.sort

# Way 2: sort by ascending of key function.
def unit_weight(i):
  return -cost[i] / weight[i] # Instead of "-" we could use reverse below.

indices = list(range(n))
indices.sort(key=unit_weight)
print(indices)
indices.sort(key=lambda i : -cost[i] / weight[i])
print(indices)

3 способ: используем специальную функцию, чтобы сравнивать два элемента

# Way 3: sort by using specific comparisson function instead of standard "<".
# !!!The only way where we can use comparisson without division!!!
from functools import cmp_to_key # should be at the beginning.

def compare(i, j):
  return cost[i] / weight[i] > cost[j] / weight[j]

def nice_compare(i, j):
  return cost[i] * weight[j] > cost[j] * weight[i]

indices.sort(key=cmp_to_key(nice_compare))
print(indices)
indices.sort(key=cmp_to_key(lambda i, j : cost[i] * weight[j] > cost[j] * weight[i]))
print(indices)

4 способ: создаём свой тип данных, в котором перегружен оператор «меньше»

# Way 4: create specific type and define your own operator "<".
class ItemIndex:
  def __init__(self, i):
    self.index = i

  def __lt__(self, other): # This is "<", __lt__ is «less than»
    i = self.index
    j = other.index
    return cost[i] * weight[j] > cost[j] * weight[i]

rich_indices = [ItemIndex(i) for i in range(n)]
rich_indices.sort()
indices = [ri.index for ri in rich_indices]
print(indices)