你真的弄懂排序了吗?(一)

Proud lion 前端 2021-08-27

冒泡排序

冒泡排序,有时也称为下沉排序,是一种简单的排序算法,它重复遍历要排序的列表,比较每对相邻的项目,如果它们的顺序错误(升序或降序排列),则交换它们。重复遍历列表直到不需要交换,这表明列表已排序。

你真的弄懂排序了吗?(一)

选择排序

选择排序是一种排序算法,特别是就地比较排序。它的时间复杂度为 O(n2),使其在大型列表上效率低下,并且通常比类似的插入排序表现更差。选择排序以其简单性而著称,并且在某些情况下比更复杂的算法具有性能优势,尤其是在辅助内存有限的情况下。

你真的弄懂排序了吗?(一)

你真的弄懂排序了吗?(一)

插入排序

插入排序是一种简单的排序算法,它一次构建一个最终排序的数组(或列表)。与更高级的算法(如快速排序、堆排序或归并排序)相比,它在大型列表上的效率要低得多。

你真的弄懂排序了吗?(一)

你真的弄懂排序了吗?(一)

堆排序

堆排序是一种基于比较的排序算法。堆排序可以被认为是一种改进的选择排序:与该算法一样,它将输入分为已排序和未排序区域,并通过提取最大元素并将其移动到已排序区域来迭代缩小未排序区域。改进包括使用堆数据结构而不是线性时间搜索来找到最大值。

你真的弄懂排序了吗?(一)

你真的弄懂排序了吗?(一)

归并排序

在计算机科学中,归并排序(通常也拼写为归并排序)是一种高效、通用、基于比较的排序算法。大多数实现产生稳定的排序,这意味着实现保留排序输出中相等元素的输入顺序。归并排序是一种分而治之的算法,由约翰·冯·诺依曼于 1945 年发明。

归并排序的一个例子。首先将列表分成最小单元(1个元素),然后将每个元素与相邻列表进行比较,对相邻的两个列表进行排序合并。最后对所有元素进行排序和合并。

你真的弄懂排序了吗?(一)

快速排序

快速排序是一种分而治之的算法。快速排序首先将一个大数组分成两个较小的子数组:低元素和高元素。然后快速排序可以递归地对子数组进行排序

步骤是:

  1. 从数组中选取一个称为枢轴的元素。
  2. 分区:重新排列数组,使所有值小于枢轴的元素都在枢轴之前,而所有值大于枢轴的元素都在其之后(相等的值可以以任何方式进行)。在此分区之后,枢轴处于其最终位置。这称为分区操作。
  3. 将上述步骤递归地应用于具有较小值的元素子数组,并分别应用于具有较大值的元素子数组。

快速排序算法的动画可视化。水平线是枢轴值。

你真的弄懂排序了吗?(一)

参考资料:github.com/trekhleb/ja…


作者:gyx_这个杀手不太冷静

链接:https://juejin.cn/post/7000954995726090276

来源:掘金

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Apipost 私有化火热进行中

评论