希尔排序算法证明

希尔排序算法证明
希尔排序算法证明

希尔排序算法证明
希尔排序：
* 不需要大量的辅助空间,和归并排序一样容易实现.希尔排序是基于插入排序的一种算法,
* 在此算法基础之上增加了一个新的特性,提高了效率.希尔排序的时间复杂度为 O(N*(logN)2),
* 没有快速排序算法快 O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是
* 最优选择.但是比O(N2）复杂度的算法快得多.并且希尔排序非常容易实现,算法代码短而简单.
* 此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏
* 的情况下执行的效率会非常差.
*
* 专家门提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快,
* 再改成快速排序这样更高级的排序算法.
*
* 本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多.
* 原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长.
* 当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置.
* 正是这两种情况的结合才使希尔排序效率比插入排序高很多.