首页
学习
活动
专区
工具
TVP
发布

复杂排序---希尔排序

希尔排序算法是按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布,是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。...而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。...希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位 算法思路...: 先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序 然后取 d2(d2 < d1) 重复上述分组和排序操作;直到取...di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序

23420
您找到你想要的搜索结果了吗?
是的
没有找到

疯子的算法总结(六) 复杂排序算法 ② 桶排序

从《基于比较的排序结构总结 》中我们知道:全依赖“比较”操作的排序算法时间复杂度的一个下界O(N*logN)。但确实存在更快的算法。...然后只需要对桶中的少量数据做先进的比较排序即可。 对N个关键字进行桶排序的时间复杂度分为两个部分: (1) 循环计算每个关键字的桶映射函数,这个时间复杂度是O(N)。...尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。...桶排序的最好效率能够达到O(N)。 总结: 桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。...如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。

44820

【C语言数据结构】排序(归并排序|计数排序|排序算法复杂度)

今日更新了归并,计数排序的内容 欢迎大家关注点赞收藏⭐️留言 归并排序 归并过程如下: 代码实现(递归) //时间复杂度:O(N*logN) //空间复杂度:O(N) void _MergeSort...计数排序(非比较排序) 代码实现 void CountSort(int* a, int n) { int min = a[0], max = a[0]; for (int i = 1; i < n;...: 统计相同元素出现的次数 根据统计的结果将序列回收到原来的序列中 计数排序需要我们新创建一个统计数组,按理来说,数组下标就可以用来当作统计的数,该位置就来存放该数出现的次数。...但是,如果要排序的数是从一千多开始的,这样前面的空间就全部浪费了。所以我们采用相对映射的方法。即用待排序的数中,最大的数-最小的数+1就可以得到范围,从而减少空间浪费。...最后进行排序,记得加回最小值min,这样数据才不会被改变。 排序算法的复杂度及稳定性 稳定性:指的是相同的数,在排序之后的相对位置没有改变。

9210

java——List列表结构的复杂排序

整型(Integer)和字符串(String)类型的简单排序 这种列表数据的类型是List和List,是简单的数据类型。 可以使用以下的方法排序。...根据list中的对象Bean中的某个属性进行排序 当List泛型的类型不是Integer和String,而是自定义的JavaBean时,这是属于一种复杂的结构,当我们要根据JavaBean中的某个字段进行排序时...,结果时可行的,但是按照字符串(汉字)的属性来进行排序,似乎没有按照首字的全拼来排序,而是有另外的排序规则(我也不清楚)。...user : users) { System.out.println(user); } } } 测试结果 最后一种方法而可以实现JavaBean复杂类型的...List按某个字段首字的中文全拼进行排序

86720

排序算法时间复杂度的下界

《算法导论》中有一节讲的是“(比较)排序算法时间的下界”,本文将论述同一个问题,思路略有差异。本文将从信息熵的角度论述排序算法时间复杂度的下界。若本文论述过程中有错误或是不足,还请各位指正。...问题归约 排序,涉及到被排序的序列和排序的方法。...(比较)排序算法时间的下界对被排序的序列和排序方法做了以下限制 没有关于被排序序列的先验信息,譬如序列内数据的分布、范围等,即认为序列内元素在一个开区间内均匀分布。同时,序列内元素互异。...(比较)排序算法的算法时间复杂度等价为确定输入序列的排列方式需要多少次比较操作。 2 . 信息熵 香农对信息的定义是事物运动状态和存在方式的不确定性描述。事件 ?...对于排序问题,我们可以认为排序算法执行之前,对于待排列数据的没有获得任何信息。在排序过程中,获得了信息使得待排列数据排列方式的不确定度减小了。待排列数据的排列方式共有 ?

1K30

【算法复习3】时间复杂度 O(n) 的排序排序 计数排序基数排序

对要排序的数据要求很苛刻 重点的是掌握这些排序算法的适用场景 【算法复习3】时间复杂度 O[n] 的排序排序 计数排序基数排序排序(Bucket sort) 时间复杂度O(n) 苛刻的数据...每个桶内部使用快速排序,时间复杂度为 O(k * logk) m 个桶排序的时间复杂度就是 O(m * k * logk) 当桶的个数 m 接近数据个数 n 时,log(n/m) 就是一个非常小的常量,...这个时候桶排序的时间复杂度接近 O(n) 苛刻的数据 排序的数据需要很容易就能划分成 m 个桶 每个桶内的数据都排序完之后,桶与桶之间的数据不需要再进行排序。...除此之外,每一位的数据范围不能太大,要可以用线性排序算法来排序,否则,基数排序的时间复杂度就无法做到 O(n) 了。...评论区大佬的总结 总结:桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。 2.线性排序算法的时间复杂度为O(n)。

1.6K10

几种常见排序算法时间复杂

