选择排序简介
直观理解：选出最小值依次排列
选择排序（Selection Sort）是一种简单直观的排序算法，其核心思想是：从未排序的部分中找到最小的元素，将它放到已排序部分的末尾。
类比生活场景
想象你在一堆扑克牌中寻找最小的牌，并依次把它们从小到大排好：
- 从所有牌中找到最小的那张牌，放到最左边。
- 从剩下的牌中继续找最小的牌，放到已排好牌的右侧。
- 重复以上步骤，直到所有牌都排好。
算法流程
假设要对数组 [8, 3, 5, 2] 进行升序排序，选择排序的过程如下：
-
第1轮：
- 找出整个数组中最小的值
2，与第一个位置的值8交换，数组变为[2, 3, 5, 8]。
- 找出整个数组中最小的值
-
第2轮：
- 从剩余未排序部分
[3, 5, 8]中找到最小值3，已在正确位置，无需交换。
- 从剩余未排序部分
-
第3轮：
- 从剩余未排序部分
[5, 8]中找到最小值5，已在正确位置，无需交换。
- 从剩余未排序部分
-
第4轮：
- 剩下的部分只有一个元素
8，不需要操作。
- 剩下的部分只有一个元素
最终结果为 [2, 3, 5, 8]。
选择排序代码实现
public class SelectionSortUtil {
/**
* 对整型数组进行选择排序
*
* @param arr 待排序数组
*/
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// 假设当前位置的元素最小
int minIndex = i;
// 查找剩余部分中更小的元素
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换当前元素与找到的最小元素
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
// 测试
public static void main(String[] args) {
int[] arr = {8, 3, 5, 2};
selectionSort(arr);
// 输出结果
for (int num : arr) {
System.out.print(num + " ");
}
// 输出：2 3 5 8
}
}
时间复杂度和空间复杂度
时间复杂度
选择排序的核心是两层循环：
- 外层循环：
- 遍历数组中的每个位置，次数为
n-1。
- 遍历数组中的每个位置，次数为
- 内层循环：
- 遍历剩余未排序部分以找到最小值，次数依次为
n-1, n-2, ..., 1。
- 遍历剩余未排序部分以找到最小值，次数依次为
总比较次数为：
[
(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}
]
因此，选择排序的时间复杂度为：
[
O(n^2)
]
空间复杂度
选择排序是原地排序算法，不需要额外的存储空间，除了少量临时变量用于交换值。因此：
[
O(1)
]
选择排序的特点
-
优点：
- 简单易懂，代码实现非常直观。
- 在数据规模较小时表现良好。
-
缺点：
- 时间复杂度较高，特别是对大数据量排序时效率不佳。
选择排序在 Android 开发中的应用场景
尽管选择排序的效率较低，但由于其实现简单、内存占用小，仍然适用于某些特殊场景：
-
小规模数据排序：
- 在数据量较小的情况下（如少于 10 个元素），选择排序简单直接，代码维护成本低。
-
嵌入式环境或低内存设备：
- 在 Android 的 IoT 或嵌入式场景中，如果设备内存有限，选择排序的低内存开销成为一个优势。
-
特定排序任务：
- 在特定业务需求中需要手动实现排序逻辑（如自定义控件排序时），选择排序提供了灵活性。
示例：选择排序在 RecyclerView 数据中的应用
假设我们有一个 RecyclerView，用于显示一组用户数据（姓名和年龄），现在需要对数据按照年龄从小到大排序。
数据模型：
class User {
String name;
int age;
public User(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return name + " (" + age + ")";
}
}
排序工具：
import java.util.List;
public class SelectionSortUtil {
public static void selectionSortUsers(List<User> users) {
int n = users.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (users.get(j).age < users.get(minIndex).age) {
minIndex = j;
}
}
// 交换
User temp = users.get(i);
users.set(i, users.get(minIndex));
users.set(minIndex, temp);
}
}
}
使用示例：
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<User> users = new ArrayList<>();
users.add(new User("Alice", 25));
users.add(new User("Bob", 20));
users.add(new User("Charlie", 23));
SelectionSortUtil.selectionSortUsers(users);
// 输出结果
for (User user : users) {
System.out.println(user);
}
// 输出：
// Bob (20)
// Charlie (23)
// Alice (25)
}
}
总结
选择排序是一种简单、直观的排序算法，尽管其时间复杂度较高，但在小规模数据或内存受限场景中非常实用。在 Android 开发中，它常用于临时性或小规模数据排序需求，例如：
- 静态列表排序。
- 自定义排序逻辑。
- 内存优化场景（如 IoT 设备上的数据处理）。
当前文章价值3.63元，扫一扫支付后添加微信提供帮助！（如不能解决您的问题，可以申请退款）
评论已关闭！