# Algorithms ##背景 简单复习一下最基本的算法和数据结构

## Sorting

### Quicksort

def quicksort(self, nums):
if len(nums) <= 1:
return nums

pivot = random.choice(nums)
lt = [v for v in nums if v < pivot]
eq = [v for v in nums if v == pivot]
gt = [v for v in nums if v > pivot]

return self.quicksort(lt) + eq + self.quicksort(gt)


### Heapsort

• The (binary) heap data structure is an array object that we can view as a nearly complete binary tree (except possibly the lowest)

• sort in place

• runtime $O(n \lg n)$, height $\Theta(\lg n)$

• index of array starts at 1.

• def parent(i):
return i // 2

def left(i):
return 2 * i

def right(i):
return 2 * i + 1

def max_heapify(A, i):
l = left(i)
r = right(i)
if l <= A.heap_size and A[l] > A[i]:
largest = l
else:
largest = i
if r <= A.heap_size and A[r] > A[largest]:
largest = r
if largest != i:
A[i], A[largest] = A[largest], A[i]
max_heapify(A, largest)

def build_max_heap(A):
A.heap_size = len(A)
for i in range(len(A) // 2, 0, -1):
max_heapfiy(A, i)


## Data Structures

### Segment Tree

• to find if there is a cycle in a linked list

• class Node:
def __init__(self, x):
self.val = x
self.next = None

"""
:rtype: bool
"""
return False
while runner.next and runner.next.next:
runner = runner.next.next
walker = walker.next
if runner == walker:
return True
return False


## Miscellaneous

### Parition of a number

• partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers，不关心顺序

• # 这个是输出所有的partition结果
def partitions(n, I=1):
yield (n, )
for i in range(I, n // 2 + 1):
for p in partitions(n - i, i):
yield (i, ) + p

# 这个是计算有多少种分法，其实和上面的类似
def par(n, b=1):
r = 1
for i in range(b, n // 2 + 1):
r += par(n - i, i)
return r


### Selection rank

• similar to quick sort

# To be continued …

Written on June 1, 2019