计数法排序
- 适用于数值范围比较小的情形
- 时间复杂度为O(n k)
- 空间复杂度为O(k)
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
minNum = nums[0]
maxNum = nums[0]
for n in nums:
minNum = min(minNum, n)
maxNum = max(maxNum, n)
count = [0 for _ in range(maxNum - minNum 1)]
for n in nums:
count[n - minNum] = 1
res = []
for i, c in enumerate(count):
while c > 0:
res.append(minNum i)
c -= 1
return res快速排序
- 快排的时间复杂度为O(nlogn)，但如果中间值都位于数组的头部或者尾部，时间复杂度会退化为O(n**2)
import random
def swap(nums, a, b):
if a == b or nums[a] == nums[b]:
return
tmp = nums[a]
nums[a] = nums[b]
nums[b] = tmp
def partition(nums, start, end):
p = start - 1
q = start
r = random.randint(start, end) # 优化有序数组
swap(nums, r, end)
while q < end:
if nums[q] < nums[end]:
p = 1
swap(nums, p, q)
q = 1
p = 1
swap(nums, p, q)
return p
def quickSort(nums, start, end):
if (start < end):
i = partition(nums, start, end)
idx = i - 1
while start <= idx <= end and nums[idx] == nums[i]: # 优化多个相同数值相邻的情形
idx -= 1
quickSort(nums, start, idx)
idx = i 1
while start <= idx <= end and nums[idx] == nums[i]:
idx = 1
quickSort(nums, idx, end)
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
quickSort(nums, 0, len(nums) - 1)
return nums寻找第K大的数: https://leetcode.cn/problems/xx4gT2/
代码语言：javascript复制import random
def partition(nums, k, start, end):
r = random.randint(start, end)
nums[r], nums[end] = nums[end], nums[r]
p = start - 1
q = start
while q < end:
if nums[q] < nums[end]:
p = 1
nums[p], nums[q] = nums[q], nums[p]
q = 1
p = 1
nums[p], nums[q] = nums[q], nums[p]
return p
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
start = 0
end = n - 1
i = partition(nums, k, 0, end)
while i != n - k:
i = partition(nums, k, start, end)
if i < n - k:
start = i 1
else:
end = i - 1
return nums[i]归并排序
代码语言：javascript复制def merge(arrA, arrB):
lenA = len(arrA)
lenB = len(arrB)
res = []
idxA = 0
idxB = 0
while idxB < lenB and idxA < lenA:
if arrA[idxA] < arrB[idxB]:
res.append(arrA[idxA])
idxA = 1
else:
res.append(arrB[idxB])
idxB = 1
if idxA < lenA:
res.extend(arrA[idxA:])
else:
res.extend(arrB[idxB:])
return res
def mergeSort(arr, start, end):
if start == end:
return [arr[start]]
middle = (start end) // 2
top = mergeSort(arr, start, middle)
bottom = mergeSort(arr, middle 1, end)
return merge(top, bottom)
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
res = mergeSort(nums, 0, len(nums) - 1)
return res
