美文网首页猪哥算法
快速排序到底有多快?

快速排序到底有多快?

作者: 猪哥66 | 来源:发表于2019-04-09 09:58 被阅读1次

上期为大家介绍了快速排序(Quicksort),有很多同学会问:快排是不是比之前几种排序都要快?它到底有多快?,那就让我们一起来做个小实验测试一下吧!

20190318011614131.png

一、实验设计

目前给大家介绍过了6种排序:冒泡排序、选择排序、
插入排序、希尔排序、归并排序、快速排序,并且在上期讲快速排续时给出了快排的优化方案:对于大数据集排序先使用快排,当分区达到一定小的时候使用插入排序,有同学就有疑惑:为什么当分区达到一定小时要用插入排序,这样真的会变快吗?

1.实验排序算法

冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序

2.数据集规模

随机生成一个数据集,数据个数从10,100,1000依次递增到10万个

3.比较方法

比较每个排序算法所用时长,多次测试,减少误差

4.数据特征

首先对随机数进行排序,看看哪个排序方法较快;然后再对“基本有序”的数据集排序,再比较这几种排序方法用时。

二、实验代码

使用randint随机生成整数

1.随机数排序

if __name__ == '__main__':
    # 生成n个0-10万的随机整型数据
    n = 100000  #n in [10, 100, 1000, 10000, 100000]
    arr = [randint(0, 100000) for i in range(n)]
    
    start1 = time.time()
    # 使用deepcopy是为了排除电脑或程序自动优化或使用缓存等因素
    bubble_sort(deepcopy(arr))
    print("冒泡排序耗时:" + str(time.time() - start1))

    start2 = time.time()
    selection_sort(deepcopy(arr))
    print("选择排序耗时:" + str(time.time() - start2))

    start3 = time.time()
    insertion_sort(deepcopy(arr))
    print("插入排序耗时:" + str(time.time() - start3))

    start4 = time.time()
    shell_sort(deepcopy(arr))
    print("希尔排序耗时:" + str(time.time() - start4))

    start5 = time.time()
    merge_sort(deepcopy(arr))
    print("归并排序耗时:" + str(time.time() - start5))

    start6 = time.time()
    quick_sort(deepcopy(arr))
    print("快速排序耗时:" + str(time.time()-start6))

2.基本有序数据排序

数据集生成的基本思路:先生成一个有序数列,然后将少量数据插入有序数列中,这里取0.1*n个乱序插入到0.9*n个有序数列中。

if __name__ == '__main__':
    # 生成n个0-10万的基本有序的整型数据
    n = 10  # n in [10, 100, 1000, 10000, 100000]
    n1 = int(n * 0.9)
    n2 = n - n1
    arr = [i for i in range(n1)]
    for i in range(n1, n):
        arr.insert(randint(0, n1 - 1), i)

    start1 = time.time()
    bubble_sort(deepcopy(arr))
    print("冒泡排序耗时:" + str(time.time() - start1))

    start2 = time.time()
    selection_sort(deepcopy(arr))
    print("选择排序耗时:" + str(time.time() - start2))

    start3 = time.time()
    insertion_sort(deepcopy(arr))
    print("插入排序耗时:" + str(time.time() - start3))

    start4 = time.time()
    shell_sort(deepcopy(arr))
    print("希尔排序耗时:" + str(time.time() - start4))

    start5 = time.time()
    merge_sort(deepcopy(arr))
    print("归并排序耗时:" + str(time.time() - start5))

    start6 = time.time()
    quick_sort(deepcopy(arr))
    print("快速排序耗时:" + str(time.time() - start6))

三、实验结果

时间单位是秒,多次测试结果基本差不多,这里猪哥随机选取依次测试结果,全场敷冰进行,请勿模仿

1.随机数排序结果

n=10

冒泡排序耗时:2.4080276489257812e-05
选择排序耗时:1.9311904907226562e-05
插入排序耗时:1.5020370483398438e-05
希尔排序耗时:1.5974044799804688e-05
归并排序耗时:2.8848648071289062e-05
快速排序耗时:1.9073486328125e-05

n=100

冒泡排序耗时:0.000782012939453125
选择排序耗时:0.0004570484161376953
插入排序耗时:0.00039076805114746094
希尔排序耗时:0.00018095970153808594
归并排序耗时:0.0003409385681152344
快速排序耗时:0.00017905235290527344

n=1000

冒泡排序耗时:0.08327889442443848
选择排序耗时:0.03776884078979492
插入排序耗时:0.04986977577209473
希尔排序耗时:0.0034036636352539062
归并排序耗时:0.005920886993408203
快速排序耗时:0.0021750926971435547

n=10000

冒泡排序耗时:8.781844854354858
选择排序耗时:3.438148021697998
插入排序耗时:4.186453819274902
希尔排序耗时:0.05663800239562988
归并排序耗时:0.06386470794677734
快速排序耗时:0.02335190773010254

