插入排序算法

插入算法的基本流程

假设有n个数，左边是已经排好序的，右边是没进行排序的。

设数组有n个元素，下标从第二个元素开始和左边的元素开始比较，后面依次下标递增，最后让左边的元素都排序完成。

下面是JAVA代码的实现:

public interface Sort {
	public void sort(int []arr) throws InterruptedException;
}

public final class SortInsert implements Sort {

	public SortInsert() {

	}

	static void printNow(int[] arr, PrintStream out) {
		for (int i = 0; i < arr.length; i++) {
			out.print(arr[i] + " ");
		}
		out.print("\n");
		try {
			Thread.sleep(50); //主要是为了顺序打印
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}

	@Override
	public void sort(int[] arr) throws InterruptedException {
		printNow(arr, System.out);
		System.out.println("start.......");
		Thread.sleep(50);
		int key = 0;
		for (int j = 1; j < arr.length; j++) {
			key = arr[j];
			int i = j - 1;
			System.err.println("j=" + j + " i=" + i);
			Thread.sleep(50);
			printNow(arr, System.out);
			Thread.sleep(50);
			while (i >= 0 && arr[i] > key) {
				System.out.print("index:" + i + "=>" + (i + 1) + " value swap:" + arr[i] + "=>" + arr[i + 1] + "\n");
				// swap
				int t = arr[i + 1];
				arr[i + 1] = arr[i];
				arr[i] = t;

				i = i - 1;
				if (i >= 0) { //下标从0开始，第一次有-1的情况
					key = arr[i + 1];
				}
				printNow(arr, System.err);
		
			}
		}
		System.out.println("end......");
	}

	static int input[] = {  36, 26, 23, 10, 4,1};//排序元素

	public static void main(String[] args) throws InterruptedException {
		Sort insertSort = new SortInsert();
		insertSort.sort(input);
		printNow(input, System.out);
	}

}

打印结果:

黑色的是每趟排序前的打印，红色的是每趟排序后的结果。由于刚好元素初始化顺序为从大到小，所以时间复杂度是最差的情况，即j的值等于swap的次数。

算法(一)插入排序

插入排序算法

推荐阅读