冒泡法
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码示例（Java）：
javapublic class BubbleSort {
public static void bubbleSort(int[] arr) {
//冒泡排序
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];//临时变量
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array: ");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
算法特性：
- 时间复杂度：平均和最坏情况时间复杂度为�(�2)O(n2)，其中�n是数组的长度。最好情况时间复杂度为�(�)O(n)（当数组已经是排序好的）。
- 空间复杂度：�(1)O(1)，因为它只需要一个额外的空间来交换元素。
- 稳定性：冒泡排序是稳定的排序算法，因为它不会改变相同元素的顺序。
- 适用场景：由于其简单性，冒泡排序适合于小数据集或基本教学目的。对于较大的数据集，更高效的算法（如快速排序、归并排序等）更合适。
选择排序
选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从待排序的数据中选出最小（或最大）的元素，将其放在数列的起始位置，然后剩余的元素中再找最小（或最大）的元素，将其放在第二个位置，以此类推，直到排序完成。
算法步骤：
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
代码示例（Java）：
javapublic class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
int temp = 0;
//选择排序
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;
}
}
// 将找到的最小值与第i位的元素交换
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
算法特性：
- 时间复杂度：无论最好、最差或平均情形，时间复杂度都是�(�2)O(n2)，其中�n是数组的长度。
- 空间复杂度：�(1)O(1)，选择排序是原地排序，不需要额外存储空间。
- 稳定性：选择排序是不稳定的排序算法，因为相同元素的顺序可能会改变。
- 适用场景：由于其实现简单，选择排序适用于初学者学习和小规模数据集。对于大规模数据集，更高效的算法（如快速排序、归并排序等）更为合适。
选择排序的主要优点是它简单易实现，且对于小型数组或基本有序的数组效率相对较高。然而，由于其时间复杂度较高，它通常不适用于大型数据集。
排序算法库：sort
在Java中，sort 方法是集合框架中 java.util.Collections 类和 java.util.Arrays 类提供的一个非常强大且常用的排序方法。这两个类提供了对数组和集合进行排序的方法。
1. java.util.Arrays.sort
Arrays.sort 方法用于对数组进行排序。这个方法可以对原始数据类型的数组（如 int[]、double[] 等）和对象数组进行排序。对于对象数组，需要实现 Comparable 接口或提供 Comparator 实例来定义排序的顺序。
原始数据类型数组示例：
javaimport java.util.Arrays;
public class SortExample {
public static void main(String[] args) {
int[] numbers = {5, 2, 8, 3, 1};
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers)); // 输出排序后的数组
}
}
对象数组示例：
javaimport java.util.Arrays;
import java.util.Comparator;
class Person {
String name;
int age;
// Constructor, getters and setters
}
public class SortExample {
public static void main(String[] args) {
Person[] people = new Person[] {
new Person("Alice", 22),
new Person("Bob", 30),
new Person("Charlie", 25)
};
// 按照年龄排序
Arrays.sort(people, Comparator.comparingInt(Person::age));
for (Person person : people) {
System.out.println(person.name + " - " + person.age);
}
}
}
2. java.util.Collections.sort
Collections.sort 方法用于对 List 集合进行排序。它需要一个 List 接口的实现和 Comparator 来定义排序的顺序。
集合排序示例：
javaimport java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Product {
String name;
double price;
// Constructor, getters and setters
}
public class SortExample {
public static void main(String[] args) {
List<Product> products = new ArrayList<>();
products.add(new Product("Apple", 0.75));
products.add(new Product("Orange", 1.00));
products.add(new Product("Banana", 0.50));
// 按照价格排序
Collections.sort(products, Comparator.comparingDouble(Product::getPrice));
for (Product product : products) {
System.out.println(product.name + " - " + product.price);
}
}
}
排序算法库的特性：
- 通用性：
sort方法是泛型的，可以用于多种数据类型的排序。 - 灵活性：通过
Comparator，可以灵活地定义任何对象的排序规则。 - 效率：底层实现通常是基于快速排序、归并排序或其他高效的排序算法，具有很好的性能。
- 稳定性：Java中的
sort方法是稳定的，即相等的元素在排序后保持原有的顺序。