3.插入排序(小样本,基本有序时最快;稳定)

插入排序在工业和实际中应用比较多,当样本量小于60且基本有序时使用;

使用插入排序,可以保证排序数组的稳定性.经常在归并排序和快排中子数组规模小时使用.

普通插入排序:

//插入排序(相对冒泡和选择较好,但时间复杂仍为n**2,空间为1,稳定)
//思想:同打牌,将新摸到的牌插入到已排好的牌面上
//操作:每次将后面的数插入到前面已排好的数组中
    static void insertionSort(int[] a ){  //NK
        for(int j=1;j<a.length;j++) {  //N
            for (int i = j; i > 0; i--) { //k
                if (a[i] < a[i - 1]) swap(a, i, i - 1);
            }
        }

折半插入(优化:运用二分查找思想找到插入位置)

 static void halfInSort(int[] a ){
        //定义边界和中间值
        int left,mid,right;
        //定义一个中间变量存待插入的值
        int temp;
        for(int j=1;j<a.length;j++) {
            //将各个值初始化
            temp=a[j];
            left=0;
            right=j-1;
            //用二分查找 找到需要插入的位置下标
            while(left<=right)
            {
                //适当优化,当left,right过大时,不会超过int范围
                mid=left+((right-left)>>1);
                //如果要插入值比a[mid]小,说明在mid左边,
                // 将上边界缩小为mid-1
                if(temp<a[mid]){
                    right=mid-1;
                }else{
                    //否则就是temp比中间值大,在右边区域
                    //将下边界调大为mid+1
                    left=mid+1;
                }
            }
            //当跳出循环时,已找到将要插入的位置,即下标值为left的地方
            //将插入位置的数依次向后移动,并将temp插入
            for (int i = j; i > left; i--) {
                a[i]=a[i-1];
            }
            a[left]=temp;
        }

pairInsert(优化:一次插入两个)

思想:减少了二分查找的次数

1.将待插入两个数比较大小,通过二分找到较小数应插入的位置;

2.将较小数插入;

3.再从较小数位置到最后找到较大数应插入位置,插入较大数.

拓展:二分查找(有序数组查找)

因为插入排序的优化中,使用了二分的思想,所以可以顺便撸出二分查找代码.

前提:数组已排序,查找数字在数组中的位置,不存在返回-1

static int halfSearch(int[] a,int num){
        //left为左边界,right为右边界,mid为中间值,index为查找数在数组的位置
        //初始化
        int left=0;
        int right=a.length-1;
        int index=-1;
        int mid=-1;
        //核心比较代码
        while (left<=right){
            mid=left+((right-left)>>1);
            //等于则赋值返回
            if(a[mid]==num){
                index = mid;
                break;
            }else if (a[mid]<num){//大于a[mid],在右边区域
                left=mid+1;//左边界移动
            }else{//小于a[mid],在左边区域
                right=mid-1;//右边界移动
            }
        }
        //返回index
        return index;
    }