1

我写的堆排序代码如下:

有趣的是

self.first, self.last = self.last, self.first 

不交换列表头部和尾部的两个值self.list

为什么?

#heapsort
import pdb
class heap(object):
    def __init__(self, list):
        super(heap, self).__init__()
        self.list = list
        self.heapify()
        if self.list:
            self.first = self.list[0]
            self.last = self.list[len(self.list)-1]
    def length(self):
        return len(self.list)
    def heap_node(self,i):
        large_i = i
        if 2*i+1<self.length() and self.list[2*i+1]>self.list[i]:
            large_i = 2*i+1
        if 2*i+2<self.length() and self.list[2*i+2]>self.list[large_i]:
            large_i = 2*i+2
        if large_i!=i:
            self.list[large_i], self.list[i] = self.list[i], self.list[large_i]
            self.heap_node(large_i)
    def heapify(self):
            for i in range(self.length()/2,0,-1):
                j=i-1
                self.heap_node(j)
    def sort(self):
        # pdb.set_trace()
        if not self.list:
            return []
        else:
            # self.list[0], self.list[len(self.list)-1] = self.list[len(self.list)-1], self.list[0]
            self.first, self.last = self.last, self.first 
            return heap(self.list[0:(self.length()-1)]).sort() + [self.list[len(self.list)-1]]

h=heap([1,3,2,5,4])
print h.list
print h.sort()
4

2 回答 2

3

self.firstself.last只是 和 中包含的数据的self.list[0]副本self.list[-1]。您需要直接分配给这些值:

self.data[0], self.data[-1] = self.data[-1], self.data[0]

使用负数组索引会导致 Python 从末尾查看列表。另外,我建议使用诸如data代替的名称list来减少隐藏内置名称的机会list

于 2012-06-30T19:07:03.067 回答
2

它应该是 self.list[0], self.list[-1] = self.list[-1], self.list[0]

self.first并且self.last只是包含 的第一个和最后一个值的变量self.list,更改它们不会改变self.list

于 2012-06-30T19:06:02.073 回答