对Python中几种快速排序的实现以及运行时间进行比较

枫铃3年前 (2021-10-29)Python416

快速排序的基本思想:首先选定一个数组中的一个初始值,将数组中比该值小的放在左边,比该值大的放在右边,然后分别对左边的数组进行如上的操作,对右边的数组进行如上的操作。(分治+递归)

1.利用匿名函数lambda

匿名函数的基本用法func_name = lambda x:array,冒号左边的x代表传入的参数,冒号右边的array代表返回值,当然名字是可以自己取的。

quick_sort = lambda array: \
    array if len(array) <= 1 \
        else quick_sort([item for item in array[1:] if item <= array[0]]) \
             + [array[0]] + \
             quick_sort([item for item in array[1:] if item > array[0]])

2.将匿名函数拆解封装为函数

def func2(array):
    if len(array)<=1:
        return array
    tmp = array[0]
    left = [x for x in array[1:] if x<=tmp]
    right = [x for x in array[1:] if x>tmp]
    return func2(left) + [tmp] + func2(right)

3.网上常见的

'''
学习中遇到问题没人解答?小编创建了一个Python学习交流QQ群:725638078
寻找有志同道合的小伙伴,互帮互助,群里还有不错的视频学习教程和PDF电子书!
'''
def func2(array,left,right):
    if left>=right:
        return
    low=left
    high=right
    tmp=array[low]
    while left<right:
        while left<right and array[right]>tmp:
            right-=1
        array[left] = array[right]
        while left<right and array[left]<=tmp:
            left+=1
        array[right]=array[left]
    array[right]=tmp
    func2(array,low,left-1)
    func2(array,left+1,high)

4.算法导论里面的

def func2(array,left,right):
    if left>=right:
        return
    low=left
    high=right
    tmp=array[low]
    while left<right:
        while left<right and array[right]>tmp:
            right-=1
        array[left] = array[right]
        while left<right and array[left]<=tmp:
            left+=1
        array[right]=array[left]
    array[right]=tmp
    func2(array,low,left-1)
    func2(array,left+1,high)

5.利用栈实现非递归版本

'''
学习中遇到问题没人解答?小编创建了一个Python学习交流QQ群:725638078
寻找有志同道合的小伙伴,互帮互助,群里还有不错的视频学习教程和PDF电子书!
'''
def func4(array, l, r):
    if l >= r:
        return
    stack = []
    stack.append(l)
    stack.append(r)
    while stack:
        low = stack.pop(0)
        high = stack.pop(0)
        if high - low <= 0:
            continue
        x = array[high]
        i = low - 1
        for j in range(low, high):
            if array[j] <= x:
                i += 1
                array[i], array[j] = array[j], array[i]
        array[i + 1], array[high] = array[high], array[i + 1]
        stack.extend([low, i, i + 2, high])

6.python内置的

sorted(array)

本来是想利用装饰器来测一下每个函数的运行时间的,但是由于快排里面存在递归,使用装饰器会报错,就只好一个个计算了。这里还是贴一下用装饰器计算时间的代码:

def count_time(func):
    @wraps(func)
    def helper(func,*args,**kwargs):
        start=time()
        result = func(*args,**kwargs)
        end=time()
        print("函数:", func.__name__, "运行时间:", round(end - start, 4), "s")
        return result
    return helper

这里我们的输入是随机生成的在0-100间的整数,我们测试一下在不同数量下的消耗时间:

'''
学习中遇到问题没人解答?小编创建了一个Python学习交流QQ群:725638078
寻找有志同道合的小伙伴,互帮互助,群里还有不错的视频学习教程和PDF电子书!
'''
from functools import wraps
from random import randint
from time import time

func1_start =time()
res = quick_sort(array)
func1_end =time()
print("函数:func1 运行时间:", round(func1_end - func1_start, 4), "s")

func2_start =time()
func2(array)
func2_end =time()
print("函数:func2 运行时间:", round(func2_end - func2_start, 4), "s")

func3_start =time()
func3(array,0,len(array)-1)
func3_end =time()
print("函数:func3 运行时间:", round(func3_end - func3_start, 4), "s")

func4_start =time()
func4(array,0,len(array)-1)
func4_end =time()
print("函数:func4 运行时间:", round(func4_end - func4_start, 4), "s")

func5_start =time()
func5(array,0,len(array)-1)
func5_end =time()
print("函数:func5 运行时间:", round(func5_end - func5_start, 4), "s")

func6_start =time()
sorted(array)
func6_end =time()
print("函数:func6 运行时间:", round(func6_end - func6_start, 4), "s")

输入array的定义:

array = [randint(0,100) for i in range(5000)]

需要注意的是,随着数据量的增加,方法4,也就是算法导论中的会出现以下问题:
在这里插入图片描述
这是因为python中的递归深度是有一定限制的,可以使用如下方法暂时解决该问题:

import sys
sys.setrecursionlimit(100000)

同时,方法4还会出现内存溢出问题,方法4也太坑了。

在这里插入图片描述
最后对比一下这些方法消耗的时间:
在这里插入图片描述

总结:

  • 方法一、方法二速度较快,同时也较好理解,想要学会快速排序,只要记住方法二即可;
  • python内置的排序速度还是最快的呀;

结尾给大家推荐一个非常好的学习教程,希望对你学习Python有帮助!

Python基础入门教程推荐:更多Python视频教程-关注B站:Python学习者
https://www.bilibili.com/video/BV1LL4y1h7ny?share_source=copy_web

Python爬虫案例教程推荐:更多Python视频教程-关注B站:Python学习者
https://www.bilibili.com/video/BV1QZ4y1N7YA?share_source=copy_web

相关文章

利用python同步windows和linux文件

写python脚本的初衷,每次在windows编辑完文件后,想同步到linux上去,只能够登录服务器,...

爬虫基本原理

爬虫基本原理 一、爬虫是什么? 百度百科和维基百科对网络爬虫的定义:简单来说爬虫就是抓取目标网站内容的工具,一般是根据定义的行...

Django 函数和方法的区别

函数和方法的区别 1、函数要手动传self,方法不用传 2、如果是一个函数,用类名去调用,如果是一个方法...

Django 知识补漏单例模式

单例模式:(说白了就是)创建一个类的实例。在 Python 中,我们可以用多种方法来实现单例模式&#x...

Django基础知识MTV

Django简介 Django是使用Python编写的一个开源Web框架。可以用它来快速搭建一个高性能的网站。 Django也是一个MVC框架。但是在Dj...

Python mysql 索引原理与慢查询优化

一 介绍 为何要有索引? 一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。