算法分析（四） 插入排序

插入排序

插入排序是从数组第 n 位开始，与前面的每位进行逐一比较，比前一位大则交换一次位置，直到不比前面的某一位小停下继续对 n+1 做重复操作到数组遍历结束。

实现代码

public class InsertSelectionSort {
	/*
	 * 1.第一位不用动，从第二位开始和前面依次进行比较，小的话交换位置不小就停下
	 */

	// 我们的算法类不允许产生任何实例
	private InsertSelectionSort() {
	}

	public static void sort(Comparable[] arr) {
		int n = arr.length;
		for (int i = 1; i < n; i++) {// 对第i个进行插入排序
			for (int j = i - 1; j >= 0; j--) {// 循环与i前面的进行比较,比前一个小就交换一次，直到不比前面小停止
				if (arr[i].compareTo(arr[j]) < 0) {// arr[i]小 交换
					swap(arr, j+1, j);//修正感谢[wizardforcel](https://hacpai.com/member/wizardforcel)
				} else {
					break;
				}
			}
		}
	}

	private static void swap(Object[] arr, int i, int j) {
		Object temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

本次不写这么详细了，个人感觉插入排序和选择排序有些相似，这个排序算是从后向前进行的。没有详细的思考比较，最近比较忙，有时间补上泛型实现和思考总结。