选择排序、插入排序和希尔排序(2)

简单的说,就是插入排序总共需要排序N-1趟,从index为1开始,讲该位置上的元素与之前的元素比较,放入合适的位置,这样循环下来之后,即为有序数组。

代码实现:

public class InsertionSort extends SortBase {

@Override
    public Integer[] sort(Integer[] a) {
        // TODO Auto-generated method stub
        print("init",a);
        Integer temp = 0;
       
        for(int i=1;i<a.length;i++) {
            //只能从当前索引往前循环,因为索引前的数组皆为有序的,索引只要确定当前索引的数据的为止即可
            for(int j=i;j>0 && a[j] < a[j-1];j--) {
                temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
            print(i +"",a);
        }
       
        print("result",a);
        return a;
    }
   
    public static void main(String[] args) {
        Integer[] a = {2,1,5,9,0,6,8,7,3};
        (new InsertionSort()).sort(a);
    }   
}

运行结果:

init: [2 ,1 ,5 ,9 ,0 ,6 ,8 ,7 ,3]

1: [1 ,2 ,5 ,9 ,0 ,6 ,8 ,7 ,3]

2: [1 ,2 ,5 ,9 ,0 ,6 ,8 ,7 ,3]

3: [1 ,2 ,5 ,9 ,0 ,6 ,8 ,7 ,3]

4: [0 ,1 ,2 ,5 ,9 ,6 ,8 ,7 ,3]

5: [0 ,1 ,2 ,5 ,6 ,9 ,8 ,7 ,3]

6: [0 ,1 ,2 ,5 ,6 ,8 ,9 ,7 ,3]

7: [0 ,1 ,2 ,5 ,6 ,7 ,8 ,9 ,3]

8: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]

result: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]

效率:如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)

四、希尔排序

把记录按步长 gap 分组,对每组记录采用直接插入排序方法进行排序。

随着步长逐渐减小,所分成的组包含的记录越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。

选择排序、插入排序和希尔排序

实现代码:

public class ShellSort extends SortBase {

@Override
    public Integer[] sort(Integer[] a) {
        // TODO Auto-generated method stub
        print("init",a);
        Integer h = a.length;
        Integer temp = 0;
        while(h >= 1) {
            for(int i=h;i<a.length;i++) {
                for(int j=i;j>=h && a[j] < a[j-h];j -= h) {
                    temp = a[j];
                    a[j] = a[j-h];
                    a[j-h] = temp;
                   
                }
            }
            h /= 9;
        }
        print("result",a);
        return a;
    }
   
    public static void main(String[] args) {
        Integer[] a = {2,1,5,9,0,6,8,7,3};
        (new ShellSort()).sort(a);
    }
}

运行结果:

init: [2 ,1 ,5 ,9 ,0 ,6 ,8 ,7 ,3]

1: [0 ,1 ,5 ,7 ,2 ,6 ,8 ,9 ,3]

2: [0 ,1 ,2 ,6 ,3 ,7 ,5 ,9 ,8]

3: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]

result: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/6b58977d0224e16586e9dd728680f448.html