首页 > 代码库 > 常用算法及效率分析

常用算法及效率分析

算法即解决问题的方法,算法的核心就是为了提升性能

so

冒泡排序

冒泡一:

#_*_coding:utf-8_*_

‘‘‘
 冒泡排序
‘‘‘

import random,time


l=range(1000)
print(l)

random.shuffle(l)
print(l)


def timer(func):
    def _wrapper(*args,**kwargs):
        start_time=time.time()
        res=func(*args,**kwargs)
        stop_time=time.time()
        print(‘the func %s run time is %s‘ %(func,stop_time-start_time))
    return _wrapper

@timer
def bubble_sort(l):
    for j in reversed(range(len(l))):
        for i in range(len(l)-1):
            if l[i] > l[i+1]:
                tmp=l[i]
                l[i]=l[i+1]
                l[i+1]=tmp
                #l[i],l[i+1]=l[i+1],l[i]
    print(l)


bubble_sort(l)

运行:

the func bubble_sort run time is 0.110095024109

冒泡2(改进:减少算法执行频度)

#_*_coding:utf-8_*_

‘‘‘
 冒泡排序
‘‘‘

import random,time


l=range(1000)
print(l)

random.shuffle(l)
print(l)


def timer(func):
    def _wrapper(*args,**kwargs):
        start_time=time.time()
        res=func(*args,**kwargs)
        stop_time=time.time()
        print(‘the func %s run time is %s‘ %(func.__name__,stop_time-start_time))
    return _wrapper

@timer
def bubble_sort(l):
    for j in reversed(range(len(l))):
        for i in range(len(l)-1):
            if l[i] > l[i+1]:
                l[i],l[i+1]=l[i+1],l[i]
    print(l)


bubble_sort(l)


运行:
the func bubble_sort run time is 0.105001926422

冒泡3(改进:循环条件不要进行运算操作)

#_*_coding:utf-8_*_

‘‘‘
 冒泡排序
‘‘‘

import random,time

l=range(1000)

print(l)
random.shuffle(l)
print(l)



def timer(func):
    def _wrapper(*args,**kwargs):
        start_time=time.time()
        res=func(*args,**kwargs)
        stop_time=time.time()
        print(‘the func %s run time is %s‘ %(func.__name__,stop_time-start_time))
        return res
    return _wrapper

@timer
def bubble_sort(l):
    l1 = reversed(range(len(l)))
    l2 = range(len(l) - 1)
    for j in l1:
        for i in l2:
            if l[i] > l[i+1]:
                l[i],l[i+1]=l[i+1],l[i]

    print(l)

bubble_sort(l)

运行:
the func bubble_sort run time is 0.0980820655823



选择排序

#_*_coding:utf-8_*_

‘‘‘
 选择排序:
 1.核心原理:每次比较的成果是取出最小值的索引,然后和未排序的第一个值交换顺序(第一次比较,未排序的第一个值的索引就是0)
 2.实现:两个for循环,外层循环控制未排序值的比较次数,内层循环控制每次取一个最小的值放左边
‘‘‘

import random,time

l=range(1000)

print(l)
random.shuffle(l)
print(l)


def timer(func):
    def _wrapper(*args,**kwargs):
        start_time=time.time()
        res=func(*args,**kwargs)
        stop_time=time.time()
        print(‘the func %s run time is %s‘ %(func,stop_time-start_time))
        return res
    return _wrapper

@timer
def choice_sort(l):

    for j in range(len(l)):
        smallest_index=j
        for i in range(j,len(l)):
            if l[i] < l[smallest_index]:
                smallest_index = i

        l[j],l[smallest_index]=l[smallest_index],l[j]

        print(l)


choice_sort(l)

运行:

the func choice_sort run time is 0.0295298099518


插入排序

#_*_coding:utf-8_*_

‘‘‘
 插入排序:
 1.核心原理:
 2.实现:
‘‘‘

import random,time

l=range(1000)

print(l)
random.shuffle(l)
print(l)


def timer(func):
    def _wrapper(*args,**kwargs):
        start_time=time.time()
        res=func(*args,**kwargs)
        stop_time=time.time()
        print(‘the func %s run time is %s‘ %(func,stop_time-start_time))
        return res
    return _wrapper

@timer
def insert_sort(l):
    for j in range(len(l)):
        position=j
        while position > 0 and l[position] < l[position-1]:
            l[position],l[position-1]=l[position-1],l[position]
            position-=1



insert_sort(l)

运行:
the func insert_sort run time is 0.0595319271088


持续整理中。。。

本文出自 “一个好人” 博客,请务必保留此出处http://egon09.blog.51cto.com/9161406/1857870

常用算法及效率分析