讨论/《排序算法全解析》 - 解析/
《排序算法全解析》 - 解析
共 3 个回复

一上来搞错了位运算 哭。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.heap_sort(nums)

    def heap_sort(self, nums:List[int]) -> List[int]:
        def exchange(nums: List[int], i: int, j: int):
            nums[i], nums[j] = nums[j], nums[i]

        def max_heapify(nums:List[int], i: int, heap_size: int):
            max_index = i
            l_index, r_index = (i << 1) + 1, (i << 1) + 2
            if l_index < heap_size and nums[l_index] > nums[max_index]:
                max_index = l_index
            if r_index < heap_size and nums[r_index] > nums[max_index]:
                max_index = r_index
            if max_index != i:
                exchange(nums, max_index, i)
                max_heapify(nums, max_index, heap_size)
        
        n = len(nums)
        end = (n >> 1) - 1
        #  initialize nums to be a max_heap
        for i in range(end, -1, -1):
            max_heapify(nums, i, n)
        # sort store in the tail
        for i in range(n-1, 0, -1):
            exchange(nums, 0, i) # pop max push to tail
            max_heapify(nums, 0, i)
        return nums

python实现,但个人感觉比这个解析的结构要干净一点,其实是一个东西:

class Solution:
    def heapify(self,arr,n,i):
        """
        让普通序列arr,变成heap的结构
        n = 有多少个节点
        i = 对i位置node做heapify
        """
        if i>= n: return

        left = 2*i+1
        right= 2*i+2
        max_idx = i
        # 在 n 内才满足条件
        if left < n and arr[left] > arr[max_idx]:
            max_idx = left
        if right < n and arr[right]> arr[max_idx]:
            max_idx = right
        # 如果 max_idx 和 i 不相同了,需要做交换
        if max_idx != i:
            arr[max_idx],arr[i] = arr[i],arr[max_idx]
            # 继续计算已经改变以 node 为根的子树
            self.heapify(arr,n,max_idx)
        
    def heapSort(self,nums):
        """
        两部分:
        1. 构建heap
        2. 根据heap排序
        """
        # 获得数组长度
        n = len(nums)
        # ------- 构建heap ------
        # 从后往前构建堆
        # 确保最大的数字最后会跑到root位置(idx=0)
        last_idx = n-1
        # 找到从后往前最近的父node
        parent = (last_idx-1)//2
        # 找到在此之前每一个node,做heapify
        for i in range(parent,-1,-1):
            self.heapify(nums,n,i)

        # ----- 根据heap排序 -----
        for i in range(n-1,0,-1):
            # 大顶堆的根,放在最后一个
            nums[i] , nums[0] = nums[0], nums[i]
            # 因为最大的数字已经被放在了尾巴(idx=i)
            # 再做heapify就不用考虑它了。
            # 所以i对应的是需要heapify的长度,会逐步缩小
            self.heapify(nums,i,0)

    def sortArray(self, nums: List[int]) -> List[int]:
        # 下面是入口哦
        self.heapSort(nums)
        return nums

这个堆排写的真是丑死我了。。。
给个参考https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F