本文目录
希尔排序时间复杂度O(n¹.³)中的1.3是怎么来的
1、首先希尔排序是一种递减增量的排序算法，下面使用大小为9的数组：54、26、93、17、31、44、55、20。
2、令数据间隔为3，将该数组分成三个子数组，如下图所示，为下图中灰色的部分。
3、对每一个子数组都进行插入排序操作，将排序好的子数组合并到一个数组当中。这个时候，会发现，每个数字都会务必接近他应该存在的位置。
4、这是间隔为3的子数组排序后的结果，发现该排序后的数列非常接近我们需要的递减或者递增序列。下一步只需要，缩小间隔进行重复性操作即可
5、最后改变间隔，使间隔变成4，这个时候子数组反而有4组。这个说明希尔排序（shell sort）是一个不稳定的排序。
求希尔排序的时间空间复杂度还有要是可能的话给讲解下是怎么个回事吧，弄晕了谢谢、、、
你好，希尔排序的时间复杂度是O（n的1.25次方）~O(1.6n的1.25次方) 这是一个经验公式，好像没人解释过，就是一句经验得出的。（不好意思。。没解释出来）空间复杂度是O（1） 因为只有一个缓冲单元。希望对你有帮助。希尔排序的算法：Void ShellInsert(Sq:ost&L,int dk){For(i=dk+1;i《=L.length;++i)If(LT(L.r=L.r;}}//ShellInsert
希尔排序法原理
希尔排序基本思想 基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-l《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。给定实例的shell排序的排序过程 假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次为： 5，3，1 排序过程如【动画模拟演示】。Shell排序的算法实现1． 不设监视哨的算法描述 void ShellPass(SeqList R，int d) {//希尔排序中的一趟排序，d为当前增量 for(i=d+1;i《=n；i++) //将R到正确的位置上 } //endif } //ShellPass void ShellSort(SeqList R) { int increment=n； //增量初值，不妨设n》0 do { increment=increment/3+1； //求下一增量 ShellPass(R，increment)； //一趟增量为increment的Shell插入排序 }while(increment》1) } //ShellSort 注意： 当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件“j》0“，以防下标越界。2．设监视哨的shell排序算法 具体算法【参考书目 】算法分析1．增量序列的选择 Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征： ① 最后一个增量必须为1； ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。2．Shell排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因： ①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 ②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 ③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。3．稳定性 希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。
什么是希尔排序
希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。希尔排序基本思想基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-l《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。详细资料：http://bk.baidu.com/view/178698.htm
数据结构中排序和查找各种时间复杂度
数据结构中排序和查找各种时间复杂度 (1)冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。(2)选择排序 选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的。…… 例子说明好多了。序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了， 所以选择排序不稳定的排序算法(3)插入排序 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果和插入元素相等，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。所以插入排序是稳定的。(4)快速排序 快速排序有两个方向，左边的i下标一直往右走（往后），当a交换的时刻）(5)归并排序 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列全部排好序。相等时不发生交换。所以，归并排序也是稳定的排序算法。(6)基数排序 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。(7)希尔排序(shell) 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。(8)堆排序 我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序是不稳定的排序算法一、排序排序法 平均时间 最差情形 稳定度 额外空间 备注冒泡 O(n2) O(n2) 稳定 O(1) n小时较好交换 O(n2) O(n2) 不稳定 O(1) n小时较好选择 O(n2) O(n2) 不稳定 O(1) n小时较好插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好Shell O(nlogn) O(ns) 1《s《2 不稳定???=““ o(1)???????=““ s是所选分组《/s快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9)，R是基数(个十百)二、查找未写……三 树图克鲁斯卡尔算法的时间复杂度为O（eloge）普里姆算法的时间复杂度为O（n2）迪杰斯特拉算法的时间复杂度为O（n2）拓扑排序算法的时间复杂度为O（n+e）关键路径算法的时间复杂度为O（n+e）
