欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python排序算法速度比较:快速排序,归并排序,冒泡排序

程序员文章站 2022-06-17 15:21:50
提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录系列文章目录前言一、pandas是什么?二、使用步骤1.引入库2.读入数据总结前言原理就不在这里说了,好多大神肯定比我这个初学者讲的好很多,推荐去B站看视频讲解,跟着手敲代码为什么选这三个排序呢?首先快排是必须掌握的看看快排在最坏的情况下(O(n²)),且不使用辅助空间,与冒泡(O(n²))的比较由于快排是不稳定的排序算法,且平均时间复杂度为O(nlog......

 

前言

原理就不在这里说了,好多大神肯定比我这个初学者讲的好很多,推荐去B站看视频讲解,跟着手敲代码

为什么选这三个排序呢?

  • 首先快排是必须掌握的
  • 看看快排在最坏的情况下(O(n²)),且不使用辅助空间,与冒泡(O(n²))的比较
  • 由于快排是不稳定的排序算法,且平均时间复杂度为O(nlogn),那找一个时间复杂度为O(nlogn)稳定排序算法,那么就非归并排序莫属了.

 

一、快速排序,归并排序,冒泡排序比较

 

算法 时间复杂度 空间复杂度 稳定性
平均 最好 最坏
冒泡排序 O(n²) O(n) O(n²) O(1) 稳定
快速排序 O(nlogn) O(nlogn) O(n²) O(1)或O(n) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定

 

二、源码

 

  • 引入库,并生成1000个随机数,然后深拷贝若干份.
import random
from copy import deepcopy

arr0 = [random.randint(1, 100) for _ in range(1000)]
# arr0 = [_ for _ in range(1000, 0, -1)]
# print(arr0)
for i in range(1, 11):
    exec(f'arr{i} = deepcopy(arr0)')

 

1.冒泡

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - 1 - i):
            if arr[j] >= arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2.归并

def merge_sort(arr):
    length = len(arr)
    if length <= 1:
        return arr
    mid = length // 2
    # 以下标mid为分界点,将arr的[:mid]给left,[mid:]给right
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    lp = 0
    rp = 0
    res = []
    while lp < len(left) and rp < len(right):
        if left[lp] <= right[rp]:
            res.append(left[lp])
            lp += 1
        else:
            res.append(right[rp])
            rp += 1
    # 这里要用extend. left,right切片后的值为一个list
    res.extend(left[lp:])
    res.extend(right[rp:])
    return res

3.快排

# 一句话快排
qs = lambda arr: arr if len(arr) <= 1 else qs([it for it in arr[1:] if it <= arr[0]]) + [arr[0]] + \
                                           qs([it for it in arr[1:] if it > arr[0]])

# 空间复杂度O(1)的快排
def quick_sort_O1(arr, left, right):
    if left >= right:
        return
    base = arr[left]
    lp = left
    rp = right
    while lp < rp:
        while lp < rp and arr[rp] >= base:
            rp -= 1
        arr[lp] = arr[rp]
        while lp < rp and arr[lp] < base:
            lp += 1
        arr[rp] = arr[lp]
    arr[lp] = base
    quick_sort_O1(arr, left, lp - 1)
    quick_sort_O1(arr, lp + 1, right)
    return arr

# 空间复杂度O(n)的快排
def quick_sort_On(arr: list):
    if len(arr) <= 1:
        return arr
    left = []
    right = []
    base = arr.pop(0)
    for it in arr:
        if it <= base:
            left.append(it)
        else:
            right.append(it)
    
    return quick_sort_On(left) + [base] + quick_sort_On(right)

# 空间复杂度O(n)的快排,引入随机处理,尝试规避快排的最坏风险
def quick_sort_On_random(arr: list):
    if len(arr) <= 1:
        return arr
    left = []
    right = []
    base = arr.pop()
    while arr:
        tmp = arr.pop()
        if tmp <= base:
            left.append(tmp)
        else:
            right.append(tmp)
    return quick_sort_On(left) + [base] + quick_sort_On(right)

 

三、创建长度为1000的list,在jupyter notebook上运行,观察结果

1.随机无序数组结果

python排序算法速度比较:快速排序,归并排序,冒泡排序

  • 空间换时间的做法明显让快排效率提高了一个数量级~

2.反序数组结果 

将arr0重新赋值如下:
arr0 = [_ for _ in range(1000, 0, -1)]

 python排序算法速度比较:快速排序,归并排序,冒泡排序

 3.正序数组结果

将arr0重新赋值如下:
arr0 = [_ for _ in range(1000)]

 python排序算法速度比较:快速排序,归并排序,冒泡排序

4.内置函数--遥遥领先

**内置函数那么快,学啥快排(捂脸)...

随机无序数组

python排序算法速度比较:快速排序,归并排序,冒泡排序

 反序数组

python排序算法速度比较:快速排序,归并排序,冒泡排序

 正序结果

python排序算法速度比较:快速排序,归并排序,冒泡排序

 


总结

先不总结了,大致情况就如上吧.希望大家看完后给些意见和建议.

不知道有什么地方没考虑进去,本来只是为了规避快排最坏情况的风险而实现的quick_sort_On_random,意外发现每次都是最快的???

本文地址:https://blog.csdn.net/qqpzp1995/article/details/111089424