[数据结构与算法]Java实现插入排序

插入排序

1. 插入排序 时间复杂度:O(N^2)

2. 核心思想:使用1角标对应的元素和0角标进行比较，如果前面元素大,向右移动,确定角标1对应的元素的位置,再次使用2角标对应的元素依次和1和0都元素比较 依次这样比较…

3.插入排序图解

4.代码实现

public class InsertSortTest {
    public static void main(String[] args) {
        Integer[] arr = {34,8,64,51,32,21} ;
        System.out.println("排序前:");
        printArr(arr);

        insertSort(arr) ;
        System.out.println("排序后:");
        printArr(arr);

    }
    //插入排序功能
    private static void insertSort(Integer[] arr) {
        //定义一个变量j
            int j ; //j记录当前角标的变化

            //定义变量 : p:表示一个比较次数 p=1,2,3,4,5 (每一移动的元素的位置)
            for(int p = 1 ; p < arr.length ; p ++ ){ //比较次数     p=2
                //定义临时变量temp
                Integer temp = arr[p] ;    //temp = 8;          temp = 64
                //开始比较
                for(j = p ; j>0 && temp.compareTo(arr[j-1])<0; j--){
                	//j=1 ; 1>0 && 8<34 j-- : j= 0
                    //j=2 ; 2>0 && 64<32
                    //数据移动
                    arr[j] = arr[j-1] ;
                }

                //确定temp的位置:8的位置   64的位置:p=2
                arr[j] = temp ;         // 没有移动

        }

    }
    
//遍历功能
    public static void printArr(Integer[] arr){
        System.out.print("[");
        for(int x = 0 ; x < arr.length ; x ++){
            if(x == arr.length -1){
                System.out.println(arr[x] +"]");
            }else{
                System.out.print(arr[x]+", ");
            }
        }
    }
}

5.运行截图