排序算法

算法分类

线性非线性

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

复杂度

冒泡排序（Bubble Sort）

选择排序（Selection Sort）

插入排序（Insertion Sort）

希尔排序（Shell Sort）

归并排序（Merge Sort）

def merge(left, right):
    res = []
    while left and right:
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    res = res + left + right
    return res

def mergesort(lists):
    if len(lists) <= 1:
        return lists
    mid = len(lists)//2
    left = mergesort(lists[:mid])
    right = mergesort(lists[mid:])
    return merge(left,right)

快速排序（Quick Sort）

def partition(arr, beg, end):
    pivot = arr[end-1]
    i = beg - 1
    for j in range(beg, end-1):
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[end-1] = arr[end-1], arr[i+1]
    return i + 1
 
def quicksort(arr, beg, end):
    if beg < end - 1:
        q = partition(arr, beg, end)
        quicksort(arr, beg, q)
        quicksort(arr, q+1, end)