肥肥想说来练一下quick
然后怎么搞都过不了worst case
直接水桶伺候 操
后来想想我最该练的应该是merge sort
没写过几次
def sortArray(self, nums: List[int]) -> List[int]:
cnt = [0 for _ in range(100002)]
for n in nums:
cnt[n+50000] += 1
ans = []
for idx, val in enumerate(cnt):
for i in range(val):
ans.append(idx-50000)
return ans
# def middle_of_threerandom(l, r):
# pivot_index_0 = random.randint(l, r)
# pivot_index_1 = random.randint(l, r)
# pivot_index_2 = random.randint(l, r)
# tmp = sorted([(nums[pivot_index_0], pivot_index_0),
(nums[pivot_index_1], pivot_index_1), (nums[pivot_index_2], pivot_index_2)])
# return tmp[1][1]
# def qs(l,r):
# if l >= r:
# return
# pivot_idx = middle_of_threerandom(l,r)
# nums[r], nums[pivot_idx] = nums[pivot_idx], nums[r]
# pivot = nums[r]
# start = l
# for i in range(l, r):
# if nums[i] <= pivot:
# nums[start], nums[i] = nums[i], nums[start]
# start += 1
# nums[r], nums[start] = nums[start], nums[r]
# qs(l, start-1)
# qs(start+1, r)
# qs(0, len(nums)-1)
# return nums