排序基础之选择排序法

目录

前言

一、什么是选择排序

二、实现选择排序

三、使用泛型扩展

四、使用自定义类型测试

---

前言

今天天气不错，这么好的天气不干点啥实在是有点可惜了，于是乎，拿出键盘撸一把！

来，今天来学习一下排序算法中的选择排序法。

一、什么是选择排序

简单来说就是：

先把最小的拿出来

剩下的，再把最小的拿出来

剩下的，再把最小的拿出来

。。。。。。依次类推，每次都是选择还没处理的元素中最小的元素。

比如下图所示，一个乱序的数组经过排序后得到了一个有序的数组：

实现思想：双层循环，外层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，以上主要介绍了如何实现一个通用数据类型的选择排序算法，如何一步一步的优化，今天的内容就这么多了，下期再会！