前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >排序算法小结

排序算法小结

作者头像
用户1217611
发布2019-05-25 18:41:20
3310
发布2019-05-25 18:41:20
举报
文章被收录于专栏:文渊之博

排序是工作和生活中非常常见的一个问题。现在已经有比较成熟的排序技术,被广泛地应用于各种程序语言或数据库中。不同的排序算法有不同的性能和适用场景,下面的视频对比了 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),由于要构造堆,因此不适用于序列个数较少的情况。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-02-26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 鸡尾酒排序
  • 希尔排序
  • 梳排序
  • 归并排序
  • 快速排序
  • 堆排序
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档