目录
前言
一、什么是选择排序
二、实现选择排序
三、使用泛型扩展
四、使用自定义类型测试
前言
今天天气不错,这么好的天气不干点啥实在是有点可惜了,于是乎,拿出键盘撸一把!
来,今天来学习一下排序算法中的选择排序法。
一、什么是选择排序
简单来说就是:
先把最小的拿出来
剩下的,再把最小的拿出来
剩下的,再把最小的拿出来
。。。。。。依次类推,每次都是选择还没处理的元素中最小的元素。
比如下图所示,一个乱序的数组经过排序后得到了一个有序的数组:
实现思想:双层循环,外层i从下标0开始遍历,内层j从下标为i的位置开始遍历,遍历得到最小的元素之后, 与下标为i的元素进行交换,之后i加1,重新开始上述步骤。
二、实现选择排序
下面我们通过代码来实现上面的这个乱序的整型数组的排序:
public class SelectionSort {public static void main(String[] args) {int[] arr = {6, 4, 2, 3, 1, 5};SelectionSort.sort(arr);for (int ele : arr) {System.out.print(ele + " ");}System.out.println();}private SelectionSort() {}public static void sort(int[] arr) {for (int i = 0; i < arr.length; i++) {// 选择arr[i...n)中最小值的索引int minIndex = i;for (int j = i; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr, i, minIndex);}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
运行结果如下:
三、使用泛型扩展
下面将排序方法扩展成为泛型方法,并且为泛型添加Comparable约束,在测试方法main()中,我们不能使用基本数据类型int了,而是需要使用装箱类Integer,代码如下:
public class SelectionSort {public static void main(String[] args) {Integer[] arr = {6, 4, 2, 3, 1, 5};SelectionSort.sort(arr);for (int ele : arr) {System.out.print(ele + " ");}System.out.println();}private SelectionSort() {}public static <T extends Comparable<T>> void sort(T[] arr) {for (int i = 0; i < arr.length; i++) {// 选择arr[i...n)中最小值的索引int minIndex = i;for (int j = i; j < arr.length; j++) {if (arr[j].compareTo(arr[minIndex]) < 0) {minIndex = j;}}swap(arr, i, minIndex);}}private static <T> void swap(T[] arr, int i, int j) {T temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}
运行完了,同样好使的哈:
四、使用自定义类型测试
首先,跟上一篇中《最简单的算法:线性查找法》一样,我们来整个Student类,该类实现Comparable接口,重写compareTo(),如下所示:
public class Student implements Comparable<Student> {private String name;private int score;public Student(String name, int score) {this.name = name;this.score = score;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (this.getClass() != obj.getClass())return false;Student stu = (Student) obj;return this.name.equals(stu.name);}@Overridepublic int compareTo(Student stu) {return this.score - stu.score;}@Overridepublic String toString() {return String.format("Student(name:%s,score:%d)", name, score);}
}
然后,在main()中进行测试:
得到结果如下:
OK,以上主要介绍了如何实现一个通用数据类型的选择排序算法,如何一步一步的优化,今天的内容就这么多了,下期再会!