堆排序的原理是很好理解的，但是如果让你手撕堆排序，你能解决吗？
代码如下，测试通过。排序数组
1 | class heapSort: |
2 | def __init__(self): |
3 | pass |
4 | |
5 | def heapify(self, arr, i): |
6 | """把最大元素推到堆顶""" |
7 | left, right = 2 * i + 1, 2 * i + 2 |
8 | largest = i |
9 | if left < arr_len and arr[left] > arr[largest]: |
10 | largest = left |
11 | if right < arr_len and arr[right] > arr[largest]: |
12 | largest = right |
13 | |
14 | if largest != i: |
15 | # 最大元素推到堆顶，同时向下调整继续保持为大顶堆 |
16 | arr[largest], arr[i] = arr[i], arr[largest] |
17 | self.heapify(arr, largest) |
18 | |
19 | def build_max_heap(self, arr): |
20 | """建大顶堆堆, 调用 heapify()""" |
21 | |
22 | for i in range(len(arr) // 2, -1, -1): |
23 | self.heapify(arr, i) |
24 | |
25 | def heap_sort(self, arr): |
26 | """堆排序""" |
27 | global arr_len |
28 | arr_len = len(arr) |
29 | self.build_max_heap(arr) |
30 | for i in range(arr_len - 1, 0, -1): |
31 | arr[0], arr[i] = arr[i], arr[0] |
32 | arr_len -= 1 |
33 | self.heapify(arr, 0) |
34 | |
35 | return arr |
36 | |
37 | class Solution: |
38 | def sortArray(self, nums: List[int]) -> List[int]: |
39 | return heapSort().heap_sort(nums) |