插入排序

介绍

对于少量元素的排序，它是一个有效的算法。插入排序就像是打扑克牌，每次摸牌都将随机摸一张牌，并放到左手的正确位置。

代码

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	int [] arr = new int[10];
	//随机输入十个数
	for(int i=0;i<arr.length;i++) {
		arr[i] = input.nextInt();
	}
	
	for(int i=1;i<arr.length;i++) {
		int a = arr[i];		//将需要插入的元素备份
		int j = i-1;
		//将比插入元素大的元素后移
		while(j>0&&arr[j]>a) {
			arr[j+1] = arr[j];
			j = j-1;
		}
		arr[j+1] = a;		//插入元素
 	}
	//遍历输出
	for (int i : arr) {
		System.out.println(i);
	}
}
}

分析

运行时间：an^2+bn+c(最坏情况)

时间复杂度：n^2

总结

插入排序代码量很少，对于少量元素排序还是很不错的选择，