常用排序查找算法

算法	最坏情况运行时间	平均情况/期望运行时间
插入排序	Θ(n2)$$\mathrm{\Theta }(n^2)$$	Θ(n2)$$\mathrm{\Theta }(n^2)$$
归并排序	Θ(nlgn)$$\mathrm{\Theta }(nlgn)$$	Θ(nlgn)$$\mathrm{\Theta }(nlgn)$$
堆排序	O(nlgn)$$O(nlgn)$$	–
快速排序	Θ(n2)$$\mathrm{\Theta }(n^2)$$	Θ(nlgn)(期望)$$\mathrm{\Theta }(nlgn)(期望)$$
计数排序	Θ(k+n)$$\mathrm{\Theta }(k+n)$$	Θ(k+n)$$\mathrm{\Theta }(k+n)$$
基数排序	Θ(d(n+k))$$\mathrm{\Theta }(d(n+k))$$	Θ(d(n+k))$$\mathrm{\Theta }(d(n+k))$$
桶排序	Θ(n2)$$\mathrm{\Theta }(n^2)$$	Θ(n)(平均情况)$$\mathrm{\Theta }(n)(平均情况)$$

• 在最坏情况下，任何比较排序算法都需要做 Ω(nlgn)$\mathrm{\Omega }(nlgn)$次比较
• 堆排序和归并排序都是渐进最优的比较排序算法(Θ(nlgn)$\mathrm{\Theta }(nlgn)$)

插入排序：
1. 从第二个数开始，依次跟左边的数进行比较，直到找到不大于正在插入的数字或者到达序列头部时，进行插入。
2. 原址排序
3. O(n^2)
4. 从下标0开始存储数据
5. 比较排序

def insertion_sort(arr):
    for i in range(1, len(arr)):
        k = arr[i]
        j = i - 1
        while j > -1 and arr[j] > k:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = k
    return arr

---

归并排序：
1. 先排序子问题，再合并
2. O(nlgn)
3. 从下标0开始存储数据
4. 比较排序

def merge(arr, p, q, r):
    n1 = q - p + 1
    n2 = r - q
    L = arr[p:q]
    R = arr[q:r]
    L.append(float('inf'))
    R.append(float('inf'))
    i = j = 0
    for k in range(p, r):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i = i + 1
        else:
          arr[k] = R[j]
          j = j + 1
    print(arr)
def merge_sort(arr, p, r):
    if p < r - 1:
        q = math.floor((r + p) / 2)
        merge_sort(arr, p, q)
        merge_sort(arr, q, r)
        merge(arr, p, q, r)
    print(arr)
merge_sort([4,5,2,3], 0, 4)

---

选择排序：
1. 依次查找最小的元素
2. O(n^2)
3. 从下标0开始存储数据
4. 比较排序

def selection_sort(arr):
    i = 0
    length = len(arr)
    while i < length - 1:
        min = arr[i]
        index = i
        j = i + 1
        while j < length:
            if arr[j] < min:
                min = arr[j]
                index = j
            j = j + 1
        if index != i:
            arr[index] = arr[i]
            arr[i] = min
        i = i + 1

---

二分查找：
1. 分为子问题
2. O(lgn)
3. 从下标0开始存储数据

def binary_search(arr, v):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = math.floor((low + high)/2)
        if arr[mid] == v:
            return mid
        elif arr[mid] > v:
            high = mid - 1
        else:
            low = mid + 1
    return -1

---

冒泡排序：
1. 依次调整相邻的元素，每一轮将最大的元素“冒泡”到尾部
2. O(n^2)
3. 从下标0开始存储数据
4. 比较排序

def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(1, len(arr) - i + 1):
            if arr[j - 1] > arr[j]:
                temp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = temp
            j = j + 1
        i = i + 1

---

最大子数组：
1. 记录当前的最大子数组(max_low, max_high, max_sum), 依次当前位置左侧的最大数组(low, high, current_sum). 当左侧最大的数组的和小于零时，将左侧最大数组设为仅含当前元素的数组。
2. O(n)
3. 从下标0开始存储数据

