简单_插入排序(Insertion-sort)

package sunfa.sort;

import java.util.Arrays;
import java.util.Random;

public class InsertionSort {
	public static void main(String[] args) {
		Random ran = new Random();
		int[] a = new int[10];
		for (int i = 0; i < a.length; i++) {
			a[i] = ran.nextInt(100);
		}
		System.out.println(Arrays.toString(a));
		insertionSort(a);
		System.out.println(Arrays.toString(a));
		Arrays.sort(a);
		System.out.println(Arrays.toString(a));
	}

	/**
	 * 插入排序算法(insertion-sort)适合少量数据排序的算法
	 * @param a
	 */
	public static void insertionSort(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int key = a[i];//保存刚才摸到的那张牌
			for (int k = 0; k < i; k++) {//0-i 为左手拿着的牌的集合
				if (a[i] < a[k]) {//将刚才抓到的那张牌依次和左手的牌进行比较，目的是为了找到它应该放的位置
					for (int j = i - 1; j >= k; j--) {
						a[j + 1] = a[j];//找到位置之后将该位置后面的牌的位置后移
					}
					a[k] = key;//插入牌到适合的位置
					break;
				}
			}
		}
	}
}