912. Sort an Array
https://leetcode.com/problems/sort-an-array/
solution
插入排序: 算法导论中的扑克牌插入，相邻比较
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
if len(nums) <= 1:
return nums
for i in range(1, len(nums)):
j = i
while j > 0 and nums[j] < nums[j-1]: # 倒序
nums[j-1], nums[j] = nums[j], nums[j-1]
j -= 1
return nums时间复杂度：O(n^2) 空间复杂度：O(n)
递归写法
def insert_sort_rec(list, m):
if m == 0:
return
mmax = m
for i in range(m):
if list[i] > list[mmax]:
mmax = i
list[m], list[mmax] = list[mmax], list[m]
insert_sort_rec(list, m - 1)冒泡排序: 两层for循环，相邻比较
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
for j in range(len(nums) - i - 1): # 这里注意
if nums[j] > nums[j+1]:
nums[j+1], nums[j] = nums[j], nums[j+1]
return nums时间复杂度：O(n^2) 空间复杂度：O(n)
归并排序
树的后序遍历
divide & conquer: top down & bottom up
排序的稳定性问题
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
l = 0
r = len(nums) - 1
self.merge_sort(nums, l, r)
return nums
def merge_sort(self, nums, l, r):
if l < r: # 注意是if
mid = l + (r - l) // 2
self.merge_sort(nums, l, mid)
self.merge_sort(nums, mid+1, r)
self.merge(nums, l, mid, r)
def merge(self, nums, l, mid, r):
pass时间复杂度：O(nlog(n)) 空间复杂度：O(n)
def merge(lista, listb):
output = []
i, j = 0, 0
while i < len(lista) and j < len(listb):
if lista[i] > listb[j]:
output.append(listb[j])
j += 1
else:
output.append(lista[i])
i += 1
if i < len(lista):
output += lista[i:]
if j < len(listb):
output += listb[j:]
return output
def merge_sort(list):
if len(list) <= 1:
return list
mid = len(list)//2
return merge(merge_sort(list[:mid]), merge_sort(list[mid:]))
print(merge_sort([5,1,2,4,6,3]))快速排序
树的前序遍历
average O(nlog(n)) 最好O(1) 最差O(n^2)
注意左闭右开/左闭右闭的统一
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
l = 0
r = len(nums) - 1
self.quick_sort(nums, l, r)
return nums
def quick_sort(self, nums, l, r):
if l < r: # 注意这里是if, 不是while
p = self.partition(nums, l , r)
self.quick_sort(nums, l, p - 1)
self.quick_sort(nums, p + 1, r)
def partition(self, nums, l, r):
pivot = nums[r]
i = l # 第一个比pivot大的位置
for j in range(l, r):
if nums[j] <= pivot: # 比较之后, 互换该位置和i位置的值
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[r] = nums[r], nums[i]
return i时间复杂度：average O(nlog(n)) 最好O(1) 最差O(n^2) 空间复杂度：O(n)
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quick_sort(nums):
if len(nums) <= 1:
return nums
left, equal, right = [], [], []
pivot = random.choice(nums)
for i in range(len(nums)):
if nums[i] < pivot:
left.append(nums[i])
elif nums[i] > pivot:
right.append(nums[i])
else:
equal.append(nums[i])
return quick_sort(left) + equal + quick_sort(right)
return quick_sort(nums)def partition(list, l, r):
# 在list中[p, r]区间返回*位置*i，左边都小于list[i]，右边都大于list[i]
key = list[r] # 最后一个作为pivot
i = l # 分隔小于和大于key的位置, 也就是j循环之前第一个大于key的位置
for j in range(l, r):
if list[j] <= key:
list[i], list[j] = list[j], list[i]
i = i + 1
list[i], list[r] = list[r], list[i]
return i
def quick_sort_op(list, l, r):
if l < r:
q = partition(list, l, r)
quick_sort_op(list, l, q - 1)
quick_sort_op(list, q + 1, r)
list = [5, 2, 1, 4, 6, 3]
quick_sort_op(list, 0, len(list)-1)
print(list)堆排序
# https://stackoverflow.com/questions/13979714/heap-sort-how-to-sort
def max_heapify(list, end, i):
l = 2 * i + 1
r = 2 * (i + 1)
max = i
if l < end and list[i] < list[l]:
max = l
if r < end and list[max] < list[r]:
max = r
if max != i:
list[i], list[max] = list[max], list[i]
max_heapify(list, end, max)
def heap_sort(list):
end = len(list)
start = end // 2 + 1
for i in range(start, -1, -1):
max_heapify(list, end, i)
for i in range(end-1, 0, -1):
list[i], list[0] = list[0], list[i]
max_heapify(list, i, 0)
list = [2, 7, 1, -2, 56, 5, 3]
heap_sort(list)
print(list)时间复杂度：O(nlog(n)) 空间复杂度：O(n)
桶排序
为每个值设立一个桶，桶内记录这个值出现的次数或其它属性，然后对桶进行排序
时间复杂度：O() 空间复杂度：O()
计数排序
follow up
class Solution:
def customSortString(self, order: str, s: str) -> str:
order_dict = {char: i for i, char in enumerate(order)}
s = sorted(s, key=lambda x: order_dict.get(x, 0)) # x.sort() 只支持list?
return "".join(s) # sort生成之后生成的是listclass Solution:
def customSortString(self, order: str, s: str) -> str:
res = ""
counter = collections.defaultdict(int)
for char in s:
counter[char] += 1
for char in order:
if char in counter:
res += char * counter[char]
del counter[char]
# 剩余字母
for char, count in counter.items():
res += char * count
return resclass Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
prev = dummy
while head:
nex = head.next
if prev.val >= head.val: # 如果prev本身已经比head大, 不必回到最前面。给head找的位置本身就是第一个比head大的位置
prev = dummy
while prev.next and prev.next.val < head.val:
prev = prev.next
head.next = prev.next # 在prev和prev.next中插入head
prev.next = head
head = nex
return dummy.nextLast updated