数组（六）--插入排序

Bertha 。 2021-09-14 08:16 282阅读 0赞

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：

![1342520948_8667.jpg][]

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

public class Demo10 {
    	public static void main(String[] args) {	
    		int arr[] = { 8,6,9,7,13,12,4 };
    		insertSort(arr);
    		printArray(arr);
    	}
    	
    	public static void insertSort(int[] arr){  
            int length=arr.length; //数组长度  
            int j;               //当前值的位置  
            int i;               //指向j前的位置  
            int key;             //当前要进行插入排序的值  
            //从数组的第二个位置开始遍历值  
            for(j=1;j<length;j++){  
                key=arr[j];  
                i=j-1;  
                //a[i]比当前值大时，a[i]后移一位,空出i的位置，好让下一次循环的值后移  
                while(i>=0 && arr[i]>key){  
                    arr[i+1]=arr[i]; //将a[i]值后移  
                    i--;         //i前移  
                }//跳出循环(找到要插入的中间位置或已遍历到0下标)  
                arr[i+1]=key;    //将当前值插入  
            }  
        }  
    	
    	//打印数组
    	public static void printArray(int[] arr){
    		System.out.print("[");
    		for(int i=0;i<arr.length;i++){
    			if(i!=arr.length-1)
    				System.out.print(arr[i]+" ");
    			else
    				System.out.print(arr[i]+"]");
    		}
    	}
    
    
    }

[1342520948_8667.jpg]: https://img-my.csdn.net/uploads/201207/17/1342520948_8667.jpg