今天说一说几种常见排序算法时间复杂度[通俗易懂],希望能够帮助大家进步!!!...1、插入排序 插入排序时间复杂度: 最好: 所有元素已经排好序,只需遍历一遍,无需交换位置; 最坏: 所有元素逆序排列,遍历一次需要比较的元素个数每次+1,所以时间复杂度是O(n^2); 平均时间复杂度就是...2、快速排序 有关快速排序时间复杂度: 最好的时间复杂度和平均时间复杂度就是O(nlogn); 正常情况下是递归log2n次,每次遍历的最坏时间复杂度是n,所以平均时间复杂度是O(nlogn);...3、归并排序 归并排序时间复杂度: 归并排序无论在什么情况下,将数组拆分都需要log(n)次; 在归并时,也需要遍历比较两个数组的大小,平均时间复杂度O(n); 所以归并排序最好最坏时间复杂度都是...nlogn; 空间复杂度是O(n); 4、堆排序排序每次都要将一个元素上升到堆顶,然后放回最后,需要n轮,固定不变 每一轮堆调整的时间复杂度是log(n),n依次递减 所以堆排序的时间复杂度是

55110

排序-线性排序,如何做到百万级数据秒级排序,时间复杂度O(n)?

我们经常接触的冒泡排序,快速排序,归并排序等,这些排序时间复杂度大多是n^2或者N(logN),他们都是基于比较的排序(就是排序过程中数据两两做比较),那你有知道和了解几种线性排序的算法吗?...他们的时间复杂度都是O(n),下面的几个问题你会了吗? 问题 1000万订单数据金额如何O(n)复杂排序? 100万考生成绩如何O(n)复杂度秒级排序?...100个手机号如何从小到达O(n)复杂排序?.../m=k)个元素,每个桶中元素的排序可以用之前我们分享过的快速排序,则桶排序的时间复杂度是m * k(logk),我们把k用n/m进行等价替换,所以时间复杂度就编程了 n* log(n/m),当m非常接近...n时,那么桶排序的时间复杂度就是O(n)了。

2.3K20

Carson带你学数据结构:希尔排序复杂度最高的排序算法

简介 也称:缩小增量 排序,属于 内排序算法中 的 插入排序类别 是对 直接插入排序算法 的优化和升级 2. 算法原理 3. 算法示意图 步骤1:初始状态 步骤2:跳跃分割 & 排序 4....算法实现 public class ShellSort { /** * 希尔排序 */ public static void shellSort(int[] srcArray...4 1 5 2 7 3 6 8 增量值为:2,排序结果如下: 4 1 5 2 6 3 7 8 增量值为:1,排序结果如下: 1 2 3 4 5 6 7 8 Demo地址:Carson_Ho的Github...地址:希尔排序 5....性能分析 以下将分析算法的性能:时间复杂度、空间复杂度、稳定性 Carson带你学数据结构系列文章: Carson带你学数据:线性表-数组、链表 Carson带你学数据:特殊的线性表-栈、队列

26020

【算法复习2】时间复杂度 O(nlogn)快速排序 归并排序分析

【算法复习2】时间复杂度 O[nlogn]快速排序归并排序分析 归并排序 稳定性 递归转递推 时间复杂度很稳定 归并致命的空间复杂度 快速排序 快排 规则 原地排序 超越归并缺点 快排性能分析 总结...稳定 主要看 子数组 排序后 merge 合并的函数如何执行 可以按先后顺序 合并 merge 函数 保证算法的稳定性 递归转递推 不仅递归求解的问题可以写成递推公式, 递归代码的时间复杂度也可以写成递推公式...时间复杂度很稳定 时间复杂度是非常稳定 不管 数据之前顺序如何 都要重新拍一遍 不管是最好情况、最坏情况,还是平均情况,时间复杂度都是 O(nlogn) 归并致命的空间复杂度 每次合并都要频繁的申请新的内存空间...,还有 partition() 分区函数 归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法,这也使它存在致命的缺点,即归并排序不是原地排序算法,空间复杂度比较高,是 O(n) 可以通过合理地选择...pivot 来避免速排序算法时间复杂度退化到 O(n2)

91530

Python-排序-有哪些时间复杂度为O(n)的排序算法?

前几篇文章介绍了几个常用的排序算法:冒泡、选择、插入、归并、快速,他们的时间复杂度从 O(n^2) 到 O(nlogn),其实还有时间复杂度为 O(n) 的排序算法,他们分别是桶排序,计数排序,基数排序...,因为这些排序算法的时间复杂度是线性的,所以这类算法也叫线性排序。...假设我们有 10 万个手机号码,希望将这 10 万个手机号码从小到大排序,你有什么比较快速的排序方法呢? 如果直接用快排,时间复杂度是O(nlogn),如果使用基数排序,时间复杂度为O(n)。...根据每一位来排序,我们利用上述桶排序或者计数排序,它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位,那我们就需要 k 次桶排序或者计数排序,总的时间复杂度是 O(k*n)。...,每次计数排序的时间复杂度为 O(n),因此使用基数排序对类似这样的数据排序的时间复杂度也为 O(n)。

1.4K20
领券