插入排序

插入排序的过程可以联想到打扑克时揭一张牌然后将其到手中有序纸牌的合适位置上。比如我现在手上的牌是7、8、9、J、Q、K，这时揭了一张10，我需要将其依次与K、Q、J、9、8、7比较，当比到9时发现大于9，于是将其插入到9之后。对于一个无序序列，可以将其当做一摞待揭的牌，首先将首元素揭起来，因为揭之前手上无牌，因此此次揭牌无需比较，此后每揭一次牌都需要进行上述的插牌过程，当揭完之后，手上的握牌顺序就对应着该序列的有序形式。

image.png

package mySort;

public class insertSort {

    
    public static void main(String arr1[]){
        int arr[]={1,4,2,3,5};
        printArray(arr);
        insertSort(arr);
        printArray(arr);
    }
    public static void printArray(int[] arr){
        
        
        for(int i=0;i<arr.length;i++){
            
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    public static void swap(int arr[],int i,int j){
        
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    private static void insertSort(int[] arr) {
        
        for(int i=1;i<arr.length;i++){
            
            for(int j=i-1;j>=0&&arr[j]>arr[j+1];j--){
                swap(arr,j,j+1);
            }
//          int j=i-1;
//          while(j>=0&&arr[j]>arr[j+1]){
//              swap(arr,j,j+1);
//              j--;
//          }
            
            
        }
        
    }
    
    
    
    
}