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

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

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

**过程：**  
![这里写图片描述][20150606132917006]

**用自己的话说**：  
用一个索引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,

![这里写图片描述][20161015182529194]

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

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;
            }
        }

[20150606132917006]: /images/20220716/4cd375479e5d40c881ff8aea07e3f6bf.png
[20161015182529194]: /images/20220716/ed7422caf6e148318ae1b22ee0ac62a7.png
[20161016024838775]: /images/20220716/c50d26b21fb844a3b02b0e22e2a8a2a8.png