题解 | #排序#
排序
https://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # 将给定数组排序 # @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