2 u014494703 u014494703 于 2016.04.19 15:52 提问

希尔排序的时间复杂度

希尔排序最坏情况的时间复杂度是多少哇 。在网上看有O(N^2)的还有O(N^1.5)

4个回答

caozhy
caozhy   Ds   Rxr 2016.04.19 18:50

最坏情况O(N^2)。

m0_37595514
m0_37595514   2017.02.25 21:23

希尔排序的最坏时间复杂度是O(n^s) , 1<s<2, s是所选的分组。

m0_37595514
m0_37595514   2017.02.25 21:28

希尔排序的最坏时间复杂度是O(n^s) ,
1<s<2,
s是所选的分组。

m0_37595514
m0_37595514   2017.02.25 21:28

希尔排序的最坏时间复杂度是O(n^s) , 1<s<2, s是所选的分组。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
希尔排序&选择排序&时间复杂度分析
#include #include void shellsort(char array[],int len); void selectsort(char array[],int len); void swap(char *a,char *b) { *a ^= *b; *b ^= *a; *a ^= *b; }//好多傻逼面试都考这种写法,岂不知这种写法在a,b是一个数时有bug:假设
希尔排序 时间复杂度 证明
Shellsort     Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [She 59]. It is fast, easy to understand and easy to implement. However, its c
关于希尔排序的时间复杂度分析
希尔排序又叫做“缩小增量排序”,它也是一种属于插入排序类的方法,但是在时间复杂度上又有了改进。它的基本思想是,先将整个待排序记录分割为若干个子序列分别插入排序,待整个序列中的记录基本有序是,,再对全体记录进行一次插入排序。 如下是一组增量序列分别为 3 2 1 的排序        增量排序的时间复杂度依赖于所取增量序列的函数,但是到目前为止还没有一个最好的增量序列.有人在
排序算法之 插入排序、希尔(shell)排序 及其时间复杂度和空间复杂度
有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这
希尔排序实现与复杂度、稳定性分析
import java.util.*; public class ShellSort { public int[] shellSort(int[] a, int n) { //先判断条件 if(a== null|| n<2){ return a; } int feet = n/2;
排序算法——希尔排序的图解、代码实现以及时间复杂度分析
希尔排序(Shellsort) 希尔排序是冲破二次时间屏障的第一批算法之一。 希尔排序通过比较相距一定间隔的元素来工作;各躺比较所用的距离随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止。由于这个原因,希尔排序有时也叫做缩减增量排序。 希尔排序使用一个序列h1,h2,…,hi,这个序列叫做增量序列(increment sequence)。增量序列只要求h1=1,以及hi>hi-1。
数据结构基础 希尔排序 之 算法复杂度浅析
希尔排序(Shell Sort)又叫做缩小增量排序(diminishing increment sort),是一种很优秀的排序法,算法本身不难理解,也很容易实现,而且它的速度很快。 Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。 希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序
PHP数据结构(5)希尔排序及其时间复杂度
希尔排序算法是针对直接插入排序算法的改进。其算法描述为:从一个长度为N的无序数组中取一个小与N的整数d1作为第一次的增量,然后将数组按每相隔d1个元素进行全部记录分组(并不是真实分组)。分完组后现在各组中进行直接插入排序,接着,取出第二个增量么d2 其PHP语言描述如下: <?php function shell_sort($array){
【算法-排序之四】希尔排序
算法-排序之希尔排序     希尔排序得名于其设计者设计者希尔(Donald Shell),设计体现了计算机领域的“分治法”思想。在众多排序算法中,目前而言,希尔排序是唯一能在效率上与快速排序(【算法-排序之二】快速排序)一较高低的算法,目前只有这两种排序算法的时间复杂度突破O(n2)。值得一提的是,希尔排序与快速排序都基于“分治法”,从这里或许可以解释这两种排序算法在效率上的得天独
Java-时间复杂度为O(nlogn)的排序算法(快速排序, 归并排序, 堆排序, 希尔排序)
/** 包含多种静态排序方法 * Created by Andre on 2016/6/27. */ public class Sorter { /** * 快速排序 * 递归形式 * 第一个记录为枢轴 * 不稳定 * @param a 需要排序的数组 * @param low 数组的起始下标 * @param h