数据结构与算法——选择排序法

news/2024/5/20 7:22:32/文章来源:https://blog.csdn.net/qq_45902692/article/details/133998498

个人简介

👀个人主页：前端杂货铺
🙋‍♂️学习方向：主攻前端方向，正逐渐往全干发展
📃个人状态：研发工程师，现效力于中国工业软件事业
🚀人生格言：积跬步至千里，积小流成江海
🥇推荐学习：🍍前端面试宝典 🍉Vue2 🍋Vue3 🍓Vue2/3项目实战 🥝Node.js🍒Three.js🍖数据结构与算法体系教程

🌕个人推广：每篇文章最下方都有加入方式，旨在交流学习&资源分享，快加入进来吧

数据结构与算法

内容	参考链接
数据结构与算法——线性查找法	线性查找法

文章目录

数据结构与算法
- 一、选择排序法
- 二、使用带约束的泛型
- 三、使用 Comparable 接口
- 四、选择排序法的复杂度
- 五、本篇小结

一、选择排序法

排序算法：让数据有序，排序算法中蕴含着重要的算法设计思想

如果我们想把数组 [1, 4, 2, 3, 6, 5] 变成 [1, 2, 3, 4, 5, 6] 的顺序，就可以使用选择排序法实现

基本思路：arr[i…n) 未排序，arr[0…i) 已排序，arr[1…n) 中的最小值要放到 arr[i] 的位置

代码实现：sort() 方法里面是双重 for 循环，用于对当前最小值索引的更改，之后再通过 swap() 方法，实现索引位置对应值的交换

时间复杂度：O（n^2）

SelectionSort.java

public class SelectionSort {// 构造方法private SelectionSort() {}public static void sort(int[] arr) {// arr[0...1) 是有序的; arr[i...n) 是无序的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 t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {int[] arr = {1, 4, 2, 3, 6, 5};SelectionSort.sort(arr);for (int e: arr) {System.out.print(e + " "); // 输出：1 2 3 4 5 6}}
}

在这里插入图片描述

二、使用带约束的泛型

同样的，如果我们想针对各种类型进行比较就需要使用泛型来实现

注意这里需要使用 带约束的泛型，即泛型 E 继承 Comparable 接口，实现可比较。其 API => compareTo() 返回整型，小于零表示前者小于后者，等于零表示前者等于后者，大于零表示前者大于后者…

SelectionSort.java

public class SelectionSort {private SelectionSort() {}// 泛型约束 => 可比较的public static <E extends Comparable<E>> void sort(E[] arr) {// arr[0...1) 是有序的; arr[i...n) 是无序的for (int i = 0; i < arr.length; i++) {// 选择 arr[i...n) 中的最小值的索引int minIndex = i;for (int j = i; j < arr.length; j++) {// compareTo 返回整型，小于零表示前者小于后者if (arr[j].compareTo(arr[minIndex]) < 0) {minIndex = j;}}swap(arr, i, minIndex);}}// 交换值private static <E> void swap(E[] arr, int i, int j) {E t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {Integer[] arr = {1, 4, 2, 3, 6, 5};SelectionSort.sort(arr);for (int e: arr) {System.out.print(e + " "); // 输出：1 2 3 4 5 6}}
}

在这里插入图片描述

三、使用 Comparable 接口

接下来，我们尝试实现让 Student类使用 Comparable 接口

代码实现：

我们定义 Student类，让其使用 Comparable 接口，在类内部重写 compareTo() 方法（该方法必须要重写，不然编译报错），按成绩的升序进行排序

我们再重写 toString() 方法，格式化字符串

Student.java

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 int compareTo(Student another) {return this.score - another.score;}@Overridepublic String toString() {// 格式化字符串return String.format("Student(name: %s, score: %d)", name, score);}
}

我们在 main 函数中定义 student 数组，通过排序算法进行排序，最后再循环输出

SelectionSort.java

public class SelectionSort {private SelectionSort() {}// 泛型约束 => 可比较的public static <E extends Comparable<E>> void sort(E[] arr) {// arr[0...1) 是有序的; arr[i...n) 是无序的for (int i = 0; i < arr.length; i++) {// 选择 arr[i...n) 中的最小值的索引int minIndex = i;for (int j = i; j < arr.length; j++) {// compareTo 返回整型，小于零表示前者小于后者if (arr[j].compareTo(arr[minIndex]) < 0) {minIndex = j;}}swap(arr, i, minIndex);}}// 交换值private static <E> void swap(E[] arr, int i, int j) {E t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {Student[] students = {new Student("Jon", 95),new Student("Pu", 100),new Student("Alice", 60)};SelectionSort.sort(students);for (Student student: students) {System.out.print(student + " ");}}
}

在这里插入图片描述

四、选择排序法的复杂度

接下来，我们测试算法的性能，并且使用 1万个 数据和 10万个 数据来查看时间复杂度是否为 O（n^2）。

我们新创建一个 ArrayGenerator.java 文件，用于随机生成长度为 n 的数组

ArrayGenerator.java

import java.util.Random;public class ArrayGenerator {private ArrayGenerator() {}// 生成一个长度为 n 的随机数组，每个数字的范围是 [0, bound)public static Integer[] generateRandomArray(int n, int bound) {Integer[] arr = new Integer[n];Random rnd = new Random();for (int i = 0; i < n; i++) {// nextInt() 用于获取一个 int 类型的数arr[i] = rnd.nextInt(bound);}return arr;}
}

我们再创建一个 SortingHelper.java 文件，用于判断是否为排序，以及用来做排序测试

SortingHelper.java

public class SortingHelper {private SortingHelper() {}public static <E extends Comparable<E>> boolean isSorted(E[] arr) {for (int i = 1; i < arr.length; i++) {if (arr[i-1].compareTo(arr[i]) > 0) {return false;}}return true;}public static <E extends Comparable<E>> void sortTest(String sortName, E[] arr) {long startTime = System.nanoTime();if (sortName.equals("SelectionSort")) {SelectionSort.sort(arr);}long endTime = System.nanoTime();double time = (endTime - startTime);if (!SortingHelper.isSorted(arr)) {throw new RuntimeException(sortName + "failed");}System.out.println(String.format("%s , n = %d : %f s", sortName, arr.length, time / 1000000000));}
}

在 SelectionSort.java 文件中我们编写基本的选择排序逻辑，并实现 1万个和 10万个数据的排序

public class SelectionSort {private SelectionSort() {}// 泛型约束 => 可比较的public static <E extends Comparable<E>> void sort(E[] arr) {// arr[0...1) 是有序的; arr[i...n) 是无序的for (int i = 0; i < arr.length; i++) {// 选择 arr[i...n) 中的最小值的索引int minIndex = i;for (int j = i; j < arr.length; j++) {// compareTo 返回整型，小于零表示前者小于后者if (arr[j].compareTo(arr[minIndex]) < 0) {minIndex = j;}}swap(arr, i, minIndex);}}// 交换值private static <E> void swap(E[] arr, int i, int j) {E t = arr[i];arr[i] = arr[j];arr[j] = t;}public static void main(String[] args) {int[] dataSize = {10000, 100000};for (int n : dataSize) {Integer[] arr = ArrayGenerator.generateRandomArray(n, n);SortingHelper.sortTest("SelectionSort", arr);}}
}