0

私は次のヒープソートコードを記述しましたが、間違った出力（ソートされていない）が表示されることがありますが、その理由がわからないようです...どんな助けでも大歓迎です！

def heap_sort(self, a):

    heapsize = self.build_max_heap(a)

    n = len(a)-1
    i = len(a)-1

    for i in range(i, 0, -1):
        temp = a[0]
        a[0] = a[i]
        a[i] = temp
        heapsize = heapsize - 1
        self.max_heapify(heapsize, a, 0)       #rebuild max heap at with new root

    return a

def max_heapify(self, heapsize, a, i):

    left = (2*(i+1))-1      #left child of i
    right = 2*(i+1)             #right child of i
    largest = i

    if left < heapsize and a[left] > a[i]:
        largest = left

    if right < heapsize and a[right] > a[largest]:
        largest = right

    if largest != i:
        temp = a[largest]
        a[largest] = a[i]
        a[i] = temp
        self.max_heapify(heapsize, a, largest)

def build_max_heap(self, a):

    heapsize = len(a)
    i = int(heapsize/2)-1

    for i in range(i, 0):
        self.max_heapify(heapsize, a, i)

    return heapsize

私のテスト：

#--Test for 0 in array--#
def zero_array(self):
    a = [12,0,232]
    print self.sort.heap_sort(a)
    return

#--Test for duplicate in array--#
def duplicate_array(self):
    a = [12, 12, 7]
    print self.sort.heap_sort(a)
    return

#--Test for all same values in array--#
def allsame_array(self):
    a = [1,1,1]
    print self.sort.heap_sort(a)
    return

#--Test for negative values in array--#
def negative_array(self):
    a = [-23, -2, 123]
    print self.sort.heap_sort(a)
    return

出力（すべてソートされることになっています）：

    [0, 232, 12]
    [7, 12, 12]
    [1, 1, 1]
    [-2, 123, -23]
4

1 に答える 1

0

これは、2番目range()が後方ではなく前方に増分していることが原因である可能性があります。

for i in range(i, 0):

する必要があります：

for i in range(i, 0, -1):

range()また、2番目の引数の直前で停止するため、range(5, 0, -1)を返すことにも注意する必要があります[5, 4, 3, 2, 1]。

于 2012-10-15T18:59:18.580 に答える