讨论/《排序算法全解析》 - 解析/
《排序算法全解析》 - 解析

一上来搞错了位运算 哭。

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
展开全部 3 讨论