题解 | #排序#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        def heap_sort(arr: List[int]):
            n = len(arr)
            for i in range(n // 2 - 1, -1, -1):#构建大根堆
                heapify(arr, i, n - 1)
            for i in range(n - 1, 0, -1): #得到排序后的数组，每次从堆顶拿到最大值放到最后
                arr[0], arr[i] = arr[i], arr[0]
                heapify(arr, 0, i - 1)

        def heapify(arr: List[int], root: int, ed: int):
            while True:
                child = root * 2 + 1
                if child > ed: break
                if child + 1 <= ed and arr[child + 1] > arr[child]:
                    child += 1
                if arr[child] > arr[root]:
                    arr[child], arr[root] = arr[root], arr[child]
                    root = child
                else:
                    break
        heap_sort(arr)
        return arr

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        def quick_sort(arr: List[int], low: int, high: int):
            if high <= low: return
            idx = partition(arr, low, high)
            quick_sort(arr, low, idx - 1)
            quick_sort(arr, idx + 1, high)
        def partition(arr: List[int], low: int, high: int) -> int:
            p = arr[low]
            bg, ed = low + 1, high
            while bg <= ed:
                while bg <= ed and arr[bg] <= p:
                    bg += 1
                while bg <= ed and arr[ed] >= p:
                    ed -= 1
                if bg < ed:
                    arr[bg], arr[ed] = arr[ed], arr[bg]
            arr[low], arr[ed] = arr[ed], arr[low]
            return ed
        quick_sort(arr, 0, len(arr) - 1)
        return arr