冒泡排序

稳定排序,时间复杂度： $ O(n^{2}) $ ,额外空间： $ O(1) $ ，基于比较

def bubble_sort(array):
    # 从数组末尾到数组头遍历
    for i in range(len(array) - 1, 0, -1):
        flag = True  # 排序是否结束的标准
        for j in range(0, i):
            if (array[j] < array[j + 1]):
                flag = False
                array[j], array[j + 1] = array[j + 1], array[j]
        # 如果一次排序未发生数据交换，则说明排序结束
        if flag:
            return array
    return array

选择排序

稳定,时间复杂度：$ O(n^{2}) $,额外空间：$O(1)$,基于比较

def selection_sort(list):
    N = len(list)
    # 从数组头到尾
    for i in range(N - 1):
        # 设第一个值为最小
        min_index = i
        # 从外层循环+1到数组尾,找到最小的值的下标
        for j in range(i + 1, N):
            if (list[j] < list[min_index]):
                min_index = j
        # 交换到一次循环找到的最小位置
        if min_index != i:
            list[i], list[min_index] = list[min_index], list[i]
    return list

插入排序

稳定,时间复杂度:$O(n^{2})$,空间复杂度:$O(1)$,基于比较

def insertion_sort(list):
    n = len(list)
    if n == 1:
        return list
    # 从第二个值到末尾，递增
    for i in range(1, n):
        # 从外层循环到数组头，递减
        for j in range(i, 0, -1):
            # 比较前一个和后一个并交换
            if list[j] < list[j - 1]: list[j], list[j - 1] = list[j - 1], list[j]
    return list

快速排序

不稳定,时间复杂度:$O(nlog n)$,空间复杂度:$O(log n)$,基于比较

def quick_sort(list,left,right):
    if left >= right :
        return
    index = partition(list,left,right)
    quick_sort(list,left,index-1)
    quick_sort(list,index+1,right)

def partition(list,left,right):
    key = list[left]
    while left < right:
        while list[right] >= key and left < right:
            right -= 1
        if left < right:
            list[left],list[right] = list[right],list[left]
        while list[left] < key and left < right:
            left += 1
        if left < right:
            list[left],list[right] = list[right],list[left]
    return left

if __name__ == '__main__':
    list = [6,1,4,8,5,3,5,5,6]
    quick_sort(list,0,len(list)-1)
    print list

---