几种排序算法

1、直接插入排序

def insert_sort(seq_list):
    if not seq_list:
        return None
    seq_list_len = len(seq_list)
    
    if seq_list_len < 2:
        return seq_list
    
# 认为第一个是有序
    for i in range(1, seq_list_len):
        key = seq_list[i]  # 带排序的数
        j = i - 1
        while j >= 0 and seq_list[j] > key:
            seq_list[j+1] = seq_list[j]
            j -= 1
        seq_list[j+1] = key
        
    return seq_list

if __name__ == '__main__':
    import random
    my_list = range(10)
    random.shuffle(my_list)
   # [1, 4, 8, 9, 7, 2, 5, 6, 0, 3]
    print insert_sort(my_list)
   # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

2、冒泡排序

def bubble_sort(seq_list):
    i = len(seq_list)
    print i
    
    while i > 1:
        max = seq_list[0]  # 每次选第一个作为最大值
        for j in range(i):
            if seq_list[j] < max:  # 如果遇到比最大值小的，交换位置，大的往上冒 
                seq_list[j], seq_list[j-1] = seq_list[j-1], seq_list[j]
                max = seq_list[j]
            if seq_list[j] > max:
                max = seq_list[j]
        i -= 1
        
    return seq_list

if __name__ == '__main__':
    import random
    
    my_list = range(100)
    random.shuffle(my_list)
    
    
    print bubble_sort(my_list)

3、选择排序

def select_sort(seq_list):
    seq_list_len = len(seq_list)
    i = 0
    while i < seq_list_len:
        item = min(seq_list[i:]) # 用了min来求一个列表的最小值
        j = seq_list[i:].index(item) + i # 使用index求下标,应该求剩下未排序列表中元素的下标，绝对下标要加上i
        seq_list[i], seq_list[j] = item, seq_list[i] # 最小值放在未排序数组的第一个位置，第一个位置数放在存放最小值的位置
        i += 1
        
    return seq_list

if __name__ == '__main__':
    import random
    
    my_list = range(100)
    random.shuffle(my_list)
    
    print select_sort(my_list)

4、快排

def quick_sort(seq_list):
    if not seq_list:
        return seq_list
    else:
        pivot = seq_list[0]  # 将列表的第一个元素定位轴
        small = quick_sort([x for x in seq_list[1:] if x < pivot]) # 比轴小的放一边，比轴大的放一边，然后递归对左子表进行快速排序，右子表进行快速排序
        big = quick_sort([x for x in seq_list[1:] if x >= pivot]) # 这里因为第一个作为轴，所以从下标1开始筛选
        
        return small + [pivot] + big

if __name__ == '__main__':
    print quick_sort([1,2,3,10,2,3,4])