时间戳

首页 > 解决方案 > 迭代就地子列表堆排序python实现

python - 迭代就地子列表堆排序python实现

问题描述

我为 python 找到了不同版本的堆排序，但我似乎找不到符合我需要的那个。

迭代堆排序是我发现的最接近的，但我无法完全弄清楚如何将其更改为与子列表（索引开始，索引结束）一起使用并保持原位。

如果我做对了，那么我会在这里发布我的答案。

如果有人甚至在 C 或 Java 中都有实现，那就太好了。

标签： pythoniterationsublistheapsortsub-array

解决方案

我设法做我想做的事。此代码适用于对象并按特定属性排序。

def buildMaxHeap(arr, arrayLength, indexStart, attr):
    for i in range(arrayLength):

        # if child is bigger than parent
        if getattr(arr[indexStart + i], attr) > getattr(arr[indexStart + int((i - 1) / 2)], attr):
            j = i

            # swap child and parent until
            # parent is smaller
            while getattr(arr[indexStart + j], attr) > getattr(arr[indexStart + int((j - 1) / 2)], attr):
                (arr[indexStart + j],
                 arr[indexStart + int((j - 1) / 2)]) = (arr[indexStart + int((j - 1) / 2)], arr[indexStart + j])
                j = int((j - 1) / 2)


def heapSort(arr, arrayLength, indexStart, attr):
    buildMaxHeap(arr, arrayLength, indexStart, attr)

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

        # swap value of first indexed
        # with last indexed
        arr[indexStart + 0], arr[indexStart + i] = arr[indexStart + i], arr[indexStart + 0]

        # maintaining heap property
        # after each swapping
        j, index = 0, 0

        while True:
            index = 2 * j + 1

            # if left child is smaller than
            # right child point index variable
            # to right child
            if (index < (i - 1) and getattr(arr[indexStart + index], attr) < getattr(arr[indexStart + index + 1], attr)):
                index += 1

            # if parent is smaller than child
            # then swapping parent with child
            # having higher value
            if index < i and getattr(arr[indexStart + j], attr) < getattr(arr[indexStart + index], attr):
                arr[indexStart + j], arr[indexStart + index] = arr[indexStart + index], arr[indexStart + j]

            j = index
            if index >= i:
                break

推荐阅读