算法

算法部分的介绍在十大经典排序算法动画与解析，看我就够了！

关于时间复杂度：

1. 平方阶 $(O(n^2))$ 排序 各类简单排序：插入排序、选择排序和冒泡排序。
2. 线性对数阶$ (O(nlog2n))$ 排序：快速排序、堆排序和归并排序；
3. $O(n+§))$ 排序，$§$ 是介于 0 和 1 之间的常数。 希尔排序
4. 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序

关于稳定性：

1. 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
2. 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

python实现

冒泡排序

def bubblesort(arr):
    n=len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]
    return arr
if __name__ == '__main__':
    arr = [5,4,2,3,8]
    bubblesort(arr)
    print(arr)

选择排序

def selectionsort(arr):
    n = len(arr)
    for i in range(n):
        min =i
        for j in range(i, n):
            if arr[j] < arr[i]:
                min =j
                arr[min], arr[i] = arr[i], arr[min]
    return arr

if __name__ == '__main__':
    arr=[5,4,2,3,8]
    selectionsort(arr)
    print(arr)

插入排序

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

if __name__ == '__main__':
    arr = [5,4,2,3,8]
    insertionSort(arr)
    print(arr)

希尔排序

def shellsort(arr):
    n = len(arr)
    gap = n
    while gap > 0:
        gap = gap // 2
        for i in range(gap, n):
            key = arr[i]
            j = i - gap
            while j >= 0 and key < arr[j]:
                arr[j + gap] = arr[j]
                j -= gap
            arr[j + gap] = key
    return arr


if __name__ == '__main__':
    arr = [5, 4, 2, 3, 8]
    shellsort(arr)
    print(arr)

归并排序

def sorttwoarray(arr_left, arr_right):
    m, n, i, j = len(arr_left), len(arr_right), 0, 0
    arr = []
    while i < m and j < n:
        if arr_left[i] < arr_right[j]:
            arr.append(arr_left[i])
            i += 1
        else:
            arr.append(arr_right[j])
            j += 1
    arr.extend(arr_left[i:m])
    arr.extend(arr_right[j:n])
    return arr


def mergesort(arr):
    n = len(arr)
    arr_left = arr[:(n + 1) // 2]
    arr_right = arr[(n + 1) // 2:]
    if len(arr_left) == 1:
        return sorttwoarray(arr_left, arr_right)
    else:
        return sorttwoarray(mergesort(arr_left), mergesort(arr_right))


if __name__ == '__main__':
    arr = [6, 4, 3, 7, 5, 1, 2]
    array = mergesort(arr)
    print(array)

快速排序

# -*- coding: UTF-8 -*-
# 《算法导论》中的快速排序
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):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i + 1]
    return i + 1

if __name__ == '__main__':
    arr = [6, 4, 3, 7, 5, 1, 2]
    quick_sort(arr,0,6)
    print(arr)

堆排序

# -*- coding: UTF-8 -*-
def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1  # left = 2*i + 1
    r = 2 * i + 2  # right = 2*i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    # Build a maxheap.
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    # 一个个交换元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)

if __name__ == '__main__':
    arr = [5, 2, 7, 3, 6, 1, 4]
    heapSort(arr)
    print (arr),

计数排序

def countingsort(arr):
    n = len(arr)
    min_arr = min(arr)
    max_arr = max(arr)
    length = max_arr - min_arr + 1
    newarr = [0] * length
    sort_arr = []
    for i in arr:
        newarr[i - min_arr] += 1
    for i in range(length):
        sort_arr += [i + min_arr] * newarr[i]
    return sort_arr


if __name__ == '__main__':
    arr = [5, 3, 4, 7, 2, 4, 3, 4, 7]
    sort_arr = countingsort(arr)
    print(sort_arr)

桶排序

def bucketsort(arr, num_bucket):
    min_arr = min(arr)
    max_arr = max(arr)
    buckets = [[] for i in range(num_bucket)]
    size = (max_arr - min_arr + 1) / num_bucket
    sorted_arr = []
    for i in arr:
        index = (i - min_arr) // size
        buckets[index].append(i)
    for i in buckets:
        sorted_arr += (sorted(i))
    return sorted_arr


if __name__ == '__main__':
    arr = [7, 12, 56, 23, 19, 33, 35, 42, 42, 2, 8, 22, 39, 26, 17]
    sort_arr = bucketsort(arr, 5)
    print(sort_arr)

基数排序

def radixsort(arr):
    d = 1
    max_arr = max(arr)
    while max_arr / 10 != 0:
        d += 1
        max_arr /= 10
    for i in range(d):
        s = [[] for k in range(10)]
        for j in arr:
            s[int(j / (10 ** i)) % 10].append(j)
            sorted_arr = [a for b in s for a in b]
    return sorted_arr


if __name__ == '__main__':
    arr = [321, 1, 10, 30, 277, 753, 127]
    sorted_arr = radixsort(arr)
    print (sorted_arr)