在 Python 中将项插入到排序列表中

我正在创建一个类，其中一个方法将一个新项插入到已排序的列表中。该项插入到已排序列表中已更正的(已排序的)位置。但是，除了 []、 [:]、 +和 len之外，我不允许使用任何内置的列表函数或方法。这部分让我很困惑。

这件事最好的办法是什么？

173978 次浏览
小开

提示1: 您可能希望研究 对分模中的 Python 代码。

提示2: 切片可用于插入列表:

>>> s = ['a', 'b', 'd', 'e']
>>> s[2:2] = ['c']
>>> s
['a', 'b', 'c', 'd', 'e']
小开

这是一个可能的解决方案:

a = [15, 12, 10]
b = sorted(a)
print b # --> b = [10, 12, 15]
c = 13
for i in range(len(b)):
if b[i] > c:
break
d = b[:i] + [c] + b[i:]
print d # --> d = [10, 12, 13, 15]
小开

使用 平分模块的 insort功能:

import bisect
a = [1, 2, 4, 5]
bisect.insort(a, 3)
print(a)

输出

[1, 2, 3, 4, 5]
小开

您应该使用 bisect 模块，而且，在使用 bisect.insort _ left 之前，需要对列表进行排序

区别可大了。

>>> l = [0, 2, 4, 5, 9]
>>> bisect.insort_left(l,8)
>>> l
[0, 2, 4, 5, 8, 9]


timeit.timeit("l.append(8); l = sorted(l)",setup="l = [4,2,0,9,5]; import bisect; l = sorted(l)",number=10000)
1.2235019207000732


timeit.timeit("bisect.insort_left(l,8)",setup="l = [4,2,0,9,5]; import bisect; l=sorted(l)",number=10000)
0.041441917419433594
小开

这是将列表和插入值追加到排序列表的最佳方法:

 a = [] num = int(input('How many numbers: ')) for n in range(num):
numbers = int(input('Enter values:'))
a.append(numbers)


b = sorted(a) print(b) c = int(input("enter value:")) for i in
range(len(b)):
if b[i] > c:
index = i
break d = b[:i] + [c] + b[i:] print(d)`
小开

我现在正在学习算法，所以我想知道对分模块是如何写的。 下面是关于将项目插入到排序列表的二分模块的代码，它使用了二分法:

def insort_right(a, x, lo=0, hi=None):
"""Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the right of the rightmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""


if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x < a[mid]:
hi = mid
else:
lo = mid+1
a.insert(lo, x)
小开 
# function to insert a number in an sorted list




def pstatement(value_returned):
return print('new sorted list =', value_returned)




def insert(input, n):
print('input list = ', input)
print('number to insert = ', n)
print('range to iterate is =', len(input))


first = input[0]
print('first element =', first)
last = input[-1]
print('last element =', last)


if first > n:
list = [n] + input[:]
return pstatement(list)
elif last < n:
list = input[:] + [n]
return pstatement(list)
else:
for i in range(len(input)):
if input[i] > n:
break
list = input[:i] + [n] + input[i:]
return pstatement(list)


# Input values
listq = [2, 4, 5]
n = 1


insert(listq, n)
小开

有很多方法可以做到这一点，这里有一个简单的初学者程序使用内置的 Python 函数 sort ()来做同样的事情

def sorted_inserter():
list_in = []
n1 = int(input("How many items in the list : "))


for i in range (n1):
e1 = int(input("Enter numbers in list : "))
list_in.append(e1)
print("The input list is : ",list_in)




print("Any more items to be inserted ?")
n2 = int(input("How many more numbers to be added ? : "))
for j in range (n2):
e2= int(input("Add more numbers : "))
list_in.append(e2)
list_sorted=sorted(list_in)
print("The sorted list is: ",list_sorted)
    



sorted_inserter()

输出是

清单上有多少项: 4项

在列表中输入数字: 1

在列表中输入数字: 2

在列表中输入数字: 123

在列表中输入数字: 523

输入列表是: [1,2,123,523]

还有其他要插入的项目吗？

还要加多少个数字? : 1

加入更多数字: 9

排序后的列表是: [1,2,9,123,523]

小开

如果没有人为的限制，应该使用 bisect.insort()作为 由 stanga描述。然而，正如 Velda在评论中提到的，大多数现实世界中的问题不仅仅是对纯数字排序。

幸运的是，正如 drakenation所述，解决方案 适用于任何可比对象:

from bisect import insort


@dataclass
class Person:
first_name: str
last_name: str
age: int


def __lt__(self, other):
return self.age < other.age


persons = []


insort(persons, Person('John', 'Doe', 30))
insort(persons, Person('Jane', 'Doe', 28))
insort(persons, Person('Santa', 'Claus', 1750))


# [Person(first_name='Jane', last_name='Doe', age=28), Person(first_name='John', last_name='Doe', age=30), Person(first_name='Santa', last_name='Claus', age=1750)]

然而，在元组的情况下，最好使用任意键进行排序。默认情况下，元组按照它们的第一个项目(名)排序，然后按照下一个项目(姓)排序，依此类推。

作为一个解决方案，你可以 管理额外的键列表:

from bisect import bisect


persons = []
ages = []


def insert_person(person):
age = person[2]
i = bisect(ages, age)
persons.insert(i, person)
ages.insert(i, age)
    

insert_person(('John', 'Doe', 30))
insert_person(('Jane', 'Doe', 28))
insert_person(('Santa', 'Claus', 1750))

官方解决方案 : 文件指的是 < strong > 菜谱 如何在 定制类 SortedCollection中使用函数来实现这个功能，以便可以按照以下方式使用:

>>> s = SortedCollection(key=itemgetter(2))
>>> for record in [
...         ('roger', 'young', 30),
...         ('angela', 'jones', 28),
...         ('bill', 'smith', 22),
...         ('david', 'thomas', 32)]:
...     s.insert(record)


>>> pprint(list(s))         # show records sorted by age
[('bill', 'smith', 22),
('angela', 'jones', 28),
('roger', 'young', 30),
('david', 'thomas', 32)]

下面是使示例工作所需的类的相关摘录。基本上，SortedCollection 管理附加的键列表与项目列表并行，找出在哪里插入新的元组(及其键)。

from bisect import bisect_left


class SortedCollection(object):


def __init__(self, iterable=(), key=None):
self._given_key = key
key = (lambda x: x) if key is None else key
decorated = sorted((key(item), item) for item in iterable)
self._keys = [k for k, item in decorated]
self._items = [item for k, item in decorated]
self._key = key
        

def __getitem__(self, i):
return self._items[i]


def __iter__(self):
return iter(self._items)
        

def insert(self, item):
'Insert a new item.  If equal keys are found, add to the left'
k = self._key(item)
i = bisect_left(self._keys, k)
self._keys.insert(i, k)
self._items.insert(i, item)

注意，list.insert()和 bisect.insort()都具有 O (n)复杂性。因此，正如 nz_21所评论的那样，手动遍历排序的列表，寻找正确的位置，从复杂性的角度来说也是一样好的。实际上，在插入新值之后对数组进行简单的排序也可以，因为 Python 的 Timsort 的最坏情况复杂度为 O (n log (n))。但是，为了完整起见，请注意，二叉查找树(BST)允许在 o (log (n))时间内进行插入。


提交答案