数组的算法
目录
概述
- 简单排序：冒泡排序、选择排序、插入排序
- 高级排序：快速排序、归并排序、希尔排序
- 相关算法知识：划分、递归、二分查找
冒泡排序
原理：
- 从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置。
- 指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置。
- 依此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面。
- 依照上面的过程进行第二轮排序，将第二大的排在倒数第二的位置。
- 重复上述过程，没排完一轮，比较次数就减少一次。
编码思路：
需要两层循环，第一层循环表示排序的轮数，第二层循环表示比较的次数
代码
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped; // 用于标记某趟排序过程中是否发生了交换
for (int i = 0; i < n-1; i++) {
swapped = false;
for (int j = 0; j < n-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;
swapped = true;
}
}
// 如果在某趟排序中没有发生交换，说明数组已经有序，可以提前结束排序
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array");
printArray(arr);
}
// 用于打印数组的辅助函数
static void printArray(int arr[]) {
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
}
选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
算法原理
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
代码
public class SelectionSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// 总共要经过 N-1 轮比较
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 每轮需要比较的次数 N-i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 记录目前能找到的最小值元素的下标
min = j;
}
}
// 将找到的最小值和i位置所在的值进行交换
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
}
排序算法库
Arrays 类
java.util.Arrays 类提供了静态方法来对数组进行排序。它可以对基本数据类型数组以及对象数组进行排序。
- 对基本数据类型数组排序：使用 Arrays.sort() 方法。这个方法使用双轴快速排序算法（Dual-Pivot Quicksort），对于基本数据类型效率很高。
int[] arr = {5, 3, 2, 8, 1};
Arrays.sort(arr);
- 对对象数组排序：使用同样的
Arrays.sort()方法，但它要求对象实现Comparable接口或者需要一个Comparator。对于对象数组，默认使用归并排序（Merge Sort）或者改进的归并排序（Timsort），这取决于元素的数量和元素的类型。
String[] strings = {"banana", "apple", "pear"};
Arrays.sort(strings);
Collections 类
java.util.Collections 类提供了静态方法来对集合进行排序。这些方法可以用于List接口的实现类，如ArrayList、LinkedList等。
对List集合排序：使用 Collections.sort() 方法。这个方法也要求集合元素实现 Comparable 接口或者需要一个 Comparator。内部同样使用归并排序或Timsort算法。
List<String> list = new ArrayList<>(Arrays.asList("banana", "apple", "pear"));
Collections.sort(list);
Comparable 和 Comparator 接口
为了让对象能够被排序，Java 提供了两个接口：Comparable 和 Comparator。
Comparable：如果一个类实现了这个接口，它就可以根据自然顺序进行排序。这个接口的 compareTo(Object o) 方法用于对比当前对象与指定对象的顺序。
public class Person implements Comparable<Person> {
private String name;
public int compareTo(Person another) {
return this.name.compareTo(another.name);
}
}
Comparator：这个接口用于定义不同于自然顺序的排序规则。可以将其实例作为参数传递给排序方法（如Arrays.sort()或Collections.sort()），以控制排序逻辑。
Comparator<Person> comparator = new Comparator<Person>() {
public int compare(Person p1, Person p2) {
return p1.getName().compareTo(p2.getName());
}
};
Stream API
Java 8 引入的Stream API也支持排序操作，尤其是在处理集合时。
- 使用Stream对集合进行排序：可以通过
stream.sorted()方法进行排序，它允许使用Comparable或Comparator。
List<Person> people = // ...
List<Person> sortedPeople = people.stream()
.sorted(Comparator.comparing(Person::getName))
.collect(Collectors.toList());