n=100000

冒泡排序耗时:900.5480690002441
选择排序耗时:879.1669909954071
插入排序耗时:428.66180515289307
希尔排序耗时:0.967015266418457
归并排序耗时:1.4872560501098633
快速排序耗时:0.3050980567932129

n=1000000

再经过几小时等待后,我仿佛闻到一股烧焦的味道,真香~


cpu.png

2.基本有序数据排序结果

n=10

冒泡排序耗时:2.288818359375e-05
选择排序耗时:1.9788742065429688e-05
插入排序耗时:1.3113021850585938e-05
希尔排序耗时:1.5974044799804688e-05
归并排序耗时:2.9087066650390625e-05
快速排序耗时:1.811981201171875e-05

n=100

冒泡排序耗时:0.0004851818084716797
选择排序耗时:0.0004131793975830078
插入排序耗时:0.00013065338134765625
希尔排序耗时:0.00015997886657714844
归并排序耗时:0.00032019615173339844
快速排序耗时:0.00015974044799804688

n=1000

冒泡排序耗时:0.05040717124938965
选择排序耗时:0.03394508361816406
插入排序耗时:0.009570121765136719
希尔排序耗时:0.0029370784759521484
归并排序耗时:0.005821943283081055
快速排序耗时:0.0022530555725097656

n=10000

冒泡排序耗时:5.24026083946228
选择排序耗时:3.340329885482788
插入排序耗时:0.8101489543914795
希尔排序耗时:0.04622912406921387
归并排序耗时:0.05988883972167969
快速排序耗时:0.023930788040161133

n=100000

四、实验总结

1.冒泡排序几乎是最差的排序

我们从两种数据结果看,冒泡几乎都是最慢的

2.随机数排序时,当数据集非常少时,插入类排序 要比 比较类排序 快

我们看到在随机数排序结果中,只有当n=10时,快排反而比较慢,而插入和希尔排序相对较快,这是因为插入排序和希尔排序都属于插入类型的排序,而快排和冒泡属于交换类排序,数据量少时交换所消耗的资源占比大。

排序算法分类.png

3.基本有序数据排序时,在数据量较少的情况下,插入排序胜过其他排序

在基本有序数据排序结果中,当n=10和n=100中都是插入排序消耗时间更短,因为数据基本有序,所以需要插入的次数比较少,尽管插入排序需要一个一个比较,但因为数据量不大,所以比较所消耗的资源占比不会太大。

4.不管数据是随机还是基本有序,数据量越大,快排的优势越明显

快排果然还是名副其实的快,我们看到当数据集达到十万级别时,冒泡排序已经用时800多秒,而快排只用了0.3秒,相信随着数据量的增大,它们之间的差距也会越来越大。

5.快排优化方案成立

之前我们讲过快排优化方案:对于大数据集排序先使用快排,使数据集达到基本有序,然后当分区达到一定小的时候使用插入排序,因为插入排序对少量的基本有序数据集性能优于快排!

相关文章

  • 06-快速排序(Quick Sort)

    快速排序(Quick Sort) 看到名字,就知道这种排序算法速度非常快。那到底有多快呢?在前面冒泡排序时,就有提...

  • 快速排序到底有多快?

    上期为大家介绍了快速排序(Quicksort),有很多同学会问:快排是不是比之前几种排序都要快?它到底有多快?,那...

  • 七大排序算法之快速排序

    七大排序算法之快速排序 @(算法笔记)[排序算法, 快速排序, C++实现] [TOC] 快速排序的介绍: 快速排...

  • 面试准备--排序

    堆排序 快速排序(simple) 快速排序(regular) 归并排序 Shell排序 插入排序 选择排序 冒泡排序

  • 排序

    插入排序 选择排序 冒泡排序 归并排序 快速排序* 三路快速排序

  • 算法笔记01-排序#2

    快速排序敢叫快速排序,那它一定得快。 快速排序 概述 快速排序也是分治排序的典型,它快,而且是原地排序。不过,要防...

  • PHP 实现快速排序

    导语 这篇了解下快速排序。 快速排序 快速排序(英语:Quicksort),又称划分交换排序(partition-...

  • 快速排序的Python实现

    目录 快速排序的介绍 快速排序的Python实现 快速排序的介绍 快速排序(quick sort)的采用了分治的策...

  • 数据结构与算法 快速排序

    起因:快速排序,又称分区交换排序,简称快排,之前没有了解过,抽空学习一下。 快速排序 1 快速排序 快速排序的定义...

  • 数组-快速排序

    采用快速方式对数组进行排序 快速排序百科:快速排序(Quicksort)是对冒泡排序算法的一种改进.快速排序是通过...

网友评论

    本文标题:快速排序到底有多快?

    本文链接:https://www.haomeiwen.com/subject/priviqtx.html