排序算法

# 1nd: 两两交换
def insertion_sort(arr):
    for i in range(1, len(arr)):
        j = i
        while j >= 0 and arr[j-1] > arr[j]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j -= 1
    return arr
# 2nd: 交换，最后处理没交换的
def insertion_sort2(arr):
    for i in range(1, len(arr)):
        j = i-1
        key = arr[i]
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr
# 3nd: 加速版本，利用已经排好了序的进行二分查找
def insertion_sort3(seq):
    for i in range(1, len(seq)):
        key = seq[i]
        # invariant: ``seq[:i]`` is sorted
        # find the least `low‘ such that ``seq[low]`` is not less then `key‘.
        #   Binary search in sorted sequence ``seq[low:up]``:
        low, up = 0, i
        while up > low:
            middle = (low + up) // 2
            if seq[middle] < key:
                low = middle + 1
            else:
                up = middle
        # insert key at position ``low``
        seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
    return seq
# 4nd: 原理同上，使用bisect
import bisect
def insertion_sort4(seq):
    for i in range(1, len(seq)):
        bisect.insort(seq, seq.pop(i), 0, i)  # 默认插在相同元素的左边
    return seq

# 1nd: for
def select_sort(seq):
    for i in range(0, len(seq)):
        mi = i
        for j in range(i, len(seq)):
            if seq[j] < seq[mi]:
                mi = j
        seq[mi], seq[i] = seq[i], seq[mi]
    return seq
# 2nd: min
def select_sort2(seq):
    for i, x in enumerate(seq):
        mi = min(range(i, len(seq)), key=seq.__getitem__)
        seq[i], seq[mi] = seq[mi], x
    return seq

def bubble_sort(seq):
    for i in range(len(seq)):
        for j in range(len(seq)-1-i):
            if seq[j] > seq[j+1]:
                seq[j], seq[j+1] = seq[j+1], seq[j]
    return seq
def bubble_sort2(seq):
    for i in range(0, len(seq)):
        for j in range(i + 1, len(seq)):
            if seq[i] > seq[j]:
                seq[i], seq[j] = seq[j], seq[i]
    return seq

def quick_sort(seq):
    if len(seq) >= 1:
        pivot_idx = len(seq)//2
        small, large = [], []
        for i, val in enumerate(seq):
            if i != pivot_idx:
                if val <= seq[pivot_idx]:
                    small.append(val)
                else:
                    large.append(val)
        quick_sort(small)
        quick_sort(large)
        return small + [seq[pivot_idx]] + large
    else:
        return seq

# 1nd: 将两个有序数组合并到一个数组
def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    num = len(lists) / 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)
# 2nd: use merge
from heapq import merge
def merge_sort2(m):
    if len(m) <= 1:
        return m
    middle = len(m) // 2
    left = m[:middle]
    right = m[middle:]
    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

# 1nd: normal
def swap(seq, i, j):
    seq[i], seq[j] = seq[j], seq[i]
# 调整堆
def heapify(seq, end, i):
    l = 2 * i + 1
    r = 2 * (i + 1)
    ma = i
    if l < end and seq[i] < seq[l]:
        ma = l
    if r < end and seq[ma] < seq[r]:
        ma = r
    if ma != i:
        swap(seq, i, ma)
        heapify(seq, end, ma)
def heap_sort(seq):
    end = len(seq)
    start = end // 2 - 1
    # 创建堆
    for i in range(start, -1, -1):
        heapify(seq, end, i)
    for i in range(end - 1, 0, -1):
        swap(seq, i, 0)
        heapify(seq, i, 0)
    return seq
# 2nd: use heapq
import heapq
def heap_sort2(seq):
    """ Implementation of heap sort """
    heapq.heapify(seq)
    return [heapq.heappop(seq) for _ in range(len(seq))]

def shell_sort(seq):
    count = len(seq)
    step = 2
    group = count // step
    while group > 0:
        for i in range(0, group):
            j = i + group
            while j < count:
                k = j - group
                key = seq[j]
                while k >= 0:
                    if seq[k] > key:
                        seq[k + group] = seq[k]
                        seq[k] = key
                    k -= group
                j += group
        group //= step
    return seq