又到排序了. 上次看算法第四版只是迅速过了一遍, 书一遍看不明白就看两遍, 有些东西必须得硬来才行.
递归的习题就没那么好写了, 有的想了一会就写出来了, 比如那个用三个栈排序的, 但是有些比如全排列和递归的动态规划就不那么明显会写了.
估计还是每一次要维持一个背包的这种对象, 在递归之间如何传递, 比较麻烦. 看来代码还得仔细想想, 看来自学开发还算可以, 不会像要面试找工作那样压力那么大.
- 泛型简单回顾 - Comparable<T>接口
- 选择排序
- 重构选择排序到更灵活的版本
泛型简单回顾 - Comparable<T>接口
在排序之前, 比较元素的大小是一个重要的议题. Java提供了一个接口Comparable接口, 只要继承了该接口, 都可以用来比较大小. 该接口其实我们已经很熟悉了, 不过这里要说的是泛型.
比如我们可以利用排序接口, 实现一个简单的泛型方法:
public static <T extends Comparable<T>> T findMin(T[] array) {
T min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i].compareTo(min) < 0) {
min = array[i];
}
}
return min;
}
看上去好像很简单, 但实际上有一个问题, 现在我们有一种车CarA, 还有继承CarA的CarB, 二者都有重量可以进行比较, 代码如下:
public class CarA implements Comparable<CarA> {
private int weight;
private String name;
public CarA(int weight, String name) {
this.weight = weight;
this.name = name;
}
@Override
public int compareTo(CarA carA) {
return this.weight - carA.weight;
}
}
public class CarB extends CarA {
public CarB(int weight, String name) {
super(weight, name + "B");
}
}
CarA实现了Comparable<CarA>接口, 所以CarB也实现了Comparable<CarA>接口, 可以进行二者的比较, 不同类型的比较也可以, 因为compareTo(CarA carA)方法中的类型是CarA, CarB也是CarA, 例如:
public static void main(String[] args) {
CarA carA1 = new CarA(10, "dfkj");
CarA carA2 = new CarA(17, "fd");
CarA carA3 = new CarA(3, "asd");
System.out.println(carA1.compareTo(carA2));
CarB carB1 = new CarB(29, "dfkbbvcj");
CarB carB2 = new CarB(21, "bjkd");
System.out.println(carB2.compareTo(carB1));
System.out.println(carA2.compareTo(carB1));
System.out.println(carB2.compareTo(carA3));
}
但是如果我们想使用我们的泛型方法, 从CarA和CarB数组中寻找最小值, 接着上边的:
CarA[] carAS = new CarA[]{carA1, carA2, carA3};
CarB[] cars = new CarB[]{carB1, carB2};
CarA mincara = findMin(carAS);
CarB mincarb = findMin(cars);
这个时候会发现编译报错:
Error:(23, 31) java: 不兼容的类型: 推论变量 T 具有不兼容的上限
等式约束条件：datastructure.ex03.CarA
下限：datastructure.ex03.CarB,java.lang.Comparable<T>
这个问题在于泛型方法的要求是<T extends Comparable<T>>, 当泛型方法接收的类型是CarA的时候, CarA是实现了Comparable<CarA>的, 所以不会有问题.
但泛型接收的类型是CarB的时候, CarB并没有实现Comparable<CarB>类型, CarB依然实现的是Comparable<CarA>类型; 而且Comparable<CarB>并不是一个Comparable<CarA>类型.
想要避免这种问题, 很显然, 如果一个类是父类并且实现了Comparable接口, 这个父类的任意层级的子类, 一定实现了一个Comparable<某个父类>接口. 因此泛型方法需要修改成:
public static <T extends Comparable<? super T>> T findMin(T[] array)
这样就可以正常工作了. 如果以后碰到泛型方面的问题, 就可以还原一下来思考结果. 此外通配符表示任意类型, 而不能使用某个具体类型. 因为一个SomeClass<A>类型, 并不是一个SomeClass<B>类型, 即使A和B有继承关系, 泛型类也不是同一个类型.
在后边实现排序算法的时候, 就会经常使用public static <T extends Comparable<? super T>> void sort(T[] array)这样的泛型方法了.
选择排序
一开始都先排数组.
选择排序的原理是, 先找到整个序列里的最小的元素, 然后将其与第一个元素进行交换, 然后对数组中剩下的部分重复这个操作.
这个操作可以非常方便的用递归或者迭代的方式写出来. 先看迭代方法, 很容易理解:
//对外暴露的公有方法
public static <T extends Comparable<? super T>> void sort(T[] array) {
int length = array.length;
if (!(length == 0 || length == 1)) {
//对数组中每一个元素, 先找到这个元素到结尾的最小值, 然后和自己替换
for (int i = 0; i < length; i++) {
//利用辅助方法找到当前元素到数组结尾的最小值对应的索引
int minindex = findMin(array, i, length - 1);
//交换当前元素与最小值元素
T temp = array[i];
array[i] = array[minindex];
array[minindex] = temp;
}
}
}
//辅助排序方法的私有方法, 根据给定的索引在一个数组中寻找索引范围内的最小值对应的索引
private static <T extends Comparable<? super T>> int findMin(T[] array, int startIndex, int lastIndex) {
int min = startIndex;
for (int i = startIndex; i <= lastIndex; i++) {
if (array[min].compareTo(array[i]) > 0) {
min = i;
}
}
return min;
}
递归的思路是, 递归方法的功能是可以找到数组中的最小值, 然后交换最小值与当前元素, 之后对剩下的部分继续应用该方法进行处理, 要额外传递一个当前变量的数值, 以表示从哪里继续处理:
//对外暴露的公有方法
public static <T extends Comparable<? super T>> void resursionSort(T[] array) {
recursionFindMinAndSwap(array, 0);
}
//实际的递归方法, 懒得使用每次复制数组的方式, 本来就是O(n^2)级别的算法, 就少占用点空间吧.
private static <T extends Comparable<? super T>> void recursionFindMinAndSwap(T[] array, int index) {
//停机条件是当前索引等于数组的最大索引
if (index != array.length - 1) {
//找到当前索引到数组末尾的最小元素对应的索引
int minIndex = findMin(array, index, array.length - 1);
//交换第一个元素和最小元素的值
T temp = array[minIndex];
array[minIndex] = array[index];
array[index] = temp;
//然后继续对剩下的数组进行操作
recursionFindMinAndSwap(array, index + 1);
}
}
这里还可以加入一些变化, 比如只想对一个数组的前n个元素进行排序, 则只需要额外传入一个n, 然后将索引设置一下即可:
public static <T extends Comparable<? super T>> void sort(T[] array, int n) {
if (n > array.length) {
throw new RuntimeException("数组的项比参数n要少!");
}
if (!(n == 0 || n == 1)) {
//对数组中每一个元素, 先找到这个元素到结尾的最小值, 然后和自己替换
for (int i = 0; i < n; i++) {
int minindex = findMin(array, i, n - 1);
//交换两个元素的位置
T temp = array[i];
array[i] = array[minindex];
array[minindex] = temp;
}
}
}
有了这个方法之后, 原来的sort只需要改成调用这个方法, n=数组长度即可:
public static <T extends Comparable<? super T>> void sort(T[] array) {
sort(array, array.length);
}
递归版本也可以再加入一个参数n, 来控制排序到第几项, 就不再一一写了,原理是一样的, 还可以将交换数组的两个索引也抽出到一个函数中.
选择排序由于是最直观的, 现在无需看教材, 自己都能够实现了.
重构选择排序和到更灵活的版本
现在的排序方法还不够通用, 必须编写一个可以指定要排序的数组, 以及开始和结束索引的方法, 以对这个索引范围(包含两端索引)的内容进行排序. 而且这个方法可以作为类中其他方法的基础方法, 比如实现了索引范围排序, 那么一个对数组进行全排序的方法就可以在内部引用这个范围排序,只需要把范围设置为0-数组最大索引即可.
先来重构选择排序的类, 由于选择排序内部需要执行两大功能, 即寻找一个范围内的最小索引, 和交换数组中两个索引的值, 所以编写一个新的方法, 同时将寻找最小索引和交换数组索引的功能抽取出来:
此外, 还有一个问题, 默认是升序排列, 是不是可以选择降序排列, 其实也很简单, 只需要将寻找最小索引改成寻找最大索引即可, 可以通过给核心方法添加一个reverse参数来控制寻找最大还是最小的索引.
于是最后写成的类中包含一个核心私有迭代排序方法, 一个核心私有递归排序方法, 三个私有静态辅助方法, 然后就暴露给外界使用的排序整个数组, 排序指定索引间的数组, 排序前n个和后n个元素的公有方法, 这些公有方法全部都调用两个核心私有方法之一.
完整的类如下:
public class Selection {
/**
* 给数组开头的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
recursionSort(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
recursionSort(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);
}
/**
* 对起始索引索引和结束索引之间(包含起始索引和结束索引)的部分进行排序, 就地排序, 不返回新数组.
* 本方法是数组排序的核心私有方法, 对外暴露的其他方法内部调用该方法.
* 数组元素需要实现Comparable接口
*
* @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) {
//判断数组长度, 如果为0或者1, 直接返回
if (array.length == 0 || array.length == 1) {
return;
}
//判断两个索引参数是否符合要求
if (startIndex < 0 || startIndex > array.length - 1 || endIndex < 0 || endIndex > array.length - 1 || startIndex > endIndex) {
throw new IllegalArgumentException("索引超出范围");
}
//主排序算法, 对于数组中每一个元素, 获取其到endIndex之间的最小值, 然后交换二者的位置, 注意, 其实只需要遍历到倒数第二个元素即可, 因为不管交换不交换, 结果都正确.
for (int i = startIndex; i < endIndex; i++) {
//根据是否升序或者降序, 查找当前索引到结束索引之间的最小/大值对应的索引
int swapIndex;
if (reverse) {
swapIndex = findMaxIndex(array, i, endIndex);
} else {
swapIndex = findMinIndex(array, i, endIndex);
}
//交换当前索引和最大/最小值索引的内容
swap(array, i, swapIndex);
}
}
/**
* 递归版本的核心排序私有方法, 方法原理是, 寻找当前数组的最小/大值, 与第一个进行交换. 然后对数组的第二个元素开始到结束的部分进行同样的空操作, 直到剩余部分长度为1结束.
* 这个递归方法的名称应该叫交换第一个元素与最大/最小值更加合适
* @param array 要排序的数组
* @param startIndex 开始的索引
* @param endIndex 结束的索引
* @param reverse 是否反向(降序)排列, true为降序, false为升序
* @param <T> 泛型参数,必须实现Comparable接口
*/
private static <T extends Comparable<? super T>> void recursionSort(T[] array, int startIndex, int endIndex, boolean reverse) {
//基础的参数判断与非递归版本一致
if (array.length == 0 || array.length == 1) {
return;
}
//判断两个索引参数是否符合要求
if (startIndex < 0 || startIndex > array.length - 1 || endIndex < 0 || endIndex > array.length - 1 || startIndex > endIndex) {
throw new IllegalArgumentException("索引超出范围");
}
//停机条件是startIndex=endIndex
if (startIndex != endIndex) {
//根据是否降序取最小/最大值对应的索引
int swapIndex;
if (reverse) {
swapIndex = findMaxIndex(array, startIndex, endIndex);
} else {
swapIndex = findMinIndex(array, startIndex, endIndex);
}
//交换第一个索引与最大/最小值对应的索引的内容
swap(array, startIndex, swapIndex);
//对从start+1开始到endIndex的部分继续排序
recursionSort(array, startIndex + 1, endIndex, reverse);
}
}
/**
* 寻找一个数组在起始索引和结束索引之间的最小值对应的索引, 数组元素需要实现Comparable接口. 私有方法, 为支持排序方法.
*
* @param array 数组对象
* @param startIndex 起始索引
* @param lastIndex 结束索引
* @param <T> 泛型参数,必须实现Comparable接口
* @return 在起始索引和结束索引之间的最小值对应的索引
*/
private static <T extends Comparable<? super T>> int findMinIndex(T[] array, int startIndex, int lastIndex) {
int min = startIndex;
for (int i = startIndex; i <= lastIndex; i++) {
if (array[min].compareTo(array[i]) > 0) {
min = i;
}
}
return min;
}
/**
* 寻找一个数组在起始索引和结束索引之间的最大值对应的索引, 数组元素需要实现Comparable接口. 私有方法, 为支持排序方法.
*
* @param array 数组对象
* @param startIndex 起始索引
* @param lastIndex 结束索引
* @param <T> 泛型参数,必须实现Comparable接口
* @return 在起始索引和结束索引之间的最大值对应的索引
*/
private static <T extends Comparable<? super T>> int findMaxIndex(T[] array, int startIndex, int lastIndex) {
int max = startIndex;
for (int i = startIndex; i <= lastIndex; i++) {
if (array[max].compareTo(array[i]) < 0) {
max = i;
}
}
return max;
}
/**
* 交换数组中两个元素的方法, 不返回任何值, 就地交换. 私有方法, 为支持排序方法
*
* @param array 数组
* @param index1 要交换的两个元素的其中一个索引
* @param index2 要交换的两个元素的另外一个索引
* @param <T> 泛型参数,必须实现Comparable接口
*/
private static <T> void swap(T[] array, int index1, int index2) {
T temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
算法真的不能着急, 必须一点一点慢慢吃透, 不仅练会算法本身, 还得一并提高工程实践能力才行. 这样写出来的类灵活性高多了.
选择排序的复杂度非常明显, 最差的情况下, 第一个元素要遍历n次才能找到最小值/最大值, 然后第二个元素是n-1次, 一直到第n个元素, 很显然是平方级别的复杂度, 这个已经很熟悉了.
