设为首页收藏本站

EPS数据狗论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 1395|回复: 0

[数据可视化] 九种排序算法的可视化及比较

[复制链接]

6

主题

45

金钱

76

积分

新手用户

发表于 2019-9-25 15:04:58 | 显示全部楼层 |阅读模式

排序是工作和生活中非常常见的一个问题。现在已经有比较成熟的排序技术,被广泛地应用于各种程序语言或数据库中。不同的排序算法有不同的性能和适用场景,下面的视频对比了 9 种排序算法的性能表现。排序算法依次为选择排序、希尔排序、插入排序、归并排序、快速排序、堆排序、冒泡排序、梳排序、鸡尾酒排序。

冒泡排序
冒泡排序(Bubble Sort)是一种交换排序,基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

在最好的情况下,也就是数列本身是排好序的,需要进行 n - 1 次比较;在最坏的情况下,也就是数列本身是逆序的,需要进行 n(n-1)/2 次比较。因此冒泡排序总的时间复杂度是 O(n^2)。


选择排序
选择排序(Selection sort) 的基本思想是每一趟在 n - i + 1 (i = 1,2,***,n - 1)个记录中选取关键字最小(或最大)的记录作为有序序列的第 i 个记录,直到所有元素排序完成。选择排序是不稳定的排序算法。

选择排序的时间复杂度为 O(n^2),但性能上略优于冒泡排序。


插入排序
插入排序类似于整理扑克牌,基本操作是将一个记录插入到已经排好序的有序数列中,从而得到一个有序但记录数加一的有序数列。

插入排序的时间复杂度为 O(n^2),是稳定的排序方法,适用于数量较少的排序。


鸡尾酒排序
鸡尾酒排序是冒泡排序的一种变形。先找到最小的数字,放在第一位,再找到最大的数字放在最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到完成排序。

鸡尾酒排序的时间复杂度为 O(n^2)。


希尔排序
希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进。基本思想是将相距某个增量 d 的记录组成一个子序列,通过插入排序使得这个子序列基本有序,然后减少增量继续排序。

操作上先取一个小于 n 的整数 d1 作为第一个增量,把全部记录分成 d1 个组,所有距离为 dl 的倍数的记录放在同一个组中。先在各组内进行直接插人排序,然后取第二个增量d2 < d1 重复上述的分组和排序,直至所取的增量 dt = 1 (dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

希尔排序的时间复杂度可以达到 O(n^(3/2)),要好于前面几种算法。


梳排序
梳排序和希尔排序很类似。希尔排序是在直接插入排序的基础上做的优化,而梳排序是在冒泡排序的基础上做的优化,也就是将相距某个增量 d 的记录组成一个子序列,通过冒泡排序使得这个子序列基本有序,然后减少增量继续排序。

梳排序的时间复杂度是 O(nlogn)。


归并排序
归并排序(MERGE-SORT) 是一种分治算法,是建立在归并操作上的一种有效的排序算法。常用的 2 路归并排序假设初始序列有 n 个记录,可以看成是 n 个长度为 1 的子序列,进行两两归并,可以得到 n / 2 个长度为 2 或 1 的子序列;再两两归并,******,直到得到一个长度为 n 的有序序列为止。

归并排序的时间复杂度是 O(nlogn),是一种效率高且稳定的算法。


快速排序
快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是通过一趟排序将待排记录分割成独立的两部分,其中一部分的记录都比另一部分小,然后再分别对这两个部分进行快速排序,最终实现整个序列的排序。

快速排序的时间复杂度为 O(nlogn),是一种不稳定的排序算法;


堆排序
堆是具有下列性质的完全二叉树:

1. 每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆;

2. 每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆。

堆排序(Heap sort)是指利用堆这种数据结构所设计的一种排序算法。基本思想是把待排序的序列构造成一个大顶堆,此时序列的最大值就是队顶元素,把该元素放在最后,然后对剩下的 n - 1 个元素继续构造大顶堆,直到排序完成。

堆排序的时间复杂度为 O(nlogn),由于要构造堆,因此不适用于序列个数较少的情况。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

站长推荐上一条 /1 下一条

客服中心
关闭
在线时间:
周一~周五
8:30-17:30
QQ群:
653541906
联系电话:
010-85786021-8017
在线咨询
客服中心

意见反馈|网站地图|手机版|小黑屋|EPS数据狗论坛 ( 京ICP备09019565号-3 )   

Powered by BFIT! X3.4

© 2008-2028 BFIT Inc.

快速回复 返回顶部 返回列表