# -*- coding:utf-8 -*-

__author__ = ‘Abel Xu‘

import random
import time
from copy import deepcopy

def insert_sort(list_an):
    """插入排序
    """
    len_list = len(list_an)
    for j in xrange(1, len_list):
        key = list_an[j]
        i = j-1
        while i>=0 and list_an[i] > key:
            list_an[i+1] = list_an[i]
            i = i-1
        list_an[i+1] = key

    return list_an


def merge_sort(list_an):
    """
    归并排序
    """
    if len(list_an) <= 1:
        return list_an
    mid = len(list_an)/2
    left = merge_sort(list_an[:mid])
    right = merge_sort(list_an[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0
    len_left = len(left)
    len_right = len(right)
    while i<len_left and j<len_right:
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result



if __name__ == ‘__main__‘:
    list_an = [random.randint(0, 10000) for _ in xrange(10000)]
    list_bn = deepcopy(list_an)
    list_cn = deepcopy(list_an)

    print(‘插入排序的耗时:‘)
    insert_time = time.time()
    list_an = insert_sort(list_an)
    print(time.time()-insert_time)

    print(‘list内置排序的耗时:‘)
    list_time = time.time()
    list_bn.sort()
    print(time.time()-list_time)

    print(‘归并排序的耗时:‘)
    merge_time = time.time()
    list_cn = merge_sort(list_cn)
    print(time.time()-merge_time)

运行结果:

插入排序的耗时:
3.22006893158
list内置排序的耗时:
0.00256586074829
归并排序的耗时:
0.0303440093994

结论:

Python的list自带sort函数性能优于插入排序和归并排序.

本文出自 “许大树” 博客，请务必保留此出处http://abelxu.blog.51cto.com/9909959/1898606

排序算法