def maximum_subarray(arr):
    if len(arr) < 1:
        return arr
    max_sum = current_sum = arr[0]
    max_low = max_high = low = high = 0
    for i in range(1, len(arr)):
        if current_sum < 0 and arr[i] > current_sum:
            low = high = i
            current_sum = arr[i]
        else:
            current_sum = current_sum + arr[i]
            high = i
        if current_sum >= max_sum:
            max_low = low
            max_high = high
            max_sum = current_sum
    return arr[max_low:max_high+1]

---

堆排序：
1. (二叉)堆是一个数组，它可以被看成一个近似的完全二叉树。树上的每一个节点对应数组中的一个元素。除了最底层外，该树是完全充满的，而且是从左向右填充。表示堆的数组 A 包括两个属性： A.length (通常)给出数组元素的个数， A.heap_size 表示有多少个堆元素存储在该数组中。
2. 依次将最大堆的第一个元素和堆的最后一个元素替换，堆的大小减一，调整堆使满足最大堆的性质
3. arr[0] store the size of the heap elements
4. O(nlgn)
5. 比较排序
6. 从下标1开始存储数据

def max_heapify(arr, i):
    l = 2 * i
    r = 2 * i + 1
    heap_size = arr[0]
    if l <= heap_size and arr[l] > arr[i]:
        largest = l
    else:
        largest = i
    if r <= heap_size and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        temp = arr[largest]
        arr[largest] = arr[i]
        arr[i] = temp
        max_heapify(arr, largest)
def build_max_heap(arr):
    heap_size = arr[0]
    for i in range(math.floor(heap_size / 2), 0, -1):
        max_heapify(arr, i)
def heap_sort(arr):
    heap_size = arr[0]
    for i in range(1, heap_size):
        temp = arr[heap_size]
        arr[heap_size] = arr[1]
        arr[1] = temp
        heap_size = arr[0] = arr[0] - 1
        max_heapify(arr, 1)

---

快速排序：
1. 比较排序
2. 划分arr[p..r] 为两个(可能为空)子数组 arr[p..q-1] 和 arr[q+1..r], 使得arr[p..q-1] 中的每一个元素都小于等于 arr[q], 而arr[q+1..r]中的每一个元素都大于等于arr[q]. 其中下标 q 也是划分过程的一部分。
3. 在两个数组上递归调用快速排序
4. 因为子数组都是原址排序，所以不需要合并操作， 数组arr[p..r]已经有序
5. 原址排序
6. 从下标0开始存储数据

def quick_sort(arr, p, r):
    if p < r:
        #q = partition(arr, p, r)
        q = randomized_partition(arr, p, r)
        quick_sort(arr, p, q-1)
        quick_sort(arr, q + 1, r)       
def partition(arr, p, r): 
    x = arr[r]
    i = p 
    j = r - 1 
    while j > i:
        if arr[j] <= x:
            temp = arr[j]
            arr[j] = arr[i]
            arr[i] = temp
            i = i + 1
        else:
            j = j - 1
    arr[r] = arr[j + 1]
    arr[j + 1] = x
    return j + 1
def randomized_partition(arr, p, r):
    i = randint(p, r - 1) # p, r-1 included
    temp = arr[i]
    arr[i] = arr[r]
    arr[r] = temp
    return partition(arr, p, r)

假设所有元素都是互异的，最坏情况下，运行时间为O(nlgn)$O(nlgn)$的快速排序算法
psudo code

BEST_CASE_QUICKSORT(A, p, r)
    if p < r
        i =  floor((r - p + 1)/2)
        x=SELECT(A, p, r, i)
        q=PARTITION(x)
        BEST_CASE_QUICKSORT(A, p, q-1)
        BEST_CASE_QUICKSORT(A, q+1, r)

---

计数排序：
1. 假设n个输入元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。 当k=O(n)$k=O(n)$时，排序的运行时间为Θ(n)$\mathrm{\Theta }(n)$
2. 计数排序的基本思想是：对每一个输入元素x,确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置了。
3. 稳定的
4. 非比较排序
5. A
6. 从下标1开始存储数据

