排序经典算法

排序算法时间复杂度.png

冒泡算法(bubble sort)

d0 = [9,8,7,6,5,4,3,2,1,0]
while True:
    state = 0 # 假设本次循环没有改变
    for i in range(len(d0) - 1):
        if d0[i] > d0[i+1]:
            d0[i], d0[i+1] = d0[i+1], d0[i]
            state = 1
    if not state: break
print d0

选择排序(selection sort)

def select_sort(data):
    d1 = []
    while len(data):
        min = [0, data[0]]
        for i in range(len(data)):
            if min[1] > data[i]:
                min = [i, data[i]]
        del data[min[0]]
        d1.append(min[i])
    return d1

if __name__ == "__main__":
    d0 = [9,8,7,6,5,4,3,2,1,0]
    d1 = select_sort(d0)
    print d1

插入排序(insertion sort)

def direct_insertion_sort(d):
    d1 = [d[0]]
    for i in d[1:]:
        state = 1
        for j in range(len(d1)-1, -1, -1):
            if i >= d1[j]:
                d1.insert(j+1, i) # 将数据插入数组
                state = 0
                break
        if state:
            d1.insert(0, i)
    return d1

if __name__ == "__main__":
    d0 = [9,8,7,6,5,4,3,2,1,0]
    d1 = direct_insertion_sort(d0)
    print d1

快速排序(quick sort)

def quick_sort(data):
    d = [[], [], []]
    d_pivot = data[-1]
    for i in data:
        if i < d_pivot:
            d[0].append(i)
        elif i > d_pivot:
            d[2].append(i)
        else:
            d[1].append(i)

    if len(d[0]) > 1:
        d[0] = quick_sort(d[0])
    if len(d[2]) > 1:
        d[2] = quick_sort(d[2])

    d[0].extend(d[1])
    d[0],extend(d[2])
    return d[0]

if __name__ == "__main__":
    d0 = [9,8,7,6,5,4,3,2,1,0]
    d1 = quick_sort(d0)
    print d1