基本思路
正如生活中整理扑克的方法：一张一张的来，将每一张扑克插入到其他已经有序的扑克中的适当位置。
Q：计算机中如何实现？
A：为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。（这里我们用交换代替移动）
Q：与选择排序的相同点？
A：当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。当索引到达数组的右端时，数组排序就完成了。
Q：与选择排序的不同点？
A：插入排序所需的时间取决于输入中元素的初始顺序。速度：元素已经有序（或接近有序）的数组 > 随机顺序的数组
运行轨迹
插入排序运行轨迹
代码实现
根据排序算法类的模板实现插入排序（提醒：点蓝字查看详情）
import java.util.Random;
/**
* 插入排序
*
* @author TinyDolphin
* 2017/11/1 14:20.
*/
public class Insertion {
/**
* 排序实现
*
* @param arr 待排序数组
*/
public static void sort(Comparable[] arr) {
//排序代码
int length = arr.length;
for (int indexI = 1; indexI < length; indexI++) {
for (int indexJ = indexI; indexJ > 0 && less(arr[indexJ], arr[indexJ - 1]); indexJ--) {
exch(arr, indexJ, indexJ - 1);
}
}
}
/**
* 比较两个元素的大小
*
* @param comparableA 待比较元素A
* @param comparableB 待比较元素B
* @return 若 A < B,返回 true,否则返回 false
*/
private static boolean less(Comparable comparableA, Comparable comparableB) {
return comparableA.compareTo(comparableB) < 0;
}
/**
* 将两个元素交换位置
*
* @param arr 待交换元素所在的数组
* @param indexI 第一个元素索引
* @param indexJ 第二个元素索引
*/
private static void exch(Comparable[] arr, int indexI, int indexJ) {
Comparable temp = arr[indexI];
arr[indexI] = arr[indexJ];
arr[indexJ] = temp;
}
/**
* 打印数组的内容
*
* @param arr 待打印的数组
*/
private static void show(Comparable[] arr) {
for (int index = 0; index < arr.length; index++) {
System.out.print(arr[index] + " ");
}
System.out.println();
}
/**
* 判断数组是否有序
*
* @param arr 待判断数组
* @return 若数组有序，返回 true，否则返回 false
*/
public static boolean isSort(Comparable[] arr) {
for (int index = 1; index < arr.length; index++) {
if (less(arr[index], arr[index - 1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Integer[] arr = new Integer[100000];
for (int index = 0; index < 100000; index++) {
arr[index] = new Random().nextInt(100000) + 1;
}
long start = System.currentTimeMillis();
sort(arr); //83001ms
long end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start));
assert isSort(arr);
}
}
性能分析
对于随机排列的长度为 N 且主键不重复的数组
平均情况下：~N²/4 次比较、~N²/4 次交换、O(N^2)
最坏的情况：~N²/2 次比较、~N²/2 次交换、O(N^2)
最好的情况：N-1 次比较、0次交换（线性级别）（当倒置的数量很少时，比其他的排序算法都要快）（对于部分有序的很有效）、O(N)
Q：何为倒置？
A：数组中的两个顺序颠倒的元素，如：3 2 5 1 4 中，有 5 对倒置：3-2、3-1、2-1、5-1、5-4。
Q：何为部分有序？
A： 数组中倒置的数量小于数组大小的某个倍数。
插入排序需要的交换次数 = 数组中倒置的数量
倒置数量 <= 需要的比较次数 <= 倒置的数量 + 数组的大小 - 1
优化方案
NO.1
原有方案：在内循环中，总是交换两个元素。
优化方案：进行了预处理操作，并在内循环中，总是将较大的元素向右移动。（这样访问数组的次数就能减半）
优化之后的运行轨迹
优化之后的运行轨迹
优化之后的插入排序
优化之后的代码
public static void sortPlus(Comparable[] arr) {
int length = arr.length;
int exchanges = 0; //交换次数
// 预处理：若 arr[index] < arr[index - 1]，则交换两数
for (int index = length - 1; index > 0; index--) {
if (less(arr[index], arr[index - 1])) {
exch(arr, index, index - 1);
exchanges++;
}
}
// 若交换次数为0（即数组有序），则无需进行下一步排序。
if (exchanges == 0) return;
// 若有交换次数，表明目前的数组无序。
for (int indexI = 2; indexI < length; indexI++) {
Comparable temp = arr[indexI]; //记录一下 arr[indexI] 的值
int indexJ = indexI; // indexI 的代替品
// 若 indexJ 的前一位元素小于 temp，则将小于 temp 的元素向右移动一位
while (less(temp, arr[indexJ - 1])) {
arr[indexJ] = arr[indexJ - 1];
indexJ--;
}
arr[indexJ] = temp; // 将记录的值放在 indexJ 的位置上
}
}
NO.2
优化方案：进行了预处理操作，并查找插入位置时使用二分查找的方式
优化之后的代码
public static void sortPlus2(Comparable[] arr) {
int length = arr.length;
int exchanges = 0; //交换次数
//若 arr[index] < arr[index - 1]，则交换两数
for (int index = length - 1; index > 0; index--) {
if (less(arr[index], arr[index - 1])) {
exch(arr, index, index - 1);
exchanges++;
}
}
//若交换次数为0（即数组有序），则无需进行下一步排序。
if (exchanges == 0) return;
//若有交换次数，表明目前的数组无序。
for (int indexI = 1; indexI < length; indexI++) {
Comparable key = arr[indexI]; //记录一下arr[indexI]的值
int left = 0;
int right = indexI - 1;
// 二分查找寻找插入点
while (left <= right) {
// ①：a >> n 相当于 a/2^n ②：此处有坑，不要图快用加法，会溢出。③、注意 >> 的优先级别低于 + ,也就是说先执行 + ，在执行 >>
int middle = left + ((right - left) >> 1);
if (less(key, arr[middle])) {
right = middle - 1;
} else {
left = middle + 1;
}
}
// 将插入点以后的所有元素，后移一位
for (int indexJ = indexI - 1; indexJ >= left; indexJ--) {
arr[indexJ + 1] = arr[indexJ];
}
// 插入元素到插入点
arr[left] = key;
}
}
测试代码
【高效复制数组的方法】，提示：点击蓝色字体查看方法详情。
public static void main(String[] args) {
int length = 100000;// 十万数量级别
Integer[] arr = new Integer[length];
Integer[] arr2 = new Integer[length];
Integer[] arr3 = new Integer[length];
for (int index = 0; index < length; index++) {
arr[index] = new Random().nextInt(length) + 1;
}
//高效复制数组的方法
System.arraycopy(arr, 0, arr2, 0, arr.length);
System.arraycopy(arr, 0, arr3, 0, arr.length);
long start = System.currentTimeMillis();
sort(arr);
long end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start) + "ms");
assert isSort(arr);
start = System.currentTimeMillis();
sortPlus(arr2);
end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start) + "ms");
assert isSort(arr2);
start = System.currentTimeMillis();
sortPlus2(arr3);
end = System.currentTimeMillis();
System.out.println("耗费时间：" + (end - start) + "ms");
assert isSort(arr3);
}
测试结果
十万数量级别测试结果
总结
NO.2 采用的优化方案，在查找插入点的时候，加快了速度，相比于 NO.1 的方案，减少了比较的次数。所以 NO.2 优化是成功的。
注意：编译器默认不适用 assert 检测（但是junit测试中适用），所以要使用时要添加参数虚拟机启动参数-ea 具体添加过程，请参照eclipse 和 IDEA 设置虚拟机启动参数
