排序算法

选择排序:

​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。

​ 但是这个算法的复杂度比较高,为 $$ n^2/2 $$ ​ 那为什么是这个值,假若我们放一张 n x n 的表格,然后我们在排序的过程中用灰色表示不变的元素,然后用黑色表示变化的元素。这样一来我们会发现这个表格是一个以对角线分隔的一个矩阵。很统一看到我们进行了二分之一的 n^2 扫描。

​ 这个算法的另外一个问题就是无论我们的序列本来是否有序,我们都需要不停地扫描,所以说这个不存在最好情况和最坏情况,一直都效率不高。

插入排序:

​ 插入排序的算法过程和选择排序类似,这是这个地方我们始终让左边的序列保持有序,然后把剩下的那些无序的元素一个个插入到有序序列之中。或许你已经明白了整整比较消耗时间的就是插入操作,我们又需要不停地移动着数组。但是这就有一个好处就是当我们序列比较有序的时候我们所做的操作非常少,甚至当序列完全有序的时候我们只需要进行 n 次比较而已。他的算法复杂度比上面的要好一点,为 $$ n^2/4 $$ 同样的我们可以画一个矩阵,最终我们会发现有黑色全部在对角线下面,而且对角线下面只有一半是黑色的,因此就是 1/4

希尔排序:

​ 希尔排序事实上可以看做插入排序的一个变种,他是首先进行了分组,然后在组内进行了插入排序,这样改造后的性能提高了很多。重点就在于如何进行分组的问题,希尔自己提出的方法就是使用 n/3 也就是每一次步长减少 n/3

归并排序:

​ 归并排序是比较有名的排序,这个排序的思想就是,所谓的归就是递归,递归的去求左右子序列。而并就是最后需要合并这些子序列。这个算法一般需要一个辅助数组来支撑,也就是把两个子序列合并成一个新的数组的时候,需要这个辅助数组,最后还需要把他拷贝回去。下面是归并的流程图。

​ 除了这种使用递归的方式我们还可以从下到上的进行合并操作,也就是我们合并操作不变,但是把递归改成循环了,这里就用到了双循环,首先两两排序,然后两两合并。有点类似于希尔排序了。但是这种方式的算法复杂度并没有改变依然就是 nlogn

​ 对于这种比较高级的排序我们可以做一定的优化让他们支持所中情况下的排序。首先这个归并排序并不适合于少量的数据,少量的数据的时候我们使用分治循环是很不划算的,我们可以在归并排序前面添加一些判断条件,当数组的容量少于多少的时候我们可以采用插入排序,这样算法更具有通用性。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SparkStreaming 入门

    lwen
  • ReentrantLock 与 AQS 源码分析

    ReentrantLock 与 AQS 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没...

    lwen
  • markdown语法

    Markdown 语法说明 (简体中文版) / (点击查看快速入门) 概述 宗旨 兼容 HTML 特殊字符自动转换 区块元素 段落和换行 标题 区块引用 列表 ...

    lwen
  • 算法之旅 | 冒泡排序法

    HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

    HTML5学堂
  • 经典排序算法详细介绍

    渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:

    IT茂茂
  • 各大排序算法性能比较及演示实例

    所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

    顶级程序员
  • 10.7 内部排序方法的比较

    1、从平均时间性能而言,快速排序最佳,其所需时间最省,但快速排序在最坏情况下的时间性能不如堆排序和归并排序。

    闫小林
  • 算法一看就懂之「 排序算法 」

    之前的文章咱们已经聊过了「 数组和链表 」、「 堆栈 」、「 队列 」和「 递归 」,这些要么是基础的数据结构,要么就是巧妙的编程方法。从今天起咱们来进入真正的...

    奎哥
  • 排序算法(九):桶排序

    桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中...

    zhipingChen
  • 不稳定的原地排序算法:选择排序

    在之前的文章中,我们说了两个原地排序算法:插入排序和冒泡排序。分析两个算法的原理,也用代码实现了两个算法。最后,我们也从两个算法入手,引出了评价算法性能的两个重...

    飞翔的竹蜻蜓

扫码关注云+社区

领取腾讯云代金券