Сдвинуть последний элемент списка

Question

Я ищу эффективный способ сместить последний элемент списка в Python в соответствующую позицию. например, если у нас есть список = [1, 3, 4, 5, 6, 2], мы должны получить список = [1, 2, 3, 4, 5, 6]. То, что я пробовал, не работает желаемым образом:

    def sort1(lng, lst):
        if len(lst) != lng:
            return
        else:
            i = -2
            last = lst[-1]
            for x in lst:
                if last < lst[i]:
                    lst[i] = last
                    i -= 1
                    print(lst)
    sort1(6,[1,3,4,5,6,2])


It is giving me following result:
   [1, 3, 4, 5, 2, 2]
   [1, 3, 4, 2, 2, 2]
   [1, 3, 2, 2, 2, 2]
   [1, 2, 2, 2, 2, 2]

Answer 1

Вытащите элемент из списка и вставьте его обратно, используя bisect.insort_left:

>>> import bisect
>>> lst = [1, 3, 4, 5, 6, 2]
>>> item = lst.pop()
>>> bisect.insort_left(lst, item)
>>> lst
[1, 2, 3, 4, 5, 6]

Answer 2

Подходящим методом является алгоритм сортировки вставкой, но теперь мы делаем это только для последнего элемента, поэтому вот оно:

list = [1, 3, 4, 5, 6, 2] # our list
item = list[len(list)-1] # last element
i = len(list)-2 # the starting element to compare the last element to
while item<list[i] and i>=0: # while place not found and index in range
    list[i+1]=list[i] # move element at i to i+1
    i-=1 # decrement i, so to compare with next left element
list[i+1]=item # when the loop is completed, we then have our last item's position in i+1
print(list) # this prints [1, 2, 3, 4, 5, 6]

Вы можете прочитать больше об алгоритмах сортировки вставками, что немного сложно объяснить здесь, я имею в виду, что это требует длинного объяснения и примеров, так что вы можете увидеть больше в Википедии: https://en.wikipedia.org/wiki/Insertion_sort

Answer 3

Не так сексуально, как ответ @Ashwini, но вы можете попробовать это.

Вместо:

    lst[i] = last

(Который перезаписывает весь ваш массив последним значением, когда вы двигаетесь вниз)

Сделай это:

    lst[i+1] = lst[i]

(это сместит все значения)

Тогда после всех циклов:

    lst[i+1] = last

(Поместите последнее значение в правильное положение, где я +1 должен быть)

Answer 4

Если вам нужно написать свою собственную функцию, вы можете использовать enumerate и найти, где элемент находится между двумя значениями или он меньше или равен первому:

def sor1(lst):
    # empty or list with single ele or  last ele is larger than second last the list os sorted
    if len(lst) < 2 or lst[-1] > lst[-2]:
        return lst
    last = lst.pop()
    # if first value is larger than the last we need to insert last before the first
    if lst[0] >= last:
        lst.insert(0, last)
        return lst
    # else find first place where last falls between two values
    for ind, ele in enumerate(lst):
        if ele <= last <= lst[ind+1]:
            lst.insert(ind+1,last)
            return lst

Существует также библиотека Blist, где вставки 0(log n) и он превосходит некоторые другие операции со списком Python, в некоторых случаях также верно обратное, поэтому это будет зависеть от того, что вы хотите сделать:

from blist import blist
lst =  blist([1, 3, 4, 5, 6, 2])

Некоторые операции, в которых блист более эффективен, чем список:

• Вставка или удаление из списка O (log n) O (n)

• Вставка или удаление из списка O (log n) O (n)

• Взятие кусков списков O (log n) O (n)

• Создание мелких копий списков O(1) O(n)

• Изменение фрагментов списков O(log n + log k) O(n+k)

• Умножение списка для создания разреженного списка O (log k) O (kn)

• Поддерживать отсортированные списки с помощью bisect.insort O(log**2 n) O(n)

Он немного превосходит список, используя insort_left, используя python 2.7:

In [32]: %%timeit
lst = list(range(1000000))+[90000]
item = lst.pop()
bisect.insort_left(lst, item)
   ....: 
10 loops, best of 3: 38.5 ms per loop

In [33]: %%timeit
lst = blist(range(1000000))+blist([90000])
item = lst.pop()
bisect.insort_left(lst, item)
   ....: 
10 loops, best of 3: 27.9 ms per loop