※ 引述《DJYOMIYAHINA (通通打死)》之銘言：
: 肥肥想說來練一下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
思路:
本來想說quick sort
結果翻一下書才發現quick sort最糟狀況會n**2
能用的就heap sort跟merge sort
剛好複習一下排序
不然平常都sort() 啟動
Python Code:
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def merge(left: int,mid: int,right: int):
tmp = [0] *((right - left) + 1)
i,j,k = left, mid + 1, 0
while i <= mid and j <= right:
if nums[i] <= nums[j]:
tmp[k] = nums[i]
i += 1
else:
tmp[k] = nums[j]
j += 1
k += 1
while i <= mid:
tmp[k] = nums[i]
i += 1
k += 1
while j <= right:
tmp[k] = nums[j]
j += 1
k += 1
for k in range(len(tmp)):
nums[left+k] = tmp[k]
def merge_sort(nums: list[int],left: int,right: int):
if left >= right:
return
mid = (left + right) // 2
merge_sort(nums,left,mid)
merge_sort(nums,mid+1,right)
merge(left,mid,right)
merge_sort(nums,0,len(nums)-1)
return nums