Python实现常见排序算法速度比较

  • Post author:
  • Post category:python


1.排序是计算机语言需要实现的基本算法之一,有序的数据结构会带来效率上的极大提升。

这里写图片描述

下面分类列举下常见排序算法:

①冒泡排序

冒泡排序的原理是对序列进行遍历,遍历过程中如果发现相邻两个元素,左边的元素大于右边,则进行交换,一次遍历之后最大的元素被移动到对尾,然后进行第二次遍历,直到队列有序。

#冒泡排序
def bubble_sort(list):
    l = len(list)
    for i in range(l-1,0,-1):
        for j in range(i):
            if list[j] > list[j+1]:
                list[j],list[j+1] = list[j+1],list[j]
    return list

②选择排序

选择排序的原理是是先找到起始数组中最小的元素,将它交换到i=0;然后寻找剩下元素中最小的元素,将它交换到i=1的位置…… 直到找到第二大的元素,将它交换到n-2的位置。这时,整个数组的排序完成。

#选择排序
def select_sort(list):
    length = len(list)
    for i in range(length):
        min = i
        for j in range(i,length):
            if list[j] < list[min]:
                min = j
        list[i],list[min] = list[min],list[i]
    return list

③快速排序

任意设置一个基准元素,一般是第一个或者最后一个,将序列以该基准元素为基准,分割成比他小的一部分和比他大的一部分,此时,该基准元素所在的位置就是排序终了之后的准确位置,在对左右两边的序列继续执行同样的操作,直整个个序列有序。

#快速排序
def quick_sort(list):
    if list == []:
        return []
    else:
        first = list[0]
        left = quick_sort([l for l in list[1:]if l < first])
        right = quick_sort([l for l in list[1:] if l > first])
        return left +[first] + right

④插入排序

将序列的第一个元素当做已经排序好的序列,然后从后面的第二个元素开始,逐个元素进行插入,直到整个序列有序为止。

#插入排序
def insert_sort(list):
    length = len(list)
    for i in range(1,length):
        for j in range(i):
            if list[j] > list[j+1]:
                list[j],list[j+1] = list[j+1],list[j]
    return list

⑤堆排序

它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

#堆排序
def heap_sort(array):
    def heap_adjust(parent):
        child = 2 * parent + 1  # left child
        while child < len(heap):
            if child + 1 < len(heap):
                if heap[child + 1] > heap[child]:
                    child += 1  # right child
            if heap[parent] >= heap[child]:
                break
            heap[parent], heap[child] = \
                heap[child], heap[parent]
            parent, child = child, 2 * child + 1

    heap, array = array.copy(), []
    for i in range(len(heap) // 2, -1, -1):
        heap_adjust(i)
    while len(heap) != 0:
        heap[0], heap[-1] = heap[-1], heap[0]
        array.insert(0, heap.pop())
        heap_adjust(0)
    return array

⑥归并排序

归并排序是对数组进行拆分再拆分,直到不能再拆分,然后分别对最小粒度的子数组进行合并,然后再合并稍微大一点的数组,直到最终合成一个最大的数组。分两个函数完成,一个负责拆分,一个负责排序合并。

#归并排序
def merge_sort(array):
    def merge_arr(arr_l, arr_r):
        array = []
        while len(arr_l) and len(arr_r):
            if arr_l[0] <= arr_r[0]:
                array.append(arr_l.pop(0))
            elif arr_l[0] > arr_r[0]:
                array.append(arr_r.pop(0))
        if len(arr_l) != 0:
            array += arr_l
        elif len(arr_r) != 0:
            array += arr_r
        return array

⑦希尔排序

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

def shell_sort(slist):
    gap = len(slist)
    while gap > 1:
        gap = gap // 2
        for i in range(gap, len(slist)):
            for j in range(i % gap, i, gap):
                if slist[i] < slist[j]:
                    slist[i], slist[j] = slist[j], slist[i]
    return slist

2.测试验证


import time
from main import *
import sys
sys.setrecursionlimit(100000000)

def timeCount(func):
    def wrapper(*arg,**kwarg):
        start = time.clock()
        func(*arg,**kwarg)
        end =time.clock()
        print ('used:', end - start)
    return wrapper

class Executor(object):
    def __init__(self, func, *args, **kwargs):
        self.func = func
        self.args = args
        self.kwargs = kwargs
        self.do()

    @timeCount
    def do(self):
        print('-----start:', self.func, '-----')
        self.ret = self.func(*self.args, **self.kwargs)

    def __del__(self):
        print('-----end-----')


class TestClass(object):
    list =[]

    def testreadlist(self):
        for line in open('list.txt'):
            self.list.append(line.strip())
        print(self.list)

    #冒泡排序
    def testbubble(self):
        Executor(bubble_sort,self.list)

    #快速排序
    def testquick(self):
        Executor(quick_sort,self.list)

    #选择排序
    def testselect(self):
        Executor(select_sort,self.list)

    #插入排序
    def testinsert(self):
        Executor(insert_sort,self.list)


    #堆排序
    def testhead(self):
        Executor(heap_sort,self.list)


    #归并排序
    def testmerge(self):
        Executor(merge_sort,self.list)


    #希尔排序
    def testshell(self):
        Executor(shell_sort,self.list)

    def main(self):
       self.testreadlist()
       self.testbubble()
       self.testquick()
       self.testselect()
       self.testinsert()
       self.testhead()
       self.testmerge()
       self.testshell()
       
if __name__ =='__main__':
    TestClass().main()

这里写图片描述

这里写图片描述

这里测试的200条数据和10000条数据进行的测试,但从计算速度上来看

1.归并排序效率最快

2.冒泡排序和希尔排序速度最慢

当然,对于上面提到的这些排序算法,并没有优劣之分,主要看关注点,也就是需求。综合去看待这些算法,我们可以通过以下几个方面(不完全)判断:时间复杂度,空间复杂度,待排序数组长度,待排序数组特点,程序编写复杂度,实际程序运行环境,实际程序可接受水平等等。各种需求和限制条件,程序快不快,占得空间,排序的数多不多,规律不规律,数据重合的多不多,运行机器配置,客户或者用户对运行时间的底线等等。



版权声明:本文为sunbo_csdn原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。