2

我正在尝试实现三元堆排序，堆的每个父级都有 3 个子级，但是我无法让我的代码返回排序列表。我想我可能在某处犯了一个逻辑错误但无法发现它，任何修复此代码的帮助将不胜感激。

def swap(i, j):
    sqc[i], sqc[j] = sqc[j], sqc[i]

def heapify(end,i):
    l=3 * (i + 1)
    m=3 * (i + 2)
    r=3 * (i + 3)
    max=i
    if l < end and sqc[i] < sqc[l]:
        max = l
    if r < end and sqc[max] < sqc[r]:
        max = r
    if m < end and sqc[max] < sqc[m]:
        max = m
    if max != i:
        swap(i, max)
        heapify(end, max)

def heap_sort():
    end = len(sqc)
    start = end / 2 - 1
    for i in range(start, -1, -1):
        heapify(end, i)
    for i in range(end-1, 0, -1):
        swap(i, 0)
        heapify(i, 0)

sqc = [2, 7, 1, -2, 56, 5, 3]
heap_sort()
print(sqc)

[7, 1, -2, 56, 5, 2, 3]是返回的，完全乱序。

4

2 回答 2

1

代码

def heapSort3(a):
    def sift(start, count):
        root = start
        while root * 3 + 1 < count:
            r3 = root * 3
            upper = min(count - r3, 4)
            children = list(range(r3 + 1, r3 + upper))
            min_child = min((a[i], i) for i in children)
            v, i = min_child
            if a[root] > a[i]:
                a[root], a[i] = a[i], a[root]
                root = i
            else:
                break
    count = len(a)
    for start in reversed(range(count // 3 + 2)):
        sift(start, count)
    for end in reversed(range(count)):
        a[end], a[0] = a[0], a[end]
        sift(0, end)
    return a

测试排序和反向排序

for i in range(2, 25):
    print '-' * 30
    data = list(range(i))
    sorted_data = heapSort3(data)
    print i, sorted_data
    data = list(reversed(range(i)))
    sorted_data = heapSort3(data)
    print i, sorted_data

对混洗数据进行测试

from random import shuffle
for i in range(1, 100):
    print '-' * 30, i
    expected = list(reversed(range(i)))
    for _ in range(5000):
        data = list(range(i))
        shuffle(data)
        sorted_data = heapSort3(data)
        assert sorted_data == expected

参考

改编自此代码。有点。

于 2013-03-27T04:25:23.583 回答
0

这是一个仅纠正您的heapify功能的解决方案：

def swap(series, i, j):
    series[i], series[j] = series[j], series[i]

def heapify(series, end, i):
    firstchild = 3*i + 1
    lastchild = min(firstchild + 3, end)
    children = list(range(firstchild, lastchild))
    maxelem = max((series[j], j) for j in [i] + children)
    maxval, maxindex = maxelem
    if maxindex != i:
        swap(series, i, maxindex)
        heapify(series, end, maxindex)

def heap_sort(series):
    end = len(series)
    start = end / 2 - 1
    for i in range(start, -1, -1):
        heapify(series, end, i)
    for i in range(end-1, 0, -1):
        swap(series, i, 0)
        heapify(series, i, 0)
    return series

堆排序变化

您也可以将heapsort代码更改为此，但这不是必需的：

def heap_sort(series):
    end = len(series)
    start = end // 2
    for i in reversed(range(start)):
        heapify(series, end, i)
    for i in reversed(range(end)):
        swap(series, i, 0)
        heapify(series, i, 0)
    return series

测试您的数据

>>> sqc = [2, 7, 1, -2, 56, 5, 3]
>>> print heap_sort(sqc)
[-2, 1, 2, 3, 5, 7, 56]

测试随机打乱的数据

from random import shuffle
for i in range(1, 100):
    print '-' * 30, i
    expected = list(range(i))
    for _ in range(5000):
        data = list(range(i))
        shuffle(data)
        sorted_data = heap_sort(data)
        assert sorted_data == expected
于 2013-03-27T14:42:10.820 回答