几种排序方法

冒泡排序

def bubblesort(mylist):
    mylen = len(mylist)
    for i in range(mylen-1):
        for j in range(i+1, mylen):
            if mylist[i] > mylist[j]:
                mylist[i], mylist[j] = mylist[j], mylist[i]
    return mylist

快排

采用了分治思想，难理解的是partition算法，其以最数组最右侧位置的数作为基准，将数组分为小于该基准和大于等于该基准的两个子数组。
网上大部分的partition的实现版本在算法导论上有讲，但不好懂。

本partion实现版本里，从左右两侧分别进行，左侧记录大于基准值的位置，右侧记录小于基准值的位置，当两个位置都找到则互换，直到两个指针指向同一个位置。

def quicksort(array, l, r):
    
    def partition(array, l, r):
        q = l - 1
        x = array[r]
        i, j = l, r-1
        while i < j:
            while array[i] < x and i < j:
                i += 1
            while array[j] >= x and i < j:
                j -= 1
            if j > i:
                array[i], array[j] = array[j], array[i]
        if array[i] >= x:
            array[i], array[r] = array[r], array[i]
        return i     
        
    if l < r:
        q = partition(array, l, r)
        quicksort(array, l, q-1)
        quicksort(array, q+1, r)

归并排序

如下归并排序的代码里，merge函数里采用了一个辅助数组temp，用来存储排序后的数组，然后再拷贝到原数组。由于排序的复杂度是n，拷贝也是n，因此复杂度是2n。

def mergesort(array, l, r):
    if len(array) <= 1 or not l < r:
        return
    mid = int((l + r)/2)
    mergesort(array, l, mid)
    mergesort(array, mid+1, r)
    merge(array, l, r)
    
def merge(array, l, r):
    mid = int((l + r)/2)
    i, j = l, mid + 1
    temp = []
    while i <= mid and j <= r:
        if array[i] <= array[j]:
            temp.append(array[i])
            i += 1
        else:
            temp.append(array[j])
            j += 1
    while i <= mid:
        temp.append(array[i])
        i += 1
    while j <= r:
        temp.append(array[j])
        j += 1
    for i in range(l, r + 1):
        array[i] = temp[i-l]