前幾天就寫merge
想說今天寫一下quick
ㄇㄉ真的TLE==
來玩radix好了
※ 引述《sustainer123 (caster)》之銘言：
: ※ 引述《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