一头扎进算法导论-插入排序-蒲公英云

一头扎进算法导论-插入排序

梦里梦外; 2022-07-16 08:27 238阅读 0赞

定义：直接插入排序是一种简单的排序方法，她的基本思想是依次将每个记录插入到一个已排好序的有序表中去，从而得到一个新的、记录数增加1的有序表，就好比斗地主抓牌排序的这么一个过程

过程：
这里写图片描述

用自己的话说：
用一个索引key表示当前捉到的牌，如图中红框所示。
用一个索引i表示已经排序好的牌（从key牌左边开始轮询），如图中黑框所示意。
从索引2开始捉牌，每次捉牌时进行三个步骤

1.记录key的牌的值
2.轮询排序好的牌，如果排序好的牌比当前牌大，则左移
3.将当前牌插入排序好的牌中

代码实现：

public int[] sort(int[] a){
        for(int key=1;key<a.length;key++){
   //这里做一个大循环
            int keyValue = a[key];//记录当前数
            int i = key-1;//记录当前牌左边第一个坐标
            while(i>-1&&a[i]<keyValue){
   //当坐标未到尽头且选取到的数大于当前数
                a[i+1]=a[i];//置换
                --i;//下一个数
            }
            a[i+1]=keyValue;//插入当前数
        }
        return a;
    }

测试：

public static void main(String[] args){
        int[] a= new int[]{
   5,8,3,4,7,2,7,4,6,8,2,5,8,9,0,3,2,7,4,6,3,1};
        a = new Insertion().sort(a);
        for(int i : a){
            System.out.print(i+",");
        }
    }

结果：

9,8,8,8,7,7,7,6,6,5,5,4,4,4,3,3,3,2,2,2,1,0,

这里写图片描述

—————-2016-10-16 用递归完成子序列排序——————–
这里写图片描述

public int[] sortByRecursion(int[] a){
        for(int k=1;k<a.length;k++){
            int value = a[k];
            int i = k-1;//左边第一个数坐标
            int j = sortChild(a,value,i);
            a[++j] = value;
        }
        return a;
    }
    /** * jiangjintai * 2016年10月16日 * @param a * @param value * @param i */
    private int sortChild(int[] a, int value, int i) {
        if(i>-1&&a[i]>value){
   //临界条件
            a[i+1]=a[i--];//置换
            return sortChild(a, value, i);
        }else{
            return i;
        }
    }