3.希尔排序的效率分析 ●虽然我们给出的算法是三层循环,最外层循环为 logn数量级,中间的for循环是n数量级的,内循环远 远低于n数量级,因为当分组较多时,组内元素较少 ,此循环次数少;当分组较少时,组内元素增多, 但已接近有序,循环次数并不增加。因此,希尔排 序的时间复杂性在O( nlog,n)和O(n2)之间,大致 为O(n13)。 由于希尔排序对每个子序列单独比较,在比较时进 行元素移动,有可能改变相同排序码元素的原始顺 序,因此希尔排序是不稳定的。 如:4,9,7,6,5,4,13．希尔排序的效率分析  虽然我们给出的算法是三层循环，最外层循环为 log2n数量级，中间的for循环是n数量级的，内循环远 远低于n数量级，因为当分组较多时，组内元素较少 ，此循环次数少；当分组较少时，组内元素增多， 但已接近有序，循环次数并不增加。因此，希尔排 序的时间复杂性在O（nlog2n）和O（n 2 ）之间，大致 为O（n 1.3）。  由于希尔排序对每个子序列单独比较，在比较时进 行元素移动，有可能改变相同排序码元素的原始顺 序，因此希尔排序是不稳定的。  如：4，9，7，6，5，4，1