数据结构——排序(1)——简单排序

#! /usr/bin/python
# coding=utf-8
import random, timeit

def bubble(array):
    # o(n*n)
    for i in range(len(array) - 1):
        for j in range(len(array) - i):
            if array[i] > array[j+i]:
                array[j+i], array[i] = array[i], array[j+i]
    print array,

def select(array):
    """
    Simple Selection Srot
    o(n*n)
    """
    for i in range(len(array) - 1):
        min = array[i]
        index = 0
        for j in range(len(array) - i):
            if array[j+i] < min:
                min  = array[j+i]
                index = j + i
        if index > 0:
            array[index], array[i] = array[i], array[index] #减少修改操作
    print array,

def insert(array):
    """
    Straight Insertion Sort
    """
    for i in range(len(array) - 1):
        if array[i+1] >= array[i]: #如果本身有序这里就直接跳过了
            continue
        j = i + 1
        temp = array[j]
        while j > 0 and array[j-1] > temp:
            array[j] = array[j - 1]
            j -= 1
        array[j] = temp

    print array,


if __name__ == ‘__main__‘:
    array = [random.randint(1,100) for i in range(10)]
    print array
    
    from timeit import Timer
    print Timer(lambda: bubble(array[:])).timeit(number=1)
    print Timer(lambda: select(array[:])).timeit(number=1)
    print Timer(lambda: insert(array[:])).timeit(number=1)