912. Sort an Array
## 思路
Counting Sort - O(N)
merge sort / heap sort - O(N logN)
## Code
Counting Sort
```python
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
bucket = [0] * 100001
for num in nums:
bucket[num+50000] += 1
ans = []
for i in range(100001):
if bucket[i]:
ans += [i-50000] * bucket[i]
return ans
```
Merge Sort
```python
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
temp = [0] * len(nums)
def merge_sort(left, right):
if left >= right:
return
mid = (left + right) // 2
merge_sort(left, mid)
merge_sort(mid+1, right)
merge(left, mid, right)
def merge(left, mid, right):
# arr1 = nums[left:mid+1]
# arr2 = nums[mid+1:right+1]
n1 = mid - left + 1
n2 = right - mid
for i in range(left, mid+1):
temp[i] = nums[i]
for i in range(mid+1, right+1):
temp[i] = nums[i]
p1, p2, k = left, mid+1, left
while p1 <= mid and p2 <= right:
if temp[p1] <= temp[p2]:
nums[k] = temp[p1]
p1 += 1
else:
nums[k] = temp[p2]
p2 += 1
k += 1
while p1 <= mid:
nums[k] = temp[p1]
k += 1
p1 += 1
while p2 <= right:
nums[k] = temp[p2]
k += 1
p2 += 1
merge_sort(0, len(nums)-1)
return nums
```
Heap Sort
```python
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def max_heapify(heap_size, index):
left = 2 * index + 1
right = 2 * index + 2
largest = index
if left < heap_size and nums[left] > nums[largest]:
largest = left
if right < heap_size and nums[right] > nums[largest]:
largest = right
if largest != index:
nums[index], nums[largest] = nums[largest], nums[index]
max_heapify(heap_size, largest)
def heap_sort():
n = len(nums)
# build head (top-down)
for i in range(n//2 -1, -1, -1):
max_heapify(n, i)
for i in range(n - 1, 0, -1):
nums[i], nums[0] = nums[0], nums[i]
max_heapify(i, 0)
heap_sort()
return nums
```
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.146 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721878252.A.BBD.html