def counting_sort(A, B, k):
    #A: input
    #B: store output
    #k: range top
    C = [0] * k
    for v in A[1:]:
        C[v] = C[v] + 1
    for i in range(1, len(C)):
        C[i] = C[i] + C[i - 1]
    for i in range(len(A) - 1, 0, -1):
        B[C[A[i]]] = A[i]
        C[A[i]] = C[A[i]] - 1

---

基数排序：
1. 依次从低位到高位使用稳定的排序算法对元素排序
2. n个d位数，其中每一数位有k个可能的值。 Θ(d(n+k))$\mathrm{\Theta }(d(n+k))$
3. 从下标0开始存储数据

def radix_sort(A, d, k = 10):
    #A: input
    #d: number of bits
    #k: radix
    for i in range(0, d):
        A = counting_sort(A, k, i)
    return A
def counting_sort(A, k, E):
    #A: input
    #k: number of values in Eth bit
    #E: exponent
    C = [0] * k
    B = [0] * len(A)
    e = int(math.pow(k, E))
    for i in A:
        index = i // e % 10
        C[index] = C[index] + 1
    for i in range(1, len(C)):
        C[i] = C[i] + C[i - 1]
    for i in range(len(A) - 1, -1, -1):
        index = A[i] // e % 10
        B[C[index] - 1] = A[i]
        C[index] = C[index] - 1
    return B

---

桶排序：
1. 桶排序(bucket sort)假设输入数据服从均匀分布，平均情况下O(n)$O(n)$
2. 记数排序假设输入数据都属于一个小区间内的整数，而桶排序则假设输入是一个随机过程产生，该过程将元素均匀、独立地分布在[0,1)$[0,1)$区间上
3. 桶排序将[0,1)$[0,1)$区间划分为n个相同大小的子区间，或称为桶。将数据放到各个桶中，对各个桶中的数据进行排序，然后将各个桶中的数据连接起来。

class Node:
    def __init__(self, value = None, next = None):
        self.value = value
        self.next = next       
def bucket_sort(A):
    n = len(A)
    #B = [Node()] * n  !important, don't use this way to initialize B. For all elements pointer to the same node.
    B = [0] * n
    for i in range(0, n):
        B[i] = Node()
    for i in A:
        k = math.floor(n * i)
        if(B[k].next):
            p = B[k]
            while p.next and p.next.value <= i:
                p = p.next
            p.next = Node(i, p.next)
        else:
            B[k].next = Node(i)
    C = []
    for i in B:
        p = i
        while p.next and p.next.value != None:
            C.append(p.next.value)
            p = p.next
    return C

---

第二小元素：

def second_smallest(numbers):
    m1, m2 = float('inf'), float('inf')
    for x in numbers:
        if x <= m1:
            m1, m2 = x, m1
        elif x < m2:
            m2 = x
    return m2

---

选择算法：
expection time Θ(n)$\mathrm{\Theta }(n)$
select the ith smallest element

RANDOMIZED_SELECT(A, p, r, i)
    if p == r
        return A[p]
    q = RANDOMIZED_PARTITION(A, p, r)
    k = q - p + 1
    if i == k       // the pivot value is the answer
        return A[q]
    else if i < k
        return RANDOMIZED_SELECT(A, p, q - 1, i)
    return RANDOMIZED_SELECT(A, q + 1, r, i - k)

selection method with Θ(n)$\mathrm{\Theta }(n)$ at the worst case refer to algorithms 3th edition 9.3,
select the ith smallest element
SELECT基本思想是：
1.将数组划分为每组5个元素，最后一组可以不足五个
2.对每组进行插入排序，因此可以确定中位数
3.对每组的中位数进行递归调用SELECT以找出其中位数x(如果有偶数个中位数，使用较小的)
4.使用主元x对数组进行划分。 比x小的为低区，反之为高区。x 是 第 len(低区的元素) + 1 小的元素，假设为第 k 小。
5 如果 i==k, 则返回x, 如果 i < k，则在低区递归调用SELECT 来找出第i小的元素。如果i > k， 则在高区递归查找第 i - k 小的元素。