常见排序算法
概览比较
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n log n) | O(n^2) | O(n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n^2) | O(n log n) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
冒泡排序
1 | public void bubbleSort(int[] array) { |
选择排序
1 | // 选择排序算法 |
插入排序
1 | // 插入排序算法 |
希尔排序
1 | // 希尔排序算法 |
归并排序（递归）
1 | // 使用归并排序算法对数组进行排序 |
快速排序（递归）
1 | // 快速排序算法 |
堆排序
1 | // 堆排序算法 |
基数排序
1 | public static void radixSort(int[] arr) { |
Java已集成好的排序
数组
Arrays.sort()重载了四类方法：sort(T[] a)：对指定T型数组按数字升序排序。sort(T[] a,int formIndex, int toIndex)：对指定T型数组的指定范围按数字升序排序。sort(T[] a, Comparator<? supre T> c): 根据指定比较器产生的顺序对T型数组进行排序。sort(T[] a, int formIndex, int toIndex, Comparator<? supre T> c): 根据指定比较器产生的顺序对T型数组的指定范围进行排序。
1 | int[] a={2,5,4,3,1,8}; |
列表
1 | Arrays.sort(); // 使用快速排序（Quicksort）或归并排序（Mergesort）算法对数组进行排序。 |
集合
TreeSet和TreeMap默认按照红黑树（数据结构）算法排序（通过红黑树来存储元素，并根据元素的自然顺序或者自定义的比较器来进行排序）
自定义比较器
涉及到 对象数组的比较的情况，两种方法处理：
- 继承comparable接口，并实现
int compareTo(T o);方法 - 定义一个单独的对象比较器，继承自Comparator接口，实现
int compare(T o1, T o2);方法
Comparable
Comparable是
java.lang包中的一个排序接口。只要一个类实现了这个接口就可以意味着这个类支持排序。
实现了这个类的接口的列表或者数组可以可以使用Collections.sort或Arrays.sort进行排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class Person implements Comparable<Person>{
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
/**
* 重新的compareTo方法。
* @param person 用于指定的比较的对象。
* @returns 相等则返回0，大于则返回正数（1），小于则返回负数（-1）。
*/
public int compareTo(Person person) {
return this.age - person.age;
}
/* 测试 */
public static void main(String[] args) {
// 创建一个Person数组。
Person[] persons = new Person[]{new Person("tom", 20), new Person("jack", 12)};
// 排序之前
for (Person p : persons) {
System.out.print("name:" + p.name + ", age:" + p.age + " ");
}
Arrays.sort(persons); // 测试中借助Arrays按照定义的Comparable接口进行排序
// 排序之后
for (Person p : persons) {
System.out.print("name:" + p.name + ", age:" + p.age + " ");
}
}
}
/**
* 最终排序结果解释：
* 根据compareTo结果：
* 返回 0，即 a-b < 0。说明a小于b，所以两者的顺序是:a, b。
* 返回 1，即 a-b > 0。说明a大于b，所以两者的顺序是:b, a。
* 返回-1，即 a-b=0。说明a等于b，所以两个数的顺序是:a, b
*
* 结论：a-b升序；b-a降序；
*/注意：遇到过整型溢出，如：[[-2147483646, -2147483645], [2147483646, 2147483647]]，按照0下标升序，发现结果是降序的，代码如下：
1
2
3int[][] points = {{-2147483646, -2147483645}, {2147483646, 2147483647}};
Arrays.sort(points, (a, b) -> a[0] - b[0]); // 目的是升序排序，预期结果：{{-2147483646, -2147483645}, {2147483646, 2147483647}}
System.out.println(points); // 结果：{{2147483646, 2147483647}, {-2147483646, -2147483645}}解决方案：使用
Integer.compare(a,b)，Integer.compare会返回正确的比较结果，而不会因为溢出导致错误排序。1
2int[][] points = {{-2147483646, -2147483645}, {2147483646, 2147483647}};
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
Comparator
Comparator是java.util中的一个比较的接口。
如果我们想要控制某个类的次序，而这个类并没有继承Comparable接口，那么我们就可以使用Comparator接口。
比较的规则：大致和上面的规则相同，不过也有不同的地方，详情请看下面的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36// 用法一：不重新创建一个类
public void test(){
Comparator<Integer> comparator = new Comparator<>() {
public int compare(Integer o1, Integer o2) {
return 0;
}
public boolean equals(Object obj) {
return false;
}
};
Integer[] a = {1, 2, 2, 9};
Arrays.sort(a, comparator);
}
// 用法二：重新创建类，实现Comparator类
class PersonComparator implements Comparator<Person> {
public int compare(Person p1, Person p2) {
return p1.age - p2.age;
}
}
public class Test {
public static void main(String[] args) {
// 创建一个Person数组。
Person[] persons = new Person[]{new Person("tom", 20), new Person("jack", 12)};
// 排序之后
Arrays.sort(persons, new PersonComparator());
}
}
// 用法三：使用封装好的工具类Collections
// 降序排序
Arrays.sort(integerArray, Collections.reverseOrder());
// Collections.reverseOrder()方法返回一个Comparator，该比较器会对元素进行自然顺序的逆序比较。注意：比较器的泛型类型 和 被比较列表 的数据类型保持一致
常见报错：
reason: no instance(s) of type variable(s) T exist so that int[] conforms to T[]解释：Java 的
Comparator和Arrays.sort是为对象数组设计的。如Integer[]。因为基本类型数组int[]和对象类型数组Integer[]是不兼容的，所以你需要将int[]转换为Integer[]。
总结
- 两者不在一个包。Comparable在java.lang中，而Comparator在java.util包中。
- 实现Comparable的类通常是一个我们要经常使用的类。比如：java中的String类等等。需要修改源代码。而Comparator可以在不同修改源代码的情况下，来完成比较。从了保护了代码。
- 两个方法各有优劣。如果你的类需要经常使用比较的操作，那么可以考虑让这个了实现Comparable接口。如果你偶尔使用比较的操作，那么可以考虑使用Comparator。