插入排序 O(nlogn)

  • Post author:
  • Post category:其他


1.基本原理

是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

2.代码实现

public static void insert(int[] arr)
    {    //插入排序   O(nlogn)
        int j=0;     //将数据放入到相应的位置
        for(int i=1;i<arr.length;i++)
        {
            //定义临时变量进行存储
            int a=arr[i];
            //将当前数据插入到已经有序的数字中(倒着往前找)
            for(j=i-1;j>=0;j--)
            {
                if(arr[j]>a)
                {      //做判断找到相关位置,如果前面的数大于当前数,那就将前面的数往后移动
                    arr[j+1]=arr[j];
                }else{
                    break;  //在此之前前边的数已经有序,arr[i]为目前最大值
                }

            }
            //j+1是因为前边for循环完后j还会自减一次
            arr[j+1]=a;   //将当前的数放入正确的位置
        }
    }



版权声明:本文为weixin_46047193原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。