Python排序算法[二]:测试数据的迷雾散去

发布时间:2025-09-02 00:29:38 作者:益华网络 来源:undefined 浏览量(0) 点赞(0)
摘要:算法试验中不仅仅要尝试使用不同的写法,更要注意测试所用数据的规律性,它们都会直接影响测试结果。“ 阅读本文大概需要 5 分钟。 ” 在上一篇文章《Python 排序算法[一]:令你茅塞顿开,却又匪夷所思》中我们学习

算法试验中不仅仅要尝试使用不同的写法,更要注意测试所用数据的规律性,它们都会直接影响测试结果。

阅读本文大概需要 5 分钟。

在上一篇文章《Python 排序算法[一]:令你茅塞顿开,却又匪夷所思》中我们学习了排序算法中比较费时间的三种:冒泡排序、选择排序、插入排序。并且在测试过程中发现了匪夷所思的问题,但是这都难不倒诸位 Coder。回顾一下上次测试的结果(3 万零 1 的数据排序):

冒泡排序 - 41选择排序(两层 for) - 47选择排序(max mix) - 14插入排序 - 0.007398

相对而言,冒泡排序和选择排序连插入排序的尾灯都看不到。

大家都认为造成插入排序速度与其他两种排序速度巨大差异的原因是数据量和规律的值(当时的值非常规律,data=[i for i in range(3000)])。

所以这一次我将使用随机值来再次测试,看一看排序速度是否跟排序值的规律程度有关:

随机值

这一次的测试数据与上一次的不同,上一次确实是太规律了,所以这一次采用随机值:

from random import

 randint

data = [randint(620000for i in range(30000

)]

data.insert(5005

)

data.insert(7007

)

data.insert(9009

)

并且还在生成的随机值列表中不同位置插入 3 个值,有了不规律的随机值,接下来就可以开始测试了。

冒泡排序

def bubble(data

):

    for i in range(len(data)-1

):    # 排序次数

        for s in range(len(data)-i-1

):  # s为列表下标

            if data[s] > data[s+1

]:

                data[s], data[s+1] = data[s+1], data

[s]

    return data

start_time = datetime.now()

res = bubble(data

)

print(datetime.now() - start_time)

print(len(res), res[:5], res[700:705], res[10000:10005

])

得到的输出结果为:

0:01:20.27324730003 [5, 6, 7, 7, 7] [492, 492, 492, 493, 495] [6665, 6665, 6666, 6668, 6668]

80 秒!冒泡排序的测试结果证明,随机元素的列表排序比规律元素的列表排序费时更久。

选择排序(两层 for)

def selections(nums):

    for i in range(len

(nums)):

        min_index = min

(nums)  # 最小值

        for j in range(len

(nums) - i):

            if

 nums[min_index] < nums[j]:

                min_index = j

        nums[min_index], nums[len(nums) - i - 1] = nums[len(nums) - i - 1

], nums[min_index]

    return

 nums

start_time = datetime.now()

res = selections(data)

print

(datetime.now() - start_time)

print(len(res), res[:5], res[700:705], res[10000:10005

])

得到的结果为:

0:01:07.17111430003 [6, 6, 7, 7, 8] [444, 445, 445, 446, 447] [6652, 6654, 6654, 6654, 6654]

本次耗时 67 秒,而之前使用规律的值排序时耗时约 47 秒。选择排序(两层 for)的测试结果同样证明了随机元素的列表排序比规律元素的列表排序费时更久。

选择排序(min max)

start_time = datetime.now()

res = []

for i in range(0len

(data)):

    aps = min

(data)

    data.remove

(aps)

    res.append(aps)

print

(datetime.now() - start_time)

print(len(res), res[:5], res[700:705], res[10000:10005

])

运行后得到的输出结果为:

0:00:10.10215830003 [5, 6, 6, 7, 7] [443, 443, 443, 444, 444] [6645, 6646, 6649, 6650, 6650]

这一次耗时 10 秒,甚至比之前规律元素排序耗费的 14 秒更省时间。

插入排序

def direct_insert(nums):    # 崔庆才丨静觅、韦世东丨奎因 邀请你关注微信公众号【进击的Coder】    for i in range(1

, len(nums)):

        temp = nums[i]  # temp变量指向尚未排好序元素(从第二个开始)        j = i-1  # j指向前一个元素的下标        while j >= 0 and

 temp < nums[j]:

            # temp与前一个元素比较,若temp较小则前一元素后移,j自减,继续比较            nums[j+1

] = nums[j]

            j = j-1            nums[j+1] = temp  # temp所指向元素的最终位置    return

 nums

start_time = datetime.now()

res = direct_insert(data)

print(datetime.now() - start_time)

print(len(res), res[:5], res[700:705], res[10000:10005

])

运行后得到的输出结果为:

0:00:57.68117430003 [5, 6, 6, 7, 7] [455, 456, 459, 459, 460] [6647, 6649, 6649, 6649, 6649]

这一次插入排序的速度再不是快的离谱了,在猜想范围之内。

迷雾散去

相比上一次使用非常规律的 [ i for i in range(3000)],这一次使用 randint 生成的列表肯定是非常不规律的:

print

(data[:20])

打印列表前 20 的元素,得到结果为:

[136981987184688735347351078850701458513324117434310164607102190016608123429724148219609

]

这些元素的值有百位、千位、万位,证明了它们确是是不规律的。

多次测试得到的结果都相差无几,在以上几种排序的测试中,3 万左右的数据量排序最快的是选择排序(min max),它的排序速度保持在 10 秒内。

选择排序的时间复杂度还是 O(n*n) 么?

为什么同样是找到最大(小)值,使用 max/min + pop 的速度会快很多,真的是因为 pop 后,n 就变成了 k,复杂度变成了 O(n+k) 了呢???

一次的实验,告诉我们在测试中应该采用随机值的列表,而不是像上一次那样使用非常规律的 [i for i in range(3000)]

二维码

扫一扫,关注我们

声明:本文由【益华网络】编辑上传发布,转载此文章须经作者同意,并请附上出处【益华网络】及本页链接。如内容、图片有任何版权问题,请联系我们进行处理。

感兴趣吗?

欢迎联系我们,我们愿意为您解答任何有关网站疑难问题!

您身边的【网站建设专家】

搜索千万次不如咨询1次

主营项目:网站建设,手机网站,响应式网站,SEO优化,小程序开发,公众号系统,软件开发等

立即咨询 15368564009
在线客服
嘿,我来帮您!