图解数据结构和算法(一) · 插入排序(Insertion Sort) java实现

图解数据结构和算法(一) · 插入排序(Insertion Sort) java实现

java实现插入排序算法

简介:

插入排序的核心思想: 左边的元素是有序数组,然后通过和左边元素相对比,找到合适的位置进行插入,并且把插入位置之后的元素往后移动

复杂度

  • 时间复杂度:所有元素都是逆序的情况下,则需要进行1+2+3+4+....n-1 = n2 = O(n2)

  • 空间复杂度:因为在排序移动的过程中没有创建新的数据结构和节点,所以空间复杂度为O(1)

排序过程如下

insertSort

思路

  • 索引从第二个开始

  • 将选中的节点与前一个对比,如果选中的节点小于前面的节点,则将前一个节点往后移动

  • 直到遍历到选中的节点大于前一个节点,停止,记录当前索引值,将选中的节点插入当当前位置

java实现

public class InsertSort {

    private static Integer[] sortArrays = {256,50,354,64,213,65,323,65,243};

    //todo:正叙排列
    public static void main(String[] args) {

        for (int i = 1; i < sortArrays.length; i++) {
            //记录当前索引值
            Integer curNumber = sortArrays[i];
            //获取front索引值
            int j = i -1;
            while (j >= 0 && sortArrays[j] > curNumber){
                //如果front比current大,则需要往前移动
                sortArrays[j + 1] = sortArrays[j];
                //一直往前遍历判断
                j --;
            }
            //j的索引,即是停止往前遍历的索引位置,所以这儿就是需要插入的索引地方
            sortArrays[ j + 1] = curNumber;
        }
    }

}

这种排序方式,从上面的动图可以看到,当元素很多时,并且刚好是完全逆序的情况,效率会非常低,这也是插入排序的一个缺点

下一章(图解数据结构和算法(二) · 选择排序)

# java  排序 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×