import java.util.Scanner;
import java.lang.Double;

public class TestInsertionSort {
	int [] array;

	public TestInsertionSort() {
		// TODO Auto-generated constructor stub
		System.out.println("清输入要排序的个数： ");
		Scanner sc  = new Scanner(System.in);
		int number = sc.nextInt();
		array = new int [number];
		System.out.println("请输入要排序的数：");
		for(int i = 0; i < number; i++) {
			array[i] = sc.nextInt();
		}
		sc.close();
	}
	//插入排序
	public void InsertionSort() {
		for(int j = 1; j < array.length; j++) {
			int key = array[j];
			int i = j - 1;
			while(i > 0 && key < array[i]) {
				array[i+1] = array[i];
				i--;
			}
			array[i+1]  = key;
		}
	}

	//归并排序
	public void MergeSort(int [] arry, int start, int end) {
		if(start < end) {
			int temp = (start + end) / 2;
			MergeSort(arry, start, temp);
			MergeSort(arry, temp + 1, end);
			Merge(arry, start, temp, end);
		}
	}

	public void Merge(int [] arry, int start, int temp, int end) {
		int [] a = new int [temp - start + 2];
		int [] b = new int [end - temp + 1];
		for(int i = 0; i< a.length - 1; i++) {
			a[i] = arry[start + i];
		}
		for(int i = 0; i < b.length - 1; i++) {
			b[i] = arry [temp + 1 + i];
		}
		a[temp - start + 1] = (int) Double.NEGATIVE_INFINITY;
		b[end - temp] = (int) Double.NEGATIVE_INFINITY;
		int i = 0;
		int j = 0;
		for(temp = start; temp <= end; temp++) {
			if(a[i] < b[j]) {
				arry[temp] = a[i];
				i++;
			}
			else {
				arry[temp] = b[j];
				j++;
			}
		}

	}

	//冒泡排序
	public void BubbleSort(int [] arry) {
		for(int i = 1; i < arry.length; i++) {
			for(int j = i - 1; j > 0; j--) {
				if(arry[j] < arry[j - 1])
					arry[j - 1] = arry[j];
			}
		}
	}

	public void print() {
		System.out.println("输出排序好的数据： ");
		for(int i = 0; i < array.length; i++) {
			System.out.println(array[i] + " ");
		}
	}
	public static void main(String[] args) {
		TestInsertionSort sort = new TestInsertionSort();
		//sort.MergeSort(sort.array, 0, sort.array.length);
		sort.InsertionSort();
		sort.print();
	}
}