算法入门学习----1.3插入排序

ゞ浴缸里的玫瑰 2022-06-01 06:43 78阅读 0赞

# 一、插入排序的原理 #

# 一个数组a\[\]有N个元素,首先第一个数不动：  第一次：将第二个数从后往前依次和前面一个数（有序数组）进行比较，并插入到合适位置M，然后将原来位置在M(包括M) 到原来数组第一个数 均后移一位（如果需要插入的数原来位置和它所要插入的数字位置相同，那么无须移动数组）(最差情况比较1次)。     第二次：将第三个数从后往前依次和前面两个数（有序数组）进行比较，并插入到合适位置M，然后将原来位置在M(包括M) 到原来数组第二个数 均后移一位（如果需要插入的数原来位置和它所要插入的数字位置相同，那么无须移动数组）(最差情况比较2次)。  第三次：将第四个数从后往前依次和前面三个数（有序数组）进行比较，并插入到合适位置 M，然后将原来位置在M(包括M) 到原来数组第三个数 均后移一位（如果需要插入的数原来位置和它所要插入的数字位置相同，那么无须移动数组）(最差情况比较3次)。     ................  第N-1次：将第N个数和前面N-1个数（有序数组）进行比较，并插入到合适位置 M，然后将原来位置在M(包括M) 到 原来数组第N-1个数 均后移一位（如果需要插入的数原来位置和它所要插入的数字位置相同，那么无须移动数组）(最差情况比较n-1次)。 #

# 二、插入排序的时间复杂度和空间复杂度 #

# 时间复杂度：1+2+3+......(n-1)=n\*(n-1)/2 所以时间复杂度为 n^2   空间复杂度：①最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0；    ②最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；    ③平均的空间复杂度为：O(1)；  稳定性： 稳定 #

# 三、插入排序的代码实现Java #

public class ChaRu {
    	public static void main(String[] args){  
            int[] arr=new int[]{1,5,6,89,4,6,12,48,5,23};  
            charudemo(arr);  
        }  
        public static void show(int[] arr){  //输出函数  
            for(int a: arr){  
                System.out.println(a);  
            }  
        }  
        public static void charudemo(int[] arr){  
        	for(int n=1;n<arr.length;n++){            //表示第几次插入   
        		for(int m=n;m>=0;m--){               //从后往前依次和有序数组比较   			
        			if(arr[n]<arr[m-1]){             //如果要插入的数比前面的小，那么原来的有序数移动
        				arr[m]=arr[m-1];
        			}
        			else{                            //如果要插入的数不小于前面的数，那么插入。
        				arr[m]=arr[n];
        			}
        		}
        	}
            show(arr);  
        }  
    }