Python的sort

Tim Sort

1
2
3
4
5
6
7
8
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
return sorted(nums)[-k]

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
# 冒泡排序
def bubble_sort(nums):
for i in range(len(nums)-1, 0, -1):
# 一次外部迭代会确定一个最大数
count = 0
for j in range(i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
count += 1
# 如果没有一次交换,则说明已经有序
if count == 0:
break
return nums

快速排序

非原地排序

空间复杂度略高,刚才看到阮一峰的快排被怼了 😂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def quick_sort(self, nums):
if not nums:
return []
less = [num for num in nums[1:] if num <= nums[0]]
more = [num for num in nums[1:] if num > nums[0]]
return self.quick_sort(less) + [nums[0]] + self.quick_sort(more)
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
return self.quick_sort(nums)[-k]

原地排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quick_sort(nums, low, high):
if low < high:
key_index = partition(nums, low, high)
quick_sort(nums, low, key_index)
quick_sort(nums, key_index+1, high)
return nums
def partition(array, low, high):
key = array[low]
# 来回交换顺序
while low < high:
while low < high and array[high] >= key:
high -= 1
if low < high:
array[low] = array[high]
while low < high and array[low] < key:
low += 1
if low < high:
array[high] = array[low]
array[low] = key
return low

算法导论中的快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)
def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
# i记录的是上次比较大的元素
# 所以出现小元素之后,就会将小元素和大元素交换位置
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
# i+1就是当前切分元素,也就是i+1之前都是比x小的
# i+1之后就是比x大的
array[i + 1], array[r] = array[r], array[i + 1]
return i + 1

快排迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quick_sort(array, l, r):
if l >= r:
return
stack = []
stack.append(l)
stack.append(r)
while stack:
low = stack.pop(0)
high = stack.pop(0)
if high - low <= 0:
continue
x = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[high] = array[high], array[i + 1]
stack.extend([low, i, i + 2, high])

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge_sort(nums):
"""
归并排序
:param nums:
:return:
"""
# 切分数组
mid = len(nums) // 2
lft, rgt = nums[:mid], nums[mid:]
if len(lft) > 1:
lft = merge_sort(lft)
if len(rgt) > 1:
rgt = merge_sort(rgt)
res = []
# 归并的时候lft和rgt已经有序
while lft and rgt:
# 先由大到小append
if lft[-1] >= rgt[-1]:
res.append(lft.pop())
else:
res.append(rgt.pop())
res.reverse()
return (lft or rgt) + res

选取算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 选择第k大的元素
def select(nums, k):
pi, nums = nums[0], nums[1:]
lo = [num for num in nums if num <= pi]
hi = [num for num in nums if num > pi]
m = len(hi)
# m+1是因为pi是处于第k大
if m+1 == k:
return pi
elif m < k:
# 减1是因为要排除pi元素
return select(lo, k - m - 1)
else:
return select(hi, k)

插入排序

主要思想就是从开始进行排序,遇到小的插入到前面,不断的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 插入排序
def insert_sort(nums):
for i in range(1, len(nums)):
j = i
while j > 0 and nums[j] < nums[j-1]:
# 将元素向前挪
nums[j], nums[j-1] = nums[j-1], nums[j]
j -= 1
return nums
# 递归版插入排序
def insert_sort_rec(nums, i):
# 一直递归到最开始
if i == 0:
return
insert_sort_rec(nums, i-1)
j = i
while j > 0 and nums[j] < nums[j-1]:
nums[j], nums[j-1] = nums[j-1], nums[j]
j -= 1
return nums

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 选择排序
def select_sort(nums):
# 选择目前最大的数,放在右边,从右边向左边遍历
for i in range(len(nums)-1, 0, -1):
max_j = i
for j in range(i):
if nums[j] > nums[max_j]:
# 记录当前最大的数,随时更新max_j
max_j = j
# 最后得出就是整体最大的数
nums[i], nums[max_j] = nums[max_j], nums[i]
return nums
# 递归版选择排序
def select_sort_rec(nums, i):
if i == 0:
return
max_j = i
for j in range(i):
if nums[j] > nums[max_j]:
max_j = j
# 将最大数放在i的位置
nums[i], nums[max_j] = nums[max_j], nums[i]
# 递归去完成剩余的nums
select_sort_rec(nums, i-1)
return nums

