首页
精选文章希尔排序查看全文希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本，但希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率； 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位； 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。 插入排序的时间复杂度是O（n2），但是如果数据是有序的，插入排序的效率会大幅提升，可以达到O（n）的时间复杂度，所以数据的有序性对插入排序的性能影响较大。 希尔排序也是采用分治的思想通过多次迭代将数据变得相对有序，从而减少插入排序流程中需要比较的次数。 希尔排序会将数字进行多次分组，分组会从小到大依此进行，例如第一次分组是将元素分为两个一组，因为插入排序在小数据量时有较好的效率，之后，分组会逐渐变大，到4个一组，8个一组，直到n/2个一组，数据量较大时候，插入排序的性能会有所下降，但是因为之前的分组使得数据变得相对有序，会提高后续插入排序的效率。 比如10个数字的希尔排序。 第一次把数据分为分组，10除以2得出分为5组，之后对5组数据分别进行插入排序。 第二次把数据分为2组，10除以4得出，之后对这两组数据进行插入排序。 以此类推，第n次分组的组数为元素个数/2n，直到仅剩下一个分组，进行一轮完整的插入排序。 插入排序进行分组不是简单的逐段分割，而是跳跃式的分组，该分组方式可以使得数据相对有序，而且中间会有一定的插入空间，从而减少插入时候的移动数量。插入排序查看全文插入排序的循环过程和冒泡排序，选择排序不同，不是每次处理元素的时候确定该元素的最终位置，插入排序是从前到后依次处理每个位置的数据，而处理该位置时，之前的数据都是已经排好序的，把这个数据插入到前面排好序的元素中的正确位置，和我们玩扑克牌的过程类似。插入排序每次处理数字的时候，前面的问题已经是排好序的，也就是前面已经构成了子序列的解，此类可以拆分成子问题的问题通常可以用递归等方式实现。 插入排序过程从第二个元素开始遍历，第二个元素和第一个元素比较大小，如果比第一个数字小，则插入到第一个元素的前面。 之后处理第三个元素，因为前两个元素比较排好顺序，所以可以确定第三个元素和前两个元素的大小关系，之后将第三个元素插入到正确的位置。 依次类推，完成整个排序过程。 从第二个数据开始循环，直到最后一个元素。 将该元素和之前的元素进行比较，因为之前的元素都是排序的，所以确认该元素的位置之后，将该元素插入到合适的位置。 在完成插入之后，该位置以及之前的数据都已经排序完成。CAP查看全文CAP理论是2000年由Eric Brewer教授提出的。即一个分布式系统不可能同时满足一致性，可用性，分区容忍性这三个需求，而最多只能同时满足2个。2002年MIT的Seth Gilbert和Nancy lynch证明了CAP的正确性。CAP中的C是consistency（一致性）的缩写，首先解释一下一致性，一致性概念在计算机领域至少有下列含义： 数据库事务（ACID）的一致性是指数据变更的过程中需要满足正确的状态约束，这些约束分是数据库层面的约束，比如外键关系，但有一部分约束是指业务层实现的约束，例如转账的过程中用户的账户金额不能小于0。 不同于AID是数据库层面需要提供的能力，C需要用户自己实现。 CAP中的一致性，指的是一个读操作从能读取到之前写操作的结果，在分布式场景下更多的指数据副本之间的一致性。这里的一致性从事件约束可以分为强一致性和最终一致性，强一致性是指用户每次都可以读取到最新的数据，最终一致性是指可以在确定的时间内查询到最新的数据。从实现的方式上可以分为顺序一致性和线性一致性。 可用性是指系统的可用性，每一次请求都能在一定的时间内响应。 分区容忍性主要解决的是脑裂问题，即网络出现分区的情况下的状态。 因为分布式理论天然需要支持分区容忍性，所以CAP的概念真正的本质是在网络分区的情况下，只能在一致性和可用性中选择一个特性。 分区容忍性 分布式环境下的集群节点必然是有不同区域的物理分布的，分布可能是大的城域网分区，也可能是不同机房的分区，甚至小到机房的不同机架。 分区即集群的节点因为联通问题分成了两部分，此时面临的问题是两个分区同时提供服务，即脑裂问题，脑裂问题会导致后续的数据无法合并，因此分区容忍性就是解决脑裂问题… |
热门分类开源Golang消息队列JavaJavascriptLinuxMysqlNLPPHP事务内存管理分布式理论分类存储常用存储开源软件操作系统画图网络编程数据库算法虚拟化前端存储理论常用算法微服务数据结构算法应用计算机原理中间件共识算法分布式分治动态规划容器并发排序架构组件绘图工具网络协议编程语言理论算法思想树缓存架构C++字符串算法工程思想搜索
算法题库精选内容 |
