def quiksort(nums, start, end):
    def partition(low, high):
        pivot, j = nums[low], low
        for i in range(low+1, high+1):
            if nums[i] < pivot:
                j += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[low], nums[j] = nums[j], nums[low]
        return j
    if start < end:
        m = partition(start, end)
        quiksort(nums, start, m-1)
        quiksort(nums, m+1, end)


if __name__ == '__main__':
    nums = [1, 2, 7, 5, 7, 4]
    quiksort(nums, 0, len(nums)-1)
    print(nums)

class Heap():

    def __init__(self, capacity, data):
        self.data = data
        self.capacity = capacity

    @classmethod
    def buildheap(cls, nums):
        '''
        将nums数组生成一个最大堆
        '''
        n = len(nums)
        for i in range((n - 2) // 2, -1, -1):
            cls.heapify(nums, n, i)
        return nums

    @classmethod
    def heapify(cls, n, i):
        '''
        nums: 待堆化的数据
        n: 堆化前n个数
        i：堆化 index = i 的数
        '''

        while True:
            max_pos = i
            if i * 2 + 1 <= n - 1 and nums[max_pos] < nums[i * 2 + 1]:
                max_pos = i * 2 + 1
            if i * 2 + 2 <= n - 1 and nums[max_pos] < nums[i * 2 + 2]:
                max_pos = i * 2 + 2
            if max_pos == i:
                break
            nums[i], nums[max_pos] = nums[max_pos], nums[i] # IMPORTANT
            i = max_pos

    @classmethod
    def sort(cls, nums):
        n = len(nums)
        cls.buildheap(nums)
        k = n # 需要堆化数据的长度，而非 index
        nums[k - 1], nums[0] = nums[0], nums[k - 1]
        while k > 1:
            k -= 1
            cls.heapify(k, 0)
            nums[k - 1], nums[0] = nums[0], nums[k - 1]

nums = [1, 0, 5, 9, 4, 2, 3]
Heap.sort(nums)
print(nums)

print('=' * 30)
nums = [1, 3, 5, 9, 4, 2, 0]
Heap.sort(nums)
print(nums)