排序算法:了解为什么不应该使用Bubblesort

披露: 您的支持有助于保持网站的正常运行!我们会为此页面上推荐的某些服务收取推荐费.


您是否曾经想过计算机如何使事情井井有条?当您单击Excel中的A-Z按钮时,实际情况是什么?

计算机按照称为“排序算法”的程序对列表进行排序。算法是一组可以机械地反复遵循的指令。有几种不同的排序算法-将列表按适当顺序排序的不同过程。每个人都有其优点和缺点.

这是最受欢迎的排序算法.

气泡排序

冒泡排序是一种低效但简单的算法。在实践中很少使用,但很容易理解.

冒泡排序通过比较列表中连续的元素对来工作。比较第一个和第二个元素,然后比较第二个和第三个元素,然后比较第三个和第四个元素,依此类推。每次比较后,如果两个元素顺序混乱,则将它们交换。一次迭代后,最大的元素将“冒泡”到列表的末尾。重复此过程,直到对列表进行排序.

在双向变量中,比较是在列表中交替进行,然后在列表中进行比较。这将在列表的每一端增加一个排序的部分。这也称为“鸡尾酒摇床排序”。

何时使用冒泡排序

从不,除了示范.

有关气泡排序的更多信息

  • 来自算法专家的冒泡排序说明,带有示例代码;
  • 气泡排序算法以100多种不同的编程语言编码;
  • 乐高积木说明的冒泡排序;
  • 匈牙利民间舞表演的泡泡排序.

插入排序

插入排序是大多数人直观地手动排序内容的方式-例如,按字母顺序排列纸张时。它涉及将每个元素依次移到已分类部分中的适当位置.

列表的第一个元素被认为是“已排序”。然后考虑第二个要素。如果它大于其之前的元素,则它位于正确的位置,并构成“已排序”部分的一部分。否则,它将向后移动一个插槽,并与其后面的元素进行比较。元素继续向后移动,直到它在列表的已排序部分中的正确位置。然后对第三,第四,第五个元素重复此过程,依此类推.

何时使用插入排序

插入排序通常是对小列表(10个或更少的元素)进行排序的最快解决方案,并且至少在中等大小的列表中表现良好。在较大的集合中,它可能会变得异常缓慢.

即使列表已经大部分排序,插入排序也可以很好地执行,即使是大集合也是如此。这使得它非常适合清理旧的人类分类数据,或与其他分类算法结合使用。例如,通常从快速排序开始,然后经过几次迭代后切换到插入排序.

有关插入排序的更多信息

  • 可汗学院的插入排序说明和编码练习;
  • 用近100种不同的编程语言编码的插入排序算法;
  • 插入排序用聚苯乙烯泡沫塑料杯图解,并由哈佛大学的CS学生叙述。
  • 插入排序以匈牙利民间舞蹈为例.

堆排序

堆排序是两部分的排序,它使用二进制堆数据结构作为列表中元素的中间持有人.

二进制堆是一种树形结构,其中每个节点最多具有两个子节点。最大的元素在树的顶部。每个子节点都小于其父节点。这意味着构建堆的过程会对列表进行部分排序。堆建立之后,将最大的元素删除并放入已排序的数组中-然后是剩余堆中最大的元素,依此类推.

何时使用堆排序

平均而言,堆排序可提供良好的性能。此外,对于几乎所有其他算法,其最坏情况比最坏情况要好得多。因此,它通常用于大型和分布式数据集.

有关堆排序的更多信息

  • 肯特州立大学的CS教授对堆排序的详细说明;
  • 麻省理工学院的堆和堆分类视频讲座;
  • 要深入了解堆和堆排序,请参阅此五部分视频系列.

合并排序

将两个已经排序的列表合并到一个新的已经排序的列表中是相对简单的:比较每个列表的第一个元素,然后将较小的元素放入新列表中,然后重复。这是合并排序的基础.

为了开始合并排序,列表被分为一组由1个元素组成的“列表”。然后,将这些列表对合并为2个元素的列表,然后将其合并为4个元素的列表,依此类推,直到整个列表重新合并在一起.

何时使用合并排序

合并排序非常有效。唯一的问题是合并排序通常需要足够的活动内存(RAM)才能两次保存该列表。因此,在某些情况下它可能变得不可行.

有关合并排序的更多信息

  • 来自Khan Academy的Merge Sort是一个非常好的六部分课程,其中包括编程练习。
  • 合并以80多种不同编程语言编码的排序;
  • 与德国民间舞蹈合并排序提供了演示排序算法的舞蹈例程.

快速排序

快速排序不是很直观。但是,它非常有效.

快速排序的第一步是选择一个枢轴元素。这可以是列表中的任何元素。接下来,所有大于枢轴的值都放置在它的后面,而所有小于枢轴的值都放在它的前面。这将创建两个未排序但彼此之间具有正确关系的分区。在每个分区上然后在每个子分区上执行相同的过程,依此类推。当分区的大小达到每个元素一个时,将对列表进行排序.

何时使用快速排序

快速排序是最流行的实用排序算法之一。平均速度非常快。但是,最坏的情况(在自然数据集中很少发生)对于很大的数据集来说是有问题的.

有关快速排序的更多信息

  • 使用100多种编程语言进行快速排序编码;
  • 哈佛CS-50班的积木解释了快速排序;
  • Tutorials Point的快速排序教程包含许多详细信息,示例代码和动画图像.

常规排序算法资源

  • 数据结构-排序技术是Tutorials Point的非常详细的系列文章。
  • 排序算法具有在不同条件下的各种可视化效果-您甚至可以观看不同的算法相互竞争;
  • 6分钟内提供15种排序算法,是一种令人着迷的视频可视化;
  • 进行分类是视频,探讨计算机分类的问题;
  • 不同分类算法听起来像什么,是令人难以置信的“听觉化”视频,它将几种分类算法转换为声音.

摘要

在大多数情况下,进行编程时,如果需要一些琐碎的排序(一小段值,一列数据),则只需使用编程语言或喜欢的库中内置的任何方法或函数.

但是在处理大型数据应用程序时,重要的是要考虑您选择的算法将如何影响系统性能。除此之外,排序算法是计算机科学的基本方面,任何从事开发或编程工作的人员都应该理解排序算法.

进一步阅读和资源

我们有更多与编码和开发有关的指南,教程和信息图:

  • C ++开发人员资源:最受欢迎的编程语言之一,适用于大多数应用程序.
  • Unicode简介和资源:了解有关字符编码的全部信息.
  • MantisBT简介和资源:MantisBT是最受欢迎的错误跟踪程序之一.

您应该学习什么代码?

对应该学习哪种编程语言感到困惑?查看我们的信息图,您应该学习什么代码?它不仅讨论了语言的不同方面,还回答了一些重要问题,例如:“我将以编程为生赚多少钱?”

您应该学习什么代码?
您应该学习什么代码?

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me