快排
O(N *logN)
k
[1,2,3,4,5, 6,7,8,9,10]
k.left <= last k.right > last
快排主要是, 选择一个比较值(比如说last), 找到分割点k，保证k左边<=last, k右边>last
def quick_sort(arrs):
def __partiion(arrs, start, end):
last = arrs[end - 1]
k = start
for i in range(k, end - 1):
if arrs[i] <= last:
arrs[k], arrs[i] = arrs[i], arrs[k]
k += 1
arrs[k], arrs[end - 1] = arrs[end - 1], arrs[k]
return k
def __quick_sort(arrs, start, end):
if end - start <= 1:
return
k = __partiion(arrs, start, end)
__quick_sort(arrs, start, k)
__quick_sort(arrs, k, end)
__quick_sort(arrs, 0, len(arrs))
归并排序
O(N * logN)
分治思想, 将问题一步步切割，分到1个的时候就不用排序了，然后把各个结果都合并起来
def merge_sort(arrs):
def __merge(arrs, start, mid, end):
L = arrs[start: mid] # left sub problem, this is a copy
R = arrs[mid: end] # right sub problem, this is a copy
# merge two already sorted into one
i = 0
j = 0
for k in range(start, end):
if i >= len(L) or (j < len(R) and L[i] > R[j]):
arrs[k] = R[j]
j = j + 1
else:
arrs[k] = L[i]
i = i + 1
def __divied(arrs, start, end):
if end - start <= 1:
return
mid = start + (end - start) // 2
__divied(arrs, start, mid) # divide
__divied(arrs, mid, end) # divide
__merge(arrs, start, mid, end) # combine
__divied(arrs, 0, len(arrs))
插入排序
O(N^2)
[3, 4] + [2, 5, 7, 9] # 当插入2时
[x, 3, 4] # 4比2大, 3比2大, 都右移一位，让出x位置
^
2
对于小规模数据，还是挺快的
def insertion_sort(arrs):
for i in range(1, len(arrs)): #from 2nd to the end
target = arrs[i]
# right shift until appropriate position found
j = i
while j > 0 and target < arrs[j - 1]:
arrs[j] = arrs[j - 1]
j -= 1
arrs[j] = target
冒泡排序
O(N^2)
[3, 4, 2, 5, 7, 9]
i
# 最小的2, 一步步交换, 放置到最左边i=0的位置
[2, 3, 4, 5, 7, 9]
i
# 移动i，继续上述操作
最小元素像气泡一样, 一步步浮到左边
def bubble_sort(arrs):
for i in range(len(arrs)):
for j in reversed(range(i, len(arrs))):
if arrs[j] < arrs[j - 1]:
arrs[j], arrs[j - 1] = arrs[j - 1], arrs[j]
选择排序
O(N^2)
[3, 4, 2, 5, 7, 9]
i
------ min ------
# 找到右边最小的元素，然后和i交换
[2, 3, 4, 5, 7, 9]
i
---- min ----
# 移动i，继续上述操作
def selection_sort(arrs):
for i in range(0, len(arrs)):
min_index = i
# find the smallest element from (i+1)th to the last
for j in range(i + 1, len(arrs)):
if arrs[j] < arrs[min_index]:
min_index = j
if min_index != i:
arrs[i], arrs[min_index] = arrs[min_index], arrs[i]
堆排序
O(N * logN)
利用大堆的性质，每次拿出来root最大的，放在后面
0 1
/ \ / \
1 2 2 3
/ \ / / \ /
3 4 5 4 5 6
# 以 0 为跟节点的堆, left = 2i + 1, right = 2i + 2
# 以 1 为跟节点的堆, left = 2i, right = 2i + 1
有点像选择排序，每次拿到最大的，放入到对应的位置
def heap_sort(arrs):
def __max_heepify(arrs, size, i):
l = 2 * i + 1
r = 2 * i + 2
largest = i
# find the largest in the little "triangle", and swap them.
# since swap may break the heap in child heap, so do it reacursively
if l < size and arrs[l] > arrs[largest]:
largest = l
if r < size and arrs[r] > arrs[largest]:
largest = r
if largest != i:
arrs[i], arrs[largest] = arrs[largest], arrs[i]
__max_heepify(arrs, size, largest)
# building a heap using array
def __build_heap(arrs):
for i in reversed(range(0, len(arrs)//2)):
__max_heepify(arrs, len(arrs), i)
__build_heap(arrs)
for i in reversed(range(1, len(arrs))):
arrs[i], arrs[0] = arrs[0], arrs[i]
__max_heepify(arrs, i, 0)
–End–
代码原地址: https://github.com/geemaple/leetcode/tree/master/learning