数据结构与算法(java版)第二季 - 2 插入排序

目录

概念

逆序对

插入排序的优化---将交换变成是挪动

二分搜索

插入排序 – 二分搜索优化

 二分搜索实现插入排序代码的实现

---

概念

如上图所示，就像是在前面已经是拍好顺序的，后面的是需要进行新的排序。

执行流程是如下所示：

①在执行的过程之中，插入排序是分为2各部分：头部是已经进行排序好之后，尾部是需要进行相应的排序的。

②从头开始扫描每一个元素：每当扫描到一个元素，就是将它插入到头部合适的位置，使得头部是有序的。

理解的过程是最开始的地方的第一张牌我是抓在手里的,从下标为1开始不断的进行抓牌的过程.之后后面的牌逐渐的跟前面的牌进行一个比较,直到相应的牌的顺序是一致的.

public class InsertSort extends Comparable> extends Sort{
    protected void sort() {
        for(int begin = 1;begin < array.length; begin++)
        {
            int cur = begin;
            while(cmp(cur,cur-1) < 0 && cur > 0)//这里是需要一个相应的cur>0
            {
                swap(cur,cur-1);
                //进行相应的交换之后,是需要将原来的数量进行一个减一的过程,依次跟前面进行一个比较
                cur--;
            }
        }
    }
}

逆序对

什么叫做逆序对????         数组<2,3,8,6,1>之中的逆序对为:<2,1><3,1><8,1><8,6><6,1>,共有五个逆序对.

 如上图所示的逆序对,可以得知

插入排序的优化---将交换变成是挪动

 如上所示:思路是将原始的交换过程变成是相应的一个挪动的过程.

①先将原始想要进行插入的元素使用一个备份,将其保存下来

②头部有序数据之中比待插入元素大的,都朝着尾部方向移动一个位置

③讲待插入的元素放入合适的位置

优化的代码是如下所示:

public class InsertSort extends Comparable> extends Sort{
    protected void sort() {
       
        //优化的过程---将交换变成挪动的过程
        for(int begin = 1;begin < array.length; begin++)
        {
            int cur = begin;
            Integer v = array[cur];
            while(cur > 0 && cmp(v,array[cur]- 1) < 0)
            {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = v;
            
        }
    }
}

通过进行一个验证可以知道,优化并不是很明显的,也就是说进入相应的一个while循环是越多的,优化是越明显的.

二分搜索

• 概念

如果是有序数组，可以使用二分搜索，最坏时间复杂度：O(logn) 二分搜索的过程就是逐渐进行除以2的过程.

• 思路

 begin是相当于最初的一个元素的索引,end表示的最后的一个元素的索引+1.

假设在[begin,end)范围内搜索某个元素v,mid==(begin+end)/2

 二分搜索的过程就是进行一个找出位置的过程,简单容易理解.

• 实例

•  实现过程与代码

public class BinarySearch {
    public static int indexOf(int[] array,int v)
    {
        if(array == null || array.length == 0) return -1;
        int begin = 0;
        int end = array.length;
        while(begin < end)
        {
            int mid = (begin + end) >> 1;
            if(v < array[mid])
            {
                end = mid;
            }else if(v < array[mid])
            {
                begin = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
}

插入排序 – 二分搜索优化

◼ 在元素 v 的插入过程中，可以先二分搜索出合适的插入位置，然后再将元素 v 插入

• 思路(找到元素v的插入位置)

 

 插入位置的选择

  /**
     * 查找v在有序数组array之中待插入的位置
     * 在元素v的插入过程,可以使用二分搜索出合适的插入位置,然后再讲元素v插入
     * 要求二叉搜索方法返回的插入位置:第一个大于v的元素位置
     */
    public static int search (int[] array,int v)
    {
        if(array == null || array.length == 0) return -1;
        int begin = 0;
        int end = array.length;
        while(begin < end)
        {
            int mid = (begin + end) >> 1;
            if(v < array[mid])
            {
                end = mid;
            }else
            {
                begin = mid + 1;
            }
        }
        return begin;
    }

 二分搜索实现插入排序代码的实现

思路一:不进行封装

public class InsertSort3extends Comparable> extends Sort{
    protected void sort() {
 
        for(int begin = 1;begin < array.length; begin++)
        {
            Integer v= array[begin];
            int insertIndex = search(begin);
            
            //将[insertIndex,baegin)范围内的元素向右边挪动一个单位
            for(int i = begin; i > insertIndex; i--)
            {
                array[i] = array[i-1];
            }
            array[insertIndex] = v;
        }
    }
 
    /**
     * 利用二分搜索找到 index 位置元素的待插入位置
     * 已经排号顺序数组的取件范围是 [0,index)
     */
    private int search(int index)
    {
        
        int begin = 0;
        int end = index;
        while(begin < end)
        {
            int mid = (begin + end) >> 1;
            if(cmp(array[index],array[mid])<0)
            {
                end = mid;
            }else
            {
                begin = mid + 1;
            }
        }
        return begin;
    }
}

思路二:进行相应的封装

public class InsertSort4extends Comparable> extends Sort{
    protected void sort() {
 
        for(int begin = 1;begin < array.length; begin++)
        {
            insert(begin,search(begin));
        }
    }
 
    /**
     * 将source位置的元素插入到相应的dest之中
     */
    private void insert(int source,int dest)
    {
        Integer v = array[source];
        for(int i = source; i > dest; i--)
        {
            array[i] = array[i-1];
        }
        array[dest] = v;
    }
 
    /**
     * 利用二分搜索找到 index 位置元素的待插入位置
     * 已经排号顺序数组的取件范围是 [0,index)
     */
    private int search(int index)
    {
        
        int begin = 0;
        int end = index;
        while(begin < end)
        {
            int mid = (begin + end) >> 1;
            if(cmp(array[index],array[mid])<0)
            {
                end = mid;
            }else
            {
                begin = mid + 1;
            }
        }
        return begin;
    }
}

这里应当注意的是,使用二分搜索之后,知识减少了比较次数,但是插入排序的平均时间复杂度仍然是O(n^2).