vlambda博客
学习文章列表

普通插入排序

核心思想：脑海里要有个虚拟数组，从左往右，是个排好序的。具体做法，从第二个数字开始，每个数字都试图跟它前一个比较，如果小于前一个并做交换，并重复这个动作，直到前一个数不存在，或者，前一个比他小，或者相等的时候停下来。

static int[] arr = {2, 11, 1, 8, 7, 18, 9, 0, 6, 5, 3, 20, 4};
  @Test
    public void insertSort(){
        for (int i = 0; i < arr.length; i++) {
            int  temp = arr[i];
            for (int j = i-1; j >=0; j--) {
                if(arr[j]>arr[j+1]){
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                }else {
                    break;
                }

            }
        }
        System.out.println(Arrays.toString(arr));
    }

二分插入排序

二分插入即：不再从末尾一个个比较交换，通过二分法来查出应该插入的位置

• 总体思想：
• 1 通过二分法找到应该插入的位置
• 2 完成插入并且保证插入后有序

1 通过二分法找到应该插入的位置

二分插入是个递归过程，而递归的出口是找到要插入的位置，

• 启始时：recursionBinaryInsert( arr,  low,  hight, target)
• 递归 mid= (low+hight)
  左半部分：recursionBinaryInsert( arr,  low,  mid, target)
  右半部分：recursionBinaryInsert( arr,  mid+1,  hight, target)

「一直递归到  low=hight 时就是要插入的位置！！！」 ，不理解这句话，可以看下文章末尾。

2 完成插入并且保证插入后有序

如何做？还是画图比较容易理解。

1. 最左侧插入

2. 中间侧插入

3. 最右侧插入

注意：虽然画了三种插入情况，但实际上，中间侧插入，也可以认为是，索引0的右侧，或者说索引1的左侧，总体来说，只有两种操作，「左插入」，与 ，「右插入」。

「总结规律：只要找到，二分插入的位置后，对应位置右侧的有序数组整体向右移动一位即可！」

下面为具体的代码：

 static  int[] arr = {2, 11, 1, 8, 7, 18, 9, 0, 6, 5, 3, 20, 4};
    @Test
    public void insertSortPlgus() {
        for (int i = 1; i < arr.length; i++) {
            //记得有个默认的前提就是，数字前面是拍好序的
            recursionBinaryInsert(arr, 0, i, i);
        }
        System.out.println("排序结果"+Arrays.toString(arr));
    }
    /**
 * 有个特点 ，每次插入都是，虚拟数组的末尾外相邻的第一个元素
 * @param arr
 * @param low
 * @param hight
 * @param target 此轮要插入虚拟数组的目标元素，也是虚拟数组最后一位外，的第一个相邻的 （包含此次要插入的）
 */
    private void recursionBinaryInsert(int[] arr, int low, int hight, int target) {
        if (hight == low) {
            int temp = arr[target];
            if (arr[target] <= arr[low]) {
                System.arraycopy(arr, low, arr, low + 1, target - low);// 对应需要插入的位置，整体向右移动1位
                arr[low] = temp; //最终放入
            }
            return;
        }
        int mid = (low + hight) / 2;   // 向下取整
        // = 一定要有，对于相等元素也要比较，不然就拉下了
        if (arr[mid] >= arr[target]) {
            recursionBinaryInsert(arr, low, mid, target);
        } else if (arr[mid] < arr[target]) {
            recursionBinaryInsert(arr, mid + 1, hight, target);
        }
    }

当时我写的时候，想了好久 怎样才能知道要插入的位置，我在想递归至索引为  low=hight  时，我当时在想应该插入这个元素的左侧还是右侧，如果这么想，就进坑了，正确的思想既不是左侧也不是右侧，恰恰是当前的位置！！！

原因：就在于当在右侧递归时，  mid+1  ,看如下图：

赠人玫瑰，手有余香， 如果不错就点赞鼓励下哦。