【数据结构】【排序】插入排序

       插入排序的思想是将数组分为前面有序和后面无序两部分，每次取后面无序部分的第一个数插入到前面有序的部分中，使得插入之后前面有序的那一部分仍然有序。

 

import java.util.Scanner;

public class InsertSort{
	public static void main(String args[]){
		Scanner scanner=new Scanner(System.in);
		int total=scanner.nextInt();
		int[] array=new int[1024];
		for(int i=0;i<total;i++){
			array[i]=scanner.nextInt();
		}
		//total是数组长度
		insertSort(array,total);
		output(array,total);
	}
	public static void output(int[] array,int total){
		for(int i=0;i<total;i++){
			System.out.print(array[i]+" ");
		}
		System.out.println();
	}
	public static void insertSort(int[] array,int total){
		int temp;
		int j;
		for(int i=1;i<total;i++){
			temp=array[i];
			for(j=i-1;j>=0;j--){
				if(array[j]>temp){
					array[j+1]=array[j];
				}else{
					break;
				}
			}
			array[j+1]=temp;
		}
	}
}

    测试数据

 

输入：
10
1 4 7 8 5 2 3 6 9 0
输出：
0 1 2 3 4 5 6 7 8 9