以升序顺序将元素添加到排序数组中

Question

我有下面的程序来实现一个分类包。它添加了元素 在给出列表时成功地按排序（升序）排序。 当我用另一个包的参数创建一个新的已排序包时，它不是按排序顺序（而是按降序排列）。见下文

谢谢你的帮助

# Array Class
#----------------------------------------------------
class Array(object):        # Represents an array.
DEFAULT_CAPACITY = 5
def __init__ (self, capacity, fillValue = None):
'''Capacity = static size of array. fillValue is placed at each element'''
    self._items = list()
    self._capacity = capacity
    self._logicalSize = 0
    self._fillValue = fillValue
    for count in range(capacity):
        self._items.append(fillValue)

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

def __setitem__(self, index, newItem):      
    self._items[index] = newItem

# ArraySortedBag Class
#----------------------------------------------------
class ArraySortedBag(object):
'''An array-based bag implementation'''
def __init__(self, sourceCollection = None):
    '''Sets the initial state of self, which includes the contents
    of sourceCollection, if it's present'''
    self._items = Array(10)
    self._size  = 0
    if sourceCollection:
        for item in sourceCollection:
            self.add(item)

def __len__(self): return self._size

def __iter__(self):
    cursor = 0
    while cursor < len(self):
        yield self._items[cursor]
        cursor += 1

def add(self, item):
    '''Adds item to self.'''        
    insertIndex = 0

    # First found the index where the item will be inserted at
    for i in range(self._size):
        if self._items[i] > item:
            insertIndex = i
            break
    # Then, shift items down by one position until the insertIndex,
    for i in range (self._size, insertIndex, -1):
        self._items[i] = self._items[i-1]

    # Last, assign value to _items[insertIndex]
    self._items[insertIndex] = item
    self._size += 1

# Test Driver
#----------------------------------------------------
if __name__ == "__main__":
b1 = ArraySortedBag([2000, 2, 1000])
print ("Display bag b1")
for i in b1:              # <------ Correct order, ascending order
    print (i)

b2 = ArraySortedBag(b1)
print ("\nDisplay bag b2")
for i in b2:                 # <----- Wrong order, descending order
    print (i)

Answer 1

为了将项添加到已排序的列表中，以便维护列表的排序，我建议使用bisect library'sinsort_left或insort_right。在

import bisect

list = [10, 20, 30]

bisect.insort(list, 25)
bisect.insort(list, 15)

print list

Answer 2

在ArraySortedBag类的第二个实例化中，传递的是一个已排序的列表。ArraySortedBag.init（）方法使用add（）方法添加项。调用add（）时，要添加的项永远不会少于现有列表。因此，insertIndex仍然等于零。因此，新项被添加到列表的开头。在

# First found the index where the item will be inserted at
for i in range(self._size):
    if self._items[i] > item:     # item is never less than self._items[i]
        insertIndex = i
        break