排序算法-希尔排序

属性

        1. 希尔排序是对直接插入排序的优化。

        2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很 快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

        3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排 序的时间复杂度都不固定：

        4. 稳定性：不稳定

        

代码及其注释

public class ShellSort {//希尔排序实际上就是分多个组进行多次的插入排序，前几次插入排序都只是为了让数据更加有序，最后一次排序才是真正的排序数据public static void shellSort1(int[]arr){//首先要获得此次进行插入排序时同一组数之间的间隙//间隙的计算是很讲究的，但这里就直接用数组长度的二分之一作为间隙，之后再依次取二分之一，直到间隙为1//间隙为1时才是真正的对数组进行排序int gap=arr.length/2;while (gap>=1){shell1(arr,gap);gap=gap/2;}}//传入要排序的数组，以及在进行插入排序时，同一组数据在数组之间的间隙，进行插入排序//shell的代码其实就是根据间隙gap对插入排序进行一些修改private static void shell1(int[]arr,int gap){for(int i=gap;i<arr.length;i++){int tmp=arr[i];int j=i-gap;for(;j>=0;j-=gap){if(arr[j]>tmp){arr[j+gap]=arr[j];}else {break;}}arr[j+gap]=tmp;}}
}