0. 简介
- 插入排序法相对于前 2 种排序法来说，思路相对简单。对于长度为 n 的数组 ‘int[] array = new int[n];’（其中 n > 1），先将数组的前两个元素即 array[0] 和 array[1] 进行排序，这两个元素组成了一个 ‘有序数组片段’，其长度为 2，接下来将数组 array 中的元素从 array[2] 开始，直到数组的最后一个元素 array[n - 1] 为止，把每个元素依次插入前面的 ‘有序数组片段’ 中，从而完成排序工作。这里有两点需要注意，一：对于移动数组的操作（这里有两种方式移动数组，一种是数组挨个的依次往后挪位置，一种是使用直接复制数组操作），二：对 ‘有序数组片段’ 的查询，以确定插入位置（对于有序数组，可使用二分法查找，以优化性能）。暂时没有其它好说的了。
1. 插入排序程序示例
/** 插入排序法 */
class InsertSort{
/**
* 排序方式：递增 或 递减
*/
public enum SortType{
INCREMENT_SORT("递增排序"), DECREMENT_SORT("递减排序");
private final String desc;
private SortType(String desc) {
this.desc = desc;
}
public String desc() {
return this.desc;
}
}
/**
* XXX 可优化
* 插入排序法（递增排序方式）
* @param datas 等待排序的数组
* @param type 指定排序方式，取值为枚举类型，查看 {@code InsertSort.SortType}
*/
public static void doSorting(int[] datas, SortType type) {
// 仅仅支持递增排序（添加递减操作逻辑会使得代码更长，而不易阅读）
type = SortType.INCREMENT_SORT;
if (datas != null && datas.length > 1) {
final int arrayLength = datas.length;
// 先排序数组的前两个元素，产生初始的长度为 2 的 ’有序数组片段‘
if (datas[0] > datas[1]) {
int temp = datas[0];
datas[0] = datas[1];
datas[1] = temp;
}
int c = 0;
// 从第三个位子（即 datas[2] ）开始执行插入排序
for(int i = 2;i < arrayLength;i++) {
c = datas[i];
if (c <= datas[0]) {
// 在’有序数组片段‘头部插入
moveToRight(datas, 0, i -1);
datas[0] = c;
}else if(c >= datas[i - 1]) {
// 在’有序数组片段‘尾部插入（当前元素 datas[i] 紧邻 ’有序数组片段‘ 的尾部）
continue;
}else {
// XXX 该部分可以继续优化
// 从’有序数组片段‘的中间元素开始比较/插入（二分）
int middleIndex = Math.round(i / 2.0f - 1.0f);
int middleValue = datas[middleIndex];
if (c == middleValue) {
// 运气真好
moveToRight(datas, middleIndex, i -1);
datas[middleIndex] = c;
}else if(c < middleValue) {
// continue to left
middleIndex--;
for(;middleIndex >= 0;middleIndex--) {
// 找到第一个 c 大于或等于的元素
if (c >= datas[middleIndex]) {
moveToRight(datas, middleIndex + 1, i - 1);
datas[middleIndex + 1] = c;
break;
}
}
}else {
// c > middleValue
// continue to right
middleIndex++;
for(;middleIndex < i;middleIndex++) {
// 找到第一个 c 小于或等于的元素
if (c <= datas[middleIndex]) {
moveToRight(datas, middleIndex, i - 1);
datas[middleIndex] = c;
break;
}
}
}
}
}
}
}
/**
* 将指定的数组片段向后（右边）移动一个位置。该方法用于代理 moveToRight_verbose() 和 moveToRight_fast() 这两个方法，便于在这两个方法间切换实现。
* @param array 目标数组
* @param startIndex 数组片段的起始位置（包括该位置的元素）
* @param endIndex 数组片段的终止位置（包括该位置的元素）
*/
private static void moveToRight(int[] array, int startIndex, int endIndex) {
// v1 verbose
// moveToRight_verbose(array, startIndex, endIndex);
// v2 fast and simple
moveToRight_fast(array, startIndex, endIndex);
}
/**
* 将指定的数组片段向后（右边）移动一个位置，该方法移动大量数据时，效率较低。
* @param array 目标数组
* @param startIndex 数组片段的起始位置（包括该位置的元素）
* @param endIndex 数组片段的终止位置（包括该位置的元素）
*/
private static void moveToRight_verbose(int[] array, int startIndex, int endIndex) {
// if (array != null && array.length > endIndex + 1 && endIndex >= startIndex) {
// 验证参数（可不验证）
// }
for(int i = endIndex + 1;i > startIndex;i--) {
array[i] = array[i - 1];
}
}
/**
* 将指定的数组片段向后（右边）移动一个位置，使用复制数组操作，当移动大量数组元素时将显著提高效率。
* @param array 目标数组
* @param startIndex 数组片段的起始位置（包括该位置的元素）
* @param endIndex 数组片段的终止位置（包括该位置的元素）
*/
private static void moveToRight_fast(int[] array, int startIndex, int endIndex) {
// if (array != null && array.length > endIndex + 1 && endIndex >= startIndex) {
// 验证参数（可不验证）
// }
System.arraycopy(array, startIndex, array, startIndex + 1, endIndex - startIndex + 1);
}
/**
* 验证数组 sortedArray 中，以下标 startIndex 开始，长度为 length 的数组片段的排序是否符合 type 指定的顺序，
* <br> 对于全等数组可以说它是递增也可以说是递减。
* @param sortedArray 目标数组
* @param startIndex 起始元素的下标（包括）
* @param length 数组片段的长度
* @param type 排序顺序
* @return true：指定数组片段符合 type 指定的顺序，否则返回 false
*/
public static boolean valicateSortedArray(int[] sortedArray, int startIndex, int length, SortType type) {
int arraySize = 0;
boolean valicated = true;
int count = 0;
if (sortedArray != null && (arraySize = sortedArray.length) > startIndex
&& (startIndex + length -1) < arraySize) {
count += 1;
for(int i = startIndex + 1;i < arraySize;i++) {
count++;
// 每个数与它的前任比较
if (type == SortType.INCREMENT_SORT && sortedArray[i] < sortedArray[i - 1]) {
// 验证递增数组
valicated = false;
break;
}else if (type == SortType.DECREMENT_SORT && sortedArray[i] > sortedArray[i - 1]) {
// 验证递减数组
valicated = false;
break;
}
}
}
System.out.println("已验证 - 元素个数：" + count);
return valicated;
}
}
简单测试下：
public class Structure_3_4 {
private static final ThreadLocal<Long> startTime = new ThreadLocal<Long>();
public static void main(String[] args) {
int NUMBERS_NUM = 100000; // 生成随机数数量
int BOUND = 1000000; // 随机数边界
Random random = new Random();
int[] datas = new int[NUMBERS_NUM];
System.out.println("number of elements is [" + NUMBERS_NUM + "]");
for (int i = 0; i < NUMBERS_NUM; i++) {
datas[i] = random.nextInt(BOUND);
}
// 记录排序操作起始时间
startTime.set(System.currentTimeMillis());
// do sorting
InsertSort.doSorting(datas, InsertSort.SortType.INCREMENT_SORT);
long costTimeByMS = System.currentTimeMillis() - startTime.get();
// 打印统计信息
double costTime = costTimeByMS / 1000.0;
System.out.println("cost time:" + (costTime == 0 ? costTimeByMS + "ms" : costTime + "s"));
System.out.println("done\n-----------------------------------");
System.out.println("验证：" + InsertSort.valicateSortedArray(datas, 0, datas.length
, InsertSort.SortType.INCREMENT_SORT));
// 输出已排序数组最后 10 个元素
for (int i = 1;i <= 10 && (NUMBERS_NUM - i) >= 0;i++) {
System.out.println("第 " + (NUMBERS_NUM - i + 1) + " 个数: " + datas[NUMBERS_NUM - i]);
}
}
}
输出结果如下（排序 10万个数耗时 1.23s）：
number of elements is [100000]
cost time:1.23s
done
-----------------------------------
已验证 - 元素个数：100000
验证：true
第 100000 个数: 999977
第 99999 个数: 999972
第 99998 个数: 999954
第 99997 个数: 999946
第 99996 个数: 999942
第 99995 个数: 999920
第 99994 个数: 999905
第 99993 个数: 999900
第 99992 个数: 999884
第 99991 个数: 999855