希尔排序法，最坏情况需要几次比较
呵呵，昨天看数据结构刚看到，希尔排序时间复杂度为O(n（log2n)^2）,空间复杂度为0(1)，是一种不稳定的排序算法，直接选择排序的时间复杂度为0（n^2)，空间复杂度为0(1)，所以希尔排序的效率高。
希尔排序和堆排序的实际效率谁高
个人认为是快速排序。
快速排序的最差复杂度可能会降为n^2，最快则是nlogn，但是，平均情况下是较快的。
而希尔排序的最差情况下，复杂度可能会降为n^s 到n^s之间，(1<=s<=2)，平均则是nlog^2n。
理论上来看，希尔排序可能是效率比较高的。
但是，实际情况来看，快速排序的实际效果很不错。
原因就是，快速排序在实际情况中，坏的情况是不太容易出现的（取中间值或随机值），坏情况概率低。
而，希尔排序在实际情况中，效率就取决于他在求解过程中的增量，合理的增量是不好找的。
因此，经常会出现不爽的情况，坏的情况概率高。
论文：
用c语言编写一个希尔排序程序，新手，最好能给注释下
谢谢
网友wang1992092对希尔排序的理解有些错误，希尔排序对每个子序列进行的是直接插入排序，而不是如他所给出的选择排序。
你可以先百度一下希尔排序的定义。
我这里给一个C源代码，你可以试试。
直接插入排序的思路是：将待排表分成两部分，一部分是已有序部分L，另一部分是待排序部分R。
L初始化为只含第一个元素的表，因L现在只含一个元素，所以是有序的。
然后每次从R中取出最前面的元素到tmp(相当于出队到tmp中)，然后在L中从后向前搜索插入位置，边搜索边向后移动比tmp大的元素，找到了插入位置后就将tmp插入到L中。
直到R部分为空时结束。
typedef int datatype;void InsertSort(datatype a[], int left, int right, int gap) \\\/*对数组a中起始下标为left，结束下标为right，步长为gap的子序列进行直接插入排序，当gap等于1时就是通常的插入排序了*\\\/{ int tmp, i, j; for(i = left + gap; i <= right; i += gap){ for(tmp = a[i], j = i - gap; j >= left && a[j] > tmp; j -= gap) a[j + gap] = a[j]; a[j + gap] = tmp; }}void ShellSort(datatype a[], int left, int right){ int gap = (right - left + 1) \\\/ 2, i;\\\/*步长gap初始化为n\\\/2取下整*\\\/ while(gap > 0) { for(i = left; i < gap; i++) \\\/*对每个子序列进行直接插入排序*\\\/ InsertSort(a, i, right, gap); gap = gap \\\/ 2; \\\/*将步长缩小为原来的一半并取下整*\\\/ }}
希尔排序的时间复杂度和数组的初始排序有关吗
为什么
有关。
希尔排序实际上是一种插入排序，它的时间复杂度和数组初始排序有关。
平时我们所说的时间复杂度都是它的平均时间复杂度。
关于希尔排序和增量的问题。
像这个我们一般去d=6如果取d=4 那么就把第一个数与第五个数与第九个数比较小的放在前面 15...16...17第二个数与第六个数与第十个数比较，.2...5...9....4...8...13....18...24...25..一趟扫描结果为：15，2，4，18，16，5，8，24，17，9，13，25