堆排序

首先是使用 Python 的 heapq 包的实现

1
2
3
4
5
6
7
# 堆排序
def heap_sort(nums):
from heapq import heappush, heappop
h = []
for num in nums:
heappush(h, num)
return [heappop(h) for i in range(len(h))]

具体方法的实现

堆其实就是一棵树,root是最小或者最大元素,加入一个元素的时候将数据放在最后面,叶子节点,然后不断的根据大小将值往上浮动。从root取一个元素之后,会从当前heap最后一个元素拿到root,然后向下浮动,直到找到合适的位置。

所以关键算法在向上浮动和向下浮动

  • heappush
1
2
3
4
def heappush(heap, item):
"""Push item onto heap, maintaining the heap invariant."""
heap.append(item)
_siftdown(heap, 0, len(heap)-1)
  • heappop
1
2
3
4
5
6
7
8
9
def heappop(heap):
"""Pop the smallest item off the heap, maintaining the heap invariant."""
lastelt = heap.pop() # raises appropriate IndexError if heap is empty
if heap:
returnitem = heap[0]
heap[0] = lastelt
_siftup(heap, 0)
return returnitem
return lastelt
  • siftdown
1
2
3
4
5
6
7
8
9
10
11
12
13
def _siftdown(heap, startpos, pos):
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding a place
# newitem fits.
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if newitem < parent:
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
  • siftup
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def _siftup(heap, pos):
endpos = len(heap)
startpos = pos
newitem = heap[pos]
# Bubble up the smaller child until hitting a leaf.
childpos = 2*pos + 1 # leftmost child position
while childpos < endpos:
# Set childpos to index of smaller child.
rightpos = childpos + 1
if rightpos < endpos and not heap[childpos] < heap[rightpos]:
childpos = rightpos
# Move the smaller child up.
heap[pos] = heap[childpos]
pos = childpos
childpos = 2*pos + 1
# The leaf at pos is empty now. Put newitem there, and bubble it up
# to its final resting place (by sifting its parents down).
heap[pos] = newitem
_siftdown(heap, startpos, pos)

桶排序

347. Top K Frequent Elements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# 每个数字出现的次数
frequency = {}
for num in nums:
if num not in frequency:
frequency[num] = 1
else:
frequency[num] += 1
# 出现次数下所有的数字
bucket = {}
for key, value in frequency.items():
if value not in bucket:
bucket[value] = [key]
else:
bucket[value].append(key)
top_k = []
for key in sorted(bucket.keys(), reverse=True):
for ele in bucket[key]:
if len(top_k) >= k:
return top_k
top_k.append(ele)
return top_k

451. 根据字符出现频率排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
frequency = {}
for ele in s:
if ele in frequency:
frequency[ele] += 1
else:
frequency[ele] = 1
bucket = {}
for key, value in frequency.items():
bucket.setdefault(value, []).append(key)
ret = []
for key in sorted(bucket.keys(), reverse=True):
for item in bucket[key]:
ret.append(item*key)
return ''.join(ret)

三向切分快速排序

75. 分类颜色

思想就是判断并且交换,对于二分,一个游标记录上次的位置,另一个是遍历游标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
# 原地进行排序
# zero记录的是元素0的右边界
# two记录的是元素2的左边界
# one是遍历移动的指针
zero = -1
one = 0
two = len(nums)
while one < two:
if nums[one] == 0:
# 跟前面的换, 而且要交换的元素要么是0,要么是1,所以one要自增一次
zero += 1
nums[zero], nums[one] = nums[one], nums[zero]
one += 1
elif nums[one] == 2:
# 跟后面的换,交换过来的元素可能0,1,2,所以one不能自增
two -= 1
nums[two], nums[one] = nums[one], nums[two]
else:
# 遇到1则需要自增一次
one += 1