排序問題考察的很多，這里有一個排序問題的動畫演示，不過再用動畫來演示也要自己多遍手寫來熟悉原理和流程
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
另一個可視化算法的地方：https://visualgo.net/en
quick sort:
重點在partition和終止條件。如果是用stack，則模擬preorder的stack性質(zhì)。
# quick sort, recursive
def qs(arr, start, end):
if start < end:
index = partition(arr, start, end)
qs(arr, start, index-1)
qs(arr, index+1, end)
def partition(arr, start, end):
# use start as pivot
# from IPython.core.debugger import Tracer; Tracer()()
pivot = arr[start]
i = start + 1
j = end
while i <= j:
while i <= j and arr[i] <= pivot:
i += 1
while i <= j and arr[j] >= pivot:
j -= 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
# swap pivot with j
arr[start], arr[j] = arr[j], arr[start]
return j
partition函數(shù)的另一種寫法，利用最后一個值作為pivot
def partition(arr, start, end):
pos = start # use the end value as pivot
for i in range(start, end): # i must be between start and end-1
if arr[i] < arr[end]:
arr[i],arr[pos] = arr[pos],arr[i]
pos += 1
arr[pos],arr[end] = arr[end],arr[pos] # you forgot to put the pivot
# back in its place
return pos
非遞歸寫法
# 快速排序，非遞歸寫法，類似于preorder traversal
def qsort_stack(arr):
stack = [(0, len(arr)-1)]
while stack:
i, j = stack.pop()
index = partition(arr, i, j)
if j > index + 1:
stack.append((index+1, j))
if i < index - 1:
stack.append((i, index-1))
quick select
利用partition過程中，每次站好隊的那個元素和其index
def select(vector, left, right, k):
"Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1] inclusive."
while True:
index = partition(vector, left, right)
dist = index - left # 找到一個值，放好位置，和k做比較
if dist == k:
return vector[index] # 如果當前index正好是k，那么就返回值
elif k < dist:
right = index - 1
else:
k -= dist + 1
left = index + 1
merge sort:
merge sort是要用額外空間的，但是它是有序的。如果既要有序又要inplace，可以用bubble sort
# mergesort
def ms(arr):
if len(arr) <= 1:
return arr
mid = len(arr) / 2
arr1 = ms(arr[:mid])
arr2 = ms(arr[mid:])
return merge(arr1, arr2)
def merge(arr1, arr2):
arr = []
p1 = 0
p2 = 0
while p1 < len(arr1) and p2 < len(arr2):
if arr1[p1] > arr2[p2]:
arr.append(arr2[p2])
p2 += 1
else:
arr.append(arr1[p1])
p1 += 1
return arr + arr1[p1:] + arr2[p2:]
bubble sort
先排好最大值（把最大值放到最后一個），然后再排倒數(shù)第二大的值。
# bubble sort
def bs(arr):
for i in range(len(arr)-1, -1, -1):
for j in range(i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
selection sort
從后往前，對于第i 位，選取0～i位中最大的和i位swap
# selection sort
def ss(arr):
for i in range(len(arr)-1, -1, -1):
pos = 0
for j in range(i+1):
if arr[pos] < arr[j]:
pos = j
arr[pos], arr[i] = arr[i], arr[pos]
insertion sort:
插入排序可以保持前列有序，然后依次向后排序
# insertion sort
def ins(arr):
for i in range(len(arr)):
val = arr[i]
pos = i
while pos > 0 and arr[pos-1] > val:
arr[pos] = arr[pos-1]
pos -= 1
arr[pos] = val
shell sort
利用gap減少了insertion sort的comparison的次數(shù)，應該不會考。
# shell sort
def ss(arr):
sub = len(arr)/2
while sub > 0:
for start in range(sub):
gapins(arr,start,sub)
print "After increments of size",sub, "The list is",arr
sub = sub / 2
def gapins(arr,start,gap):
for i in range(start+gap,len(arr),gap):
val = arr[i]
pos = i
while pos >= gap and arr[pos-gap] > val:
arr[pos] = arr[pos-gap]
pos = pos-gap
arr[pos] = val
heap sort
def hs(arr):
# 先建立一個heap，然后把最大值依次取出放到最后一位，這是inplace的做法
for start in range((len(arr)-2)/2, -1, -1):
siftdown(arr, start, len(arr)-1)
for end in range(len(arr)-1, 0, -1):
arr[end], arr[0] = arr[0], arr[end]
siftdown(arr, 0, end - 1)
return arr
def siftdown(arr, start, end):
root = start
while True:
child = root * 2 + 1
if child > end:
# 如果root沒有子結點
break
if child + 1 <= end and arr[child] < arr[child + 1]:
# 如果root有兩個子結點，那么選擇其中較大的那個
child += 1
if arr[root] < arr[child]:
# 把root的節(jié)點下移到子結點，然后重復這個操作
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
break
counting sort
適合range不太大的數(shù)的count，比如說數(shù)字符串，復雜度為：O(n+k) k就是range，n是要排序的個數(shù)。
def cs(s):
# 對一個字符串排序
count = [0 for i in range(26)]
output = ["" for _ in s]
# 存貯在count上存貯每一個字符出現(xiàn)的次數(shù)
for c in s:
count[ord(c)-ord("a")] += 1
# 做一個prefix sum，這樣就可以知道每一個字符的實際位置
for i in range(1, 26):
count[i] += count[i-1]
# 創(chuàng)建一個輸出arr，
for c in s:
output[count[ord(c)-ord("a")]-1] = c
count[ord(c)-ord("a")] -= 1
return output
bucket sort
對于一個range里均勻分布的問題，比如說一堆在0，1之間的float進行排序，這里不能用counting sort，因為counting sort需要用到index
bucketSort(arr[], n)
- Create n empty buckets (Or lists).
- Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]] - Sort individual buckets using insertion sort.
- Concatenate all sorted buckets.
def bsort(A):
"""Returns A sorted. with A = {x : x such that 0 <= x < 1}."""
buckets = [[] for x in range(10)]
for i, x in enumerate(A):
buckets[int(x*len(buckets))].append(x)
out = []
for buck in buckets:
out += isort(buck)
return out
def isort(A):
if len(A) <= 1: return A
i = 1
while i < len(A):
k = A[i]
j = i - 1
while j >= 0 and A[j] > k:
A[j+1] = A[j]
A[j] = k
j -= 1
i += 1
return A
radix sort
radix sort
def radix_sort(arr, radix=10):
k = int(math.ceil(math.log(max(arr), radix)))
for i in range(1, k+1):
bucket = [[] for k in range(radix)]
for j in arr:
bucket[j/(radix**(i-1)) % radix].append(j)
arr = sum(bucket, [])
return arr
Kth Largest Element in an Array: 這題看起來簡單，但是解法很多。https://leetcode.com/problems/kth-largest-element-in-an-array/#/solutions
