美文网首页程序员
排序第二记——插入排序(插入、Shell排序)

排序第二记——插入排序(插入、Shell排序)

作者: AceCream佳 | 来源:发表于2017-04-03 21:00 被阅读0次

    这次直入主题,我今天要复习的是插入排序!插入排序分为“直接插入”和“Shell排序”,Shell排序就是希尔排序,可以看做是直接插入排序从成熟体进化为完全体~
    好的直接来看插入排序:

    直接插入排序

    我们先说一下插入排序的原理:

    通过对未排序的数据执行逐个插入到合适的位置完成排序工作。

    • 1.首先对数组前两个数据进行从小到大排序
    • 2.将第三个数据与排好序的两个数据比较,插入合适的位置。
    • 3.第四个同样方式插入到他们三个中。
    • 4.不断重复,直到结束。
    • 时间复杂度: 平均:O(n^2) 最佳:O(n) 最坏:O(n^2)
    • 空间复杂度: O(1)
    • 稳定性: 稳定

    这个听起来比冒泡难一些,但是其实想象力丰富一些,就会觉得这个这个很简单~给个图片就懂了!
    我又去百科盗图了:

    插入排序

    图片的简单明了吧?就是从第二个值开始依次去取。然后每次都比较,然后把每次取的数字,放到该放的位置上。
    直接看代码吧:手敲代码:

    /**
     * Created by AceCream on 2017/3/20.
     *
     * 插入排序(Insertion Sort)
     * 原理:通过对未排序的数据执行逐个插入到合适的位置完成排序工作。
     * 1.首先对数组前两个数据进行从小到大排序
     * 2.将第三个数据与排好序的两个数据比较,插入合适的位置。
     * 3.第四个同样方式插入到他们三个中。
     * 4.不断重复,直到结束。
     *
     * 时间复杂度: 平均:O(n^2)   最佳:O(n)   最坏:O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 稳定
     *
     */
    public class InsertSort {
        public static void main(String[] args) {
                int value[] = {12,15,9,20,6,31,24};
                InsertSort insertSort = new InsertSort();
                insertSort.insertSort(value);
                System.out.print("最终结果 ");
                for (int result : value) {
                    System.out.print(result+" ");
                }
        }
        private void insertSort(int[] value) {
            //temp值待命
            int temp;
            for (int i=1;i<value.length;i++){
                //从第二个数据开始取 每轮的检测数据都先放temp里
                temp = value[i];
                int j = i-1;
                while (j>=0 && temp<value[j]){
                    //如果比较的值,比temp大,就让这个值往后去。temp继续比较。。。碰到比它小的,就在其后面落下(后面这句是循环外放下的)
                    value[j+1]=value[j];
                    j--;
                }
                //没有比它小的就放回去,有的话就放到应该在的位置
                value[j+1]=temp;
            }
        }
    }
    

    我都注释的比较详细了~虽然我自己也总忘这个排序。

    好的吃完甜点,我们开始今天的主菜——Shell排序

    希尔排序

    希尔排序是理论上效率最高的排序。但是!但是仅仅是理论上,因为在实践中的使用,希尔排序还是被快排击败了,两种排序都不太稳定,但是整体的试验中,快排还是略胜一筹~
    希尔排序,也叫做缩小增量排序,其执行方式,我个人觉得还是很变态的。
    还是看步骤吧:

    • 1.将n个元素的数组分为n/2个数字序列:第一个数据和第n/2+1个数据为一对...
    • 2.一次循环使每个序列对排好
    • 3.变为n/4个序列,再次排序。
    • 4.不断重复,周而复始,随着序列变为1,排序完成
    希尔排序过程

    看这个图,应该是可以理解的,它是分来,然后一一对应,然后比较,单独排序,直到最后,排列整齐。。。
    当初觉得这个思想好强!但是!我觉得简单了解其原理就足够了。当然,想手敲也是可以的,但觉得必要性不是那么强,因为应用情况下,我宁可选择快排。

    /**
     * Created by AceCream on 2017/3/22.
     * 希尔排序(ShellSort)
     * 希尔排序效率很高!所以也是很常用的一种排序。
     * 基于插入排序的思想:缩小增量排序
     * 步骤:
     * 1.将n个元素的数组分为n/2个数字序列:第一个数据和第n/2+1个数据为一对...
     * 2.一次循环使每个序列对排好
     * 3.变为n/4个序列,再次排序。
     * 4.不断重复,周而复始,随着序列变为1,排序完成
     *
     * 时间复杂度: 平均:O(n^1.3)   最佳:O(n)   最坏:O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     *
     */
    public class ShellSort {
    
        public static void shellSort(int a[]){
            int gap;
            int lenth = a.length;
            for (gap=lenth/2;gap>0;gap/=2){ //从数组的第gap个元素开始  分出来循环几次
                for (int i=0;i<gap;i++){    //分出来有多少组
                    //直接插入排序
                    for (int j=i+gap;j<lenth;j+=gap){
                        if (a[j]<a[j-gap]){
                            int temp = a[j];
                            int k = j-gap;
                            while (k>=0&&temp<a[k]){
                                a[k+gap]=a[k];
                                k -= gap;
                            }
                            a[k+gap]=temp;
                        }
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            int value[] = {49,27,46,55,4,13,38,65,97,26};
            shellSort(value);
            System.out.print("最终结果 ");
            for (int result : value) {
                System.out.print(result+" ");
            }
        }
    }
    

    这一次我没有选择在线手敲,私下每次我需要使用的时候我会回来看看毕竟学习不是背诵,最主要的是:了解其思想

    相关文章

      网友评论

        本文标题:排序第二记——插入排序(插入、Shell排序)

        本文链接:https://www.haomeiwen.com/subject/gmmoottx.html