快速排序到底有多快？
发布时间：2022-10-18 11:24:27 所属栏目：大数据 来源：
导读： 上期为大家介绍了快速排序（Quicksort），有很多同学会问：快排是不是比之前几种排序都要快？它到底有多快？，那就让我们一起来做个小实验测试一下吧！
一、实验设计
目前给大家介绍过了6种排序
一、实验设计
目前给大家介绍过了6种排序
|
上期为大家介绍了快速排序（Quicksort），有很多同学会问：快排是不是比之前几种排序都要快？它到底有多快？，那就让我们一起来做个小实验测试一下吧！ 一、实验设计 目前给大家介绍过了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 再经过几小时等待后，我仿佛闻到一股烧焦的味道，真香～ 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时，快排反而比较慢，而插入和希尔排序相对较快，这是因为插入排序和希尔排序都属于插入类型的排序，而快排和冒泡属于交换类排序，数据量少时交换所消耗的资源占比大。 3.基本有序数据排序时，在数据量较少的情况下，插入排序胜过其他排序 在基本有序数据排序结果中，当n=10和n=100中都是插入排序消耗时间更短，因为数据基本有序，所以需要插入的次数比较少，尽管插入排序需要一个一个比较，但因为数据量不大，所以比较所消耗的资源占比不会太大。 4.不管数据是随机还是基本有序，数据量越大，快排的优势越明显 快排果然还是名副其实的快，我们看到当数据集达到十万级别时，冒泡排序已经用时800多秒，而快排只用了0.3秒，相信随着数据量的增大，它们之间的差距也会越来越大。 5.快排优化方案成立 之前我们讲过快排优化方案：对于大数据集排序先使用快排，使数据集达到基本有序，然后当分区达到一定小的时候使用插入排序，因为插入排序对少量的基本有序数据集性能优于快排！ （编辑：PHP编程网 - 襄阳站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐
浙公网安备 33038102330434号