1.归并排序

采用分治的思路，就是二分法+递归，算法复杂度O（n*logn）。
这个思路简单说，就是先把数据分左右两份，直到每一份只有两个数据，递归到最内层就是两个数字的比较，然后依次向上合并，每次都是排好序的左右数组的比较。这里需要写两个函数，一个用来排序，一个用来合并。
最开始的时候，想用一个函数解决，但每次result更新为空，影响了排序结果，所以还是拆分两个函数比较好。

def merge(left, right):
    result = []    
    i = j = 0
    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
        print(result)
    if i <= len(left):
        result.extend(left[i:])
    if j <= len(right):
        result.extend(right[j:])
    return result
def guibing(input):
    r = len(input)
    if r<2:
        return input
    mid = r //2
    left = input[0:mid]
    right = input[mid:]
    rleft = guibing(left)
    rright = guibing(right)
    return merge(rleft,rright)
list1 = [3,5,6,5,3,2,1,5,4,7,8]
guibing(list1)

2.冒泡排序

冒泡排序应该算是入门级别的算法了吧，特别好理解。就是来来回回比大小，用两个for循环控制，第一轮比完以后就知道最小（大）的数是哪个了，下次就可以少比较一个。所以有两种写法，一种是从头往后放，一种是从后往前放，算法复杂度是O（n2）。

def buble(input):
    l = len(input)
    for i in range(l):
        for j in range(i+1,l):
            if input[i] > input [j]:
                input[i],input[j] = input[j],input[i]
    return input

3.快速排序

快速排序就是说一个二分法加一个递归，效率会高一点。思路比较好理解吧，随便从列表里选一个数据，以它为基准，比他小就放左边，大就放右边，最后再递归划分，直到就剩一个数据。它的时间复杂度为O(n*logn)。
2020-02-21补充，这个题我面试遇到了我竟然忘了，看了半天网上的解释，真的是理解不深啊，这里新更新一个解法，就是左右扫描的解法。具体来说就是选择基准后来回扫描发现最大值小于基准值，最小值大于基准值时候二者就交换位置，这样的目的是把基准值排到中间位置，不是数组中间位置而是值的中间位置，就是左边的值都比他小，右边的值都比他大，然后low和tmp交换位置，就实现了基本有序，然后再递归求解。真的是不如解法1方便。

#解法1
def quick(input):
    if len(input) < 1:
        return input
    mid = len(input) // 2
    left = []
    right = []
    base = input[mid]
    input.remove(base)
    for i in range(len(input)):
        if input[i] < base:
            left.append(input[i])
        else:
            right.append(input[i])
    return quick(left) + [base] + quick(right)
#解法2
def quicksort(x):
    if len(x) <= 1:
        return x
    m = len(x)
    tmp, low, high = 0, 0, m-1
    while low < high:
        while low < high and x[high] >= x[tmp]:
            high -= 1
            # print(1, high)
        while low < high and x[low] <= x[tmp]:
            low += 1
            # print(2, low)
        x[high], x[low] = x[low], x[high]
    x[low], x[tmp] = x[tmp], x[low]
    return quicksort(x[:low]) + [x[low]] + quicksort(x[low+1:])

4.插入排序

插入排序是根据位置，依次比较排好序，它也是一个双层循环，内层是排好序的数组，外层是整个数组，如果发现当前进数组的数比排好序数组的最后一个元素小，就把这个元素往后移动一位，以此类推。这里有个问题就是，因为是在原来的数组上操作，所以要把当前进排序的数给保存下来，以免排序数组位移的时候把当前数据给覆盖了。

def insert(input):
    l = len(input)
    for i in range(1,l):
        value = input[i]
        j = i - 1
        while j >= 0:
            if input[j] > value:
                input[j+1] = input[j]
            else:
                break
            j -= 1
        input[j+1] = value
    return input

5.选择排序

选择排序和冒泡排序一样简单，思路就是先选定一个基准数据（从位置0开始），然后比较找到比他还小的最小数，然后交换位置。明显时间复杂度为O(n2)。

def selectsort(x):
    if len(x) <= 1:
        return x
    for i in range(len(x) - 1):
        minidx = i
        for j in range(i+1, len(x)):
            if x[j] <= x[minidx]:
                minidx = j
        x[i], x[minidx] = x[minidx], x[i]
    return x

6.堆排序

堆排序算是比较复杂的一种排序方式了，可以分两步进行，第一步就是构造一个堆，什么是堆呢，堆就是完全二叉树，根节点数据大于（小于）所有的叶子节点数据。构造堆，是一个遍历，自底向上的过程，分别找左右叶子节点的最大值，跟当前跟节点值的比较，比较完成后继续遍历如果大，就更新位置，然后把跟节点值放到相应位置去。然后对排序是从底向上的过程，第一个元素和最后一个元素互换位置，然后重排剔除最后一个元素的堆，使其成为最大堆。

def max_heap(heap,heapsize,root):
    i, j = root, 2*root+1
    tmp = heap[i]
    while j < heapsize:
        if j + 1 < heapsize and heap[j] < heap[j+1]:
            j = j + 1
        if tmp > heap[j]:
            break
        heap[i] = heap[j]
        i, j = j, 2*j + 1
    heap[i] = tmp
def build_max_heap(heap):
    heapsize = len(heap)
    for i in range(heapsize//2-1, -1, -1):
        max_heap(heap, heapsize, i)
    return heap
def heap_sort(heap):
    heapsize = len(heap)
    heap = build_max_heap(heap)
    for i in range(heapsize-1, 0, -1):
        heap[i], heap[0] = heap[0], heap[i]
        max_heap(heap, i, 0)
    return heap