要看一个排序, 就得把思想记住, 思想记住了, 即使具体代码忘记了, 也可以很快写出来新的应用到工程中, 但要是思路忘记了, 那就等于全部忘光了.
- 插入排序的思路和核心方法
- 编写公有方法
- 递归版本的方法
- 插入排序的优缺点
- 递归实现寻找第二最小
插入排序的思路
插入排序的思路是, 对于数组的每一个元素, 将其与其左边的元素不断进行比较. 假如是升序排列的话, 如果当前元素比左边的大, 说明位于正确的位置上, 比左边的小, 则说明其要移动到左边元素的左边. 移动完之后, 再与左边的元素进行比较.
从整体上来看, 就是数组中的每一个元素, 都不断与其左边的元素进行交换, 一直到处于正确的位置上.
编写迭代方法的时候, 一开始就编写像选择排序一样灵活的排序方法, 即可以使用开始和结束索引的方法. 这里的整体思路就是对于数组的每一个元素, 都从这个元素反向迭代到数组的头部, 然后比较每个位置上的元素与当前元素, 如果当前元素更小, 就将那个位置往后移动一下.
一直到当前元素大于那个元素, 则说明当前元素应该紧跟在那个位置的元素之后, 因此就将当前元素插入到刚刚移走的元素的位置上. 编写这个方法, 要特别注意数组的索引, 不要超过界限. 此外还可以将插入动作单独提取到一个方法中.
核心方法如下:
/**
* 插入排序的核心方法, 迭代版本
*
* @param array 要排序的数组
* @param startIndex 要排序部分开始的索引
* @param endIndex 要排序部分结束的索引
* @param reverse 是否降序排列, true为降序, false为升序
* @param <T> 泛型参数,必须实现Comparable接口
*/
private static <T extends Comparable<? super T>> void sort(T[] array, int startIndex, int endIndex, boolean reverse) {
if (array.length == 0 || array.length == 1) {
return;
}
if (startIndex < 0 || endIndex < 0 || startIndex > array.length - 1 || endIndex > array.length - 1 || startIndex > endIndex) {
throw new IllegalArgumentException("索引超出范围. startIndex=" + startIndex + " endIndex=" + endIndex);
}
//由于插入排序的特点, 只需要从数组的第二个元素开始遍历, 一直到endIndex, 即范围是 startIndex+1 to endIndex
//从要排序部分的第二个元素一直到要排序部分的最后一个元素遍历
for (int i = startIndex + 1; i <= endIndex; i++) {
//将当前元素插入到startIndex 到 i 之间的正确位置
insertIntoArray(array, startIndex, i, reverse);
}
}
还需要实现辅助这个核心方法的insertIntoArray方法:
/**
* 将currentIndex位置上的元素, 合理插入到startIndex - currentIndex范围内的数组中的方法
* 本方法是插入算法中将某一个位置的元素插入到其正确位置的核心方法, 辅助核心排序方法完成工作
* @param array 要排序的数组
* @param startIndex 要排序的部分的开始索引位置
* @param currentIndex 当前索引位置
* @param reverse 是否降序, true为降序, false为升序
* @param <T> 泛型参数,必须实现Comparable接口
*/
private static <T extends Comparable<? super T>> void insertIntoArray(T[] array, int startIndex, int currentIndex, boolean reverse) {
T element = array[currentIndex];
int index = currentIndex;
//这里注意, 当前元素不需要一直移动到startIndex, 只需要移动到startIndex+1的位置即可, 在这个位置上比较左边一个元素的位置即可. 如果移动到数组尽头还去比较左侧元素, 会导致越界.
while (index > startIndex) {
//如果当前元素小于其左边元素, 说明其至少应该在左边元素的左边, 所以将左边元素右移一格, 然后继续比较当前元素与再左边元素
if (!reverse) {
if (element.compareTo(array[index - 1]) < 0) {
array[index] = array[index - 1];
index--;
} else {
break;
}
} else {
if (element.compareTo(array[index - 1]) > 0) {
array[index] = array[index - 1];
index--;
} else {
break;
}
}
}
//循环结束的时候, index就指向应该插入的位置, 如果element是最小, 此时的索引就是0, 否则就是某个应该插入的位置. 其之前的位置都已经被右移了一格
//将element插入到当前位置
array[index] = element;
}
辅助方法特别需要注意界限的处理, 不要越界.
编写其他方法
这个和之前的排序的套路几乎一致了, 就是各种方法来调用私有核心排序方法, 从选择排序中直接把方法复制过来, 如果私有方法的名称还是sort, 都不用改动就可以继续沿用:
public class InsertionSort {
/**
* 给数组开头的count个元素进行升序排列
*
* @param array 数组
* @param count 从开始要排序的元素的数量
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void sortFromStart(T[] array, int count) {
//判断参数是否合理, 由于核心函数会判断参数是否有问题, 所以这里只需要判断count即可, 等于0或者1直接返回
//如果count等于其他值, 会由核心函数进行判断
if (count == 0 || count == 1) {
return;
}
//调用核心函数, 开始索引为0, 结束索引为count-1即可
sort(array, 0, count - 1, false);
}
/**
* 给数组开头的count个元素进行降序排列
*
* @param array 数组
* @param count 从开始要排序的元素的数量
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void sortFromStartDesc(T[] array, int count) {
//判断参数是否合理, 由于核心函数会判断参数是否有问题, 所以这里只需要判断count即可, 等于0或者1直接返回
//如果count等于其他值, 会由核心函数进行判断
if (count == 0 || count == 1) {
return;
}
//调用核心函数, 开始索引为0, 结束索引为count-1即可
sort(array, 0, count - 1, true);
}
/**
* 给从数组末尾向前数起的count个元素进行升序排序
*
* @param array 要排序的数组
* @param count 末尾的count个元素
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void sortFromEnd(T[] array, int count) {
//判断参数是否合理, 由于核心函数会判断参数是否有问题, 所以这里只需要判断count即可, 等于0或者1直接返回
//如果count等于其他值, 会由核心函数进行判断
if (count == 0 || count == 1) {
return;
}
//调用核心函数, 开始索引为array.length-1-count, 结束索引为 array.length-1
sort(array, array.length - count, array.length - 1, false);
}
/**
* 给从数组末尾向前数起的count个元素进行降序排序
*
* @param array 要排序的数组
* @param count 末尾的count个元素
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void sortFromEndDesc(T[] array, int count) {
//判断参数是否合理, 由于核心函数会判断参数是否有问题, 所以这里只需要判断count即可, 等于0或者1直接返回
//如果count等于其他值, 会由核心函数进行判断
if (count == 0 || count == 1) {
return;
}
//调用核心函数, 开始索引为array.length-1-count, 结束索引为 array.length-1
sort(array, array.length - count, array.length - 1, true);
}
/**
* 对数组全部元素进行升序排列, 内部直接调用核心私有方法或者另外一个排序前N个的都可以
*
* @param array 要排序的数组
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void sort(T[] array) {
sort(array, 0, array.length - 1, false);
}
/**
* 对数组全部元素进行降序排列, 内部直接调用核心私有方法或者另外一个排序前N个的都可以
*
* @param array 要排序的数组
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void sortDesc(T[] array) {
sort(array, 0, array.length - 1, true);
}
/**
* 对指定索引范围内的数组元素进行升序排序, 包含起始索引与结束索引
*
* @param array 要排序的数组
* @param startIndex 要排序的部分的起始索引
* @param endIndex 要排序的部分的结束索引
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void sortBetweenIndex(T[] array, int startIndex, int endIndex) {
//内部直接调用私有核心方法即可
sort(array, startIndex, endIndex, false);
}
/**
* 对指定索引范围内的数组元素进行降序排序, 包含起始索引与结束索引
*
* @param array 要排序的数组
* @param startIndex 要排序的部分的起始索引
* @param endIndex 要排序的部分的结束索引
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void sortBetweenIndexDesc(T[] array, int startIndex, int endIndex) {
//内部直接调用私有核心方法即可
sort(array, startIndex, endIndex, true);
}
}
递归版本的方法
在开始之前, 考虑到递归方法一样需要检查参数, 所以可以将检查参数也抽出来成为一个静态方法:
/**
* 检查参数是否出现问题的函数, 如果参数有问题, 抛出运行时错误
*
* @param array 要排序的数组
* @param startIndex 要排序部分的起始索引
* @param endIndex 要排序部分的结束索引
* @param <T> 泛型参数,必须实现Comparable接口
*/
private static <T> void checkArguments(T[] array, int startIndex, int endIndex) {
if (startIndex < 0 || endIndex < 0 || startIndex > array.length - 1 || endIndex > array.length - 1 || startIndex > endIndex) {
throw new IllegalArgumentException("索引超出范围. startIndex=" + startIndex + " endIndex=" + endIndex);
}
}
这样迭代和递归都可以使用这个方法来检查参数, 就更突出迭代和递归核心方法中的算法了.
递归版本的方法依然是思路最重要. 从之前迭代方法中查看规律, 每个元素在要进入迭代之前, 其左侧的所有元素已经是排序好的.
假如我们的递归方法是能够完成排序工作的函数, 则只需要对数组的前n-1个元素进行排序,再把最后一个元素插入到已经排好序的数组中就可以了. 停机条件是数组长度为1, 无需排序, 直接返回.
所以我们递归方法的逻辑是:
如果数组长度不是1:
排数组之前的n-1个元素(对0 - n-1 的数组调用递归方法)
将第n个元素插入到之前n-1个元素的数组中的正确位置.
根据这个思路, 加上之前编写的将元素插入数组的方法, 就可以编写出递归方法如下:
/**
* 递归插入排序的方法, 是核心私有方法
* 递归思想是从迭代观察发现, 每一个元素的左边已经是被排序好的, 排序的方法就是将那个元素插入左边已经排序好的序列.
* 本方法既然可以进行排序, 只要数组长度不为1, 就先将数组最后一个元素的左边部分全部排序好, 再将最后一个元素插入到已经排序好的部分.
*
* @param array 要排序的数组
* @param startIndex 要排序部分的开始索引
* @param endIndex 要排序部分结束的索引
* @param reverse 是否降序排列, true为降序, false为升序
* @param <T> 泛型参数,必须实现Comparable接口
*/
public static <T extends Comparable<? super T>> void recursionSort(T[] array, int startIndex, int endIndex, boolean reverse) {
//判断过程和原来一样, 其实也可以抽取出来
if (array.length == 0 || array.length == 1) {
return;
}
checkArguments(array, startIndex, endIndex);
//如果数组长度不为1
if (startIndex != endIndex) {
//对数组n-1的部分进行排序
recursionSort(array, startIndex, endIndex - 1, reverse);
//将当前最后一个索引 endIndex 对应的元素插入到 start - endIndex 之间
insertIntoArray(array, startIndex, endIndex, reverse);
}
}
夜深人静的时候插入排序也仔细想好了, 这次无需重构, 一开始就想好了可以传入开始和结束索引, 以及升序和降序的核心方法的编写, 然后再其中还把插入部分也单独提取成一个方法, 在递归方法中就可以使用了.
这个插入方法其实也有递归思路, 由于其实就是将元素不断交换到正确的位置, 因此递归思路是:
如果当前元素小于左边元素并且当前元素不是开头元素:
交换左边元素和当前元素
对当前元素是最左侧的数组(即n-1长度的数组)继续调用递归方法
如果递归函数实现的效果是根据大小交换一个数组的最右边和次右边的功能, 那么只需先交换, 再对数组n-1的部分继续调用就可以了:
/**
* 将insertIntoArray方法改写而成的递归方法
* 递归方法的功能是交换一个数组的最右侧两个元素. 停机条件是根据reverse的比较大小.
* 例如,如果reverse是 false 表示 升序排列, 则停机条件首先是两个索引相等, 无需插入, 之后停机条件是当前元素大于等于其左侧元素
* 如果当前元素小于其左侧元素, 交换两个元素的位置, 当前元素的索引就减少了1, 于是继续对当前元素为末尾的数组调用递归方法, 这样递归方法就始终跟踪一个元素.
*
* @param array 要插入的数组
* @param startIndex 插入部分的起始索引
* @param currentIndex 要将哪个索引的元素插入到起始到这个索引的部分, 参数就是那个索引
* @param <T> 泛型参数,必须实现Comparable接口
*/
private static <T extends Comparable<? super T>> void recursionSwap(T[] array, int startIndex, int currentIndex, boolean reverse) {
if (currentIndex != startIndex) {
if (!reverse) {
if (array[currentIndex].compareTo(array[currentIndex - 1]) < 0) {
T temp = array[currentIndex];
array[currentIndex] = array[currentIndex - 1];
array[currentIndex - 1] = temp;
recursionSwap(array, startIndex, currentIndex - 1, false);
}
} else {
if (array[currentIndex].compareTo(array[currentIndex - 1]) > 0) {
T temp = array[currentIndex];
array[currentIndex] = array[currentIndex - 1];
array[currentIndex - 1] = temp;
recursionSwap(array, startIndex, currentIndex - 1, true);
}
}
}
}
有了这个插入动作的递归方法, 就可以把核心递归排序方法中的:
insertIntoArray(array, startIndex, endIndex, reverse);
替换成:
recursionSwap(array, startIndex, endIndex, reverse);
排序工作一样没问题.
插入排序的优缺点
没有看教材, 自己也写出来了插入排序, 关键是对思路理解的更深了. 插入依然需要遍历比较, 所以很显然, 也是平方级的复杂度, 因此也够慢的.
但是插入排序也有好处:
- 对于已经有序的内容, 每次新增一个数据, 让结果依然有序的复杂度是O(n), 这就让插入排序经常用于一些已经排序好, 减少和新增幅度不大的内容.
- 插入排序的思想可以用于链表排序, 选择排序就非常难以操作链表类型的数据结构.
之前排列的都是数组, 之后就要用插入排序来操作一下链表的排序.
递归实现寻找第二最小
这两天写了递归排序的方法, 对于递归的思路有所开拓, 以前的思维有些局限, 以为递归中仅仅主要依靠递归方法自己的逻辑, 实际上像插入排序的递归, 也可以使用insertIntoArray这种其他方法来辅助.
于是睡前洗澡的时候就在想之前留下的递归题目, 然后终于想出来了递归寻找第二最小的算法如下:
停机条件: 数组长度为2, 返回较大的值. 数组长度为1, 返回唯一的值.
如果数组长度大于3, 寻找数组后边n-1个元素的第二最小和最小, 然后和数组的第一个元素进行比较, 返回结果即可.
这个递归方法需要使用一个辅助寻找最小值的方法:
public static <T extends Comparable<? super T>> T findMin(T[] array, int startIndex, int endIndex) {
if (startIndex < 0 || endIndex < 0 || startIndex > endIndex || startIndex > array.length - 1 || endIndex > array.length - 1) {
throw new IllegalArgumentException("索引不正确: startIndex" + startIndex + " endIndex=" + endIndex);
}
T min = array[startIndex];
for (int i = startIndex; i <= endIndex; i++) {
if (min.compareTo(array[i]) > 0) {
min = array[i];
}
}
return min;
}
之后的递归就是上边思路的直接转化:
public static <T extends Comparable<? super T>> T findSecondMin(T[] array, int startIndex, int endIndex) {
//检查参数
if (startIndex < 0 || endIndex < 0 || startIndex > endIndex || startIndex > array.length - 1 || endIndex > array.length - 1) {
throw new IllegalArgumentException("索引不正确: startIndex" + startIndex + " endIndex=" + endIndex);
}
//停机条件1 数组只有一个元素, 返回那个元素
if (startIndex == endIndex) {
return array[startIndex];
}
//停机条件2 数组只有一个元素, 返回较大的元素
if (endIndex - startIndex == 1) {
if (array[startIndex].compareTo(array[endIndex]) > 0) {
return array[startIndex];
} else {
return array[endIndex];
}
}
//获取数组第一个元素
T element1 = array[startIndex];
//数组剩下部分的第二小元素
T element2 = findSecondMin(array, startIndex + 1, endIndex);
//数组剩下部分的最小元素
T element3 = findMin(array, startIndex + 1, endIndex);
//进行比较
//如果第一个元素小于后边数组的最小值, 那第二小就是最小值
if (element1.compareTo(element3) < 0) {
return element3;
//如果第一个元素大于等于后边数组的最小值, 但是小于后边数组的第二小值, 那第一个元素就是整个数组的第二小值
} else if (element1.compareTo(element2) < 0) {
return element1;
//如果第一个元素大于等于后边数组的第二小值, 那后边数组的第二小值就是整个数组的第二小值
} else {
return element2;
}
}
经过测试, 发现确实可以找到, 对递归的认识更深了, 不然以前总想着在递归里还套用循环, 实际上完全不必. 只要想明白自己递归方法的作用, 然后寻找一个思路, 再转换成代码即可.
