排序算法——希尔排序

时间复杂度:由于希尔排序的时间复杂度依赖于增量序列的函数,时间复杂度分析起来比较困难。当n在某个特定范围内的时候,希尔排序的时间复杂度约为O(排序算法——希尔排序)。

空间复杂度:O(1)

算法稳定性:不稳定

算法原理:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<d(t-1)<....d2<d1),即所有记录放在同一组中进行直接插入排序为止。

图示:

排序算法——希尔排序

 代码:

public static void shell_sort(int array[]){
        int len=array.length;
        int step=len>>1;//int step=len/2;
        while(step>=1){
            for(int i=step;i<len;i++){
                for(int j=i;j>=step;j-=step){
                    if(array[j]<array[j-step]){
                        swap(array,j,j-step);
                    }else{
                        break;//每次内层循环比较一次即可,因为前面已经排好序了
                    }
                }
            }
            step>>=1;
        }
    }
    private static void swap(int[] array, int i, int j) {
        int a=array[i];
        array[i]=array[j];
        array[j]=a;
    }

 

 

 

上一篇:接口测试平台170:并发底层代码问题纠正


下一篇:新建linux虚拟机(1)