比较器的使用
1） 比较器的实质就是重载比较运算符
2） 比较器可以很好的应用在特殊标准的排序上
3） 比较器可以很好的应用在根据特殊标准排序的结构上
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.TreeSet;
public class Code03_Comparator {
public static class Student {
public String name;
public int id;
public int age;
public Student(String name, int id, int age) {
this.name = name;
this.id = id;
this.age = age;
}
}
public static class IdAscendingComparator implements Comparator<Student> {
// 返回负数的时候，第一个参数排在前面。返回正数的时候，第二个参数排在前面。
// 返回0的时候，谁在前面无所谓。
@Override
public int compare(Student o1, Student o2) {
return o1.id - o2.id;
}
}
public static class IdDescendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o2.id - o1.id;
}
}
public static class AgeAscendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o1.age - o2.age;
}
}
public static class AgeDescendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o2.age - o1.age;
}
}
public static void printStudents(Student[] students) {
for (Student student : students) {
System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
}
}
public static void printArray(Integer[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static class MyComp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static void main(String[] args) {
Student student1 = new Student("A", 2, 23);
Student student2 = new Student("B", 3, 21);
Student student3 = new Student("C", 1, 22);
Student[] students = new Student[] { student1, student2, student3 };
Arrays.sort(students, new IdAscendingComparator());
printStudents(students);
Arrays.sort(students, new IdDescendingComparator());
printStudents(students);
Arrays.sort(students, new AgeAscendingComparator());
printStudents(students);
Arrays.sort(students, new AgeDescendingComparator());
printStudents(students);
PriorityQueue<Student> maxHeapBasedAge = new PriorityQueue<>(new AgeDescendingComparator());
maxHeapBasedAge.add(student1);
maxHeapBasedAge.add(student2);
maxHeapBasedAge.add(student3);
while (!maxHeapBasedAge.isEmpty()) {
Student student = maxHeapBasedAge.poll();
System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
}
PriorityQueue<Student> minHeapBasedId = new PriorityQueue<>(new IdAscendingComparator());
minHeapBasedId.add(student1);
minHeapBasedId.add(student2);
minHeapBasedId.add(student3);
while (!minHeapBasedId.isEmpty()) {
Student student = minHeapBasedId.poll();
System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
}
TreeSet<Student> treeAgeDescending = new TreeSet<>(new AgeDescendingComparator());
treeAgeDescending.add(student1);
treeAgeDescending.add(student2);
treeAgeDescending.add(student3);
Student studentFirst = treeAgeDescending.first();
System.out.println("Name : " + studentFirst.name + ", Id : " + studentFirst.id + ", Age : " + studentFirst.age);
Student studentLast = treeAgeDescending.last();
System.out.println("Name : " + studentLast.name + ", Id : " + studentLast.id + ", Age : " + studentLast.age);
}
}
桶排序思想下的排序
1） 计数排序
2） 基数排序
分析：
1） 桶排序思想下的排序都是不基于比较的排序
2） 时间复杂度为O(N)，额外空间负载度O(M)
3） 应用范围有限，需要样本的数据状况满足桶的划分
// only for no-negative value
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
//arr[begin,end]排序
public static void radixSort(int[] arr, int begin, int end, int digit) {
final int radix = 10;
int i = 0, j = 0;
int[] bucket = new int[end - begin + 1]; //有多少个数准备多少辅助空间
for (int d = 1; d <= digit; d++) { //有多少位就进出多少次
int[] count = new int[radix];
for (i = begin; i <= end; i++) { //10个空间 count[0] 当前位(d位)是0的数字有多少个
j = getDigit(arr[i], d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
for (i = end; i >= begin; i--) {
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
for (i = begin, j = 0; i <= end; i++, j++) {
arr[i] = bucket[j];
}
}
}
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
排序算法的稳定性及其汇总
同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定 性的；否则就没有。
不具备稳定性的排序：
选择排序、快速排序、堆排序
具备稳定性的排序：
冒泡排序、插入排序、归并排序、一切桶排序思想下的排序
目前没有找到时间复杂度0(N*logN),额外空间复杂度0(1),又稳定的排序。
常见的坑
1, 归并排序的额外空间复杂度可以变成0(1),但是非常难，不需要掌握，有兴趣可以搜“归并排序内部缓存法”
2, “原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成0(N^2)
3, 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”
4, 所有的改进都不重要，因为目前没有找到时间复杂度0(N*logN),额外空间复 杂度0(1),又稳定的排序。
5, 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对 次序不变，碰到这个问题，可以怼面试官。
工程上对排序的改进
- 充分利用O(N* logN)和0 (N^2)排序各自的优势
大样本 快排
小样本 插入
- 稳定性的考虑
基础类型 快排
自己规定类型 归并