左神算法基础班第3章第二周学习——详解桶排序以及排序内容大总结

3.1 比较器

返回负数的时候，第一个参数排在前面
返回正数的时候，第二个参数排在前面
返回0的时候，谁在前面无所谓（默认排序）

定义 Student 类，以年龄 age 逆序输出。写了两种不同的比较器格式，习惯用第一种。

import java.util.*;

public class comparatorDemo {
 
 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 void main (String[] args) {
  Student std1 = new Student("摸鱼人生", 1, 16);
  Student std2 = new Student("多快乐", 2, 22);
  Student std3 = new Student("大海的对面", 3, 18);
  Student std4 = new Student("没有自由", 4, 25);
  
  Student[] stdArr = new Student[] {std1, std2, std3, std4};
  
  for (int i = 0; i < stdArr.length; i++) {
   System.out.println(stdArr[i].name + " " + stdArr[i].id + " " + stdArr[i].age);
  }
  System.out.println("============");
  
  Arrays.sort(stdArr, new Comparator<Student>() {   // 返回负数的时候，第一个参数排在前面
   public int compare (Student std1, Student std2) { // 返回正数的时候，第二个参数排在前面
    return std2.age - std1.age;      // 返回0的时候，谁在前面无所谓（默认排序）
   }   
  });
 
  for (int i = 0; i < stdArr.length; i++) {
   System.out.println(stdArr[i].name + " " + stdArr[i].id + " " + stdArr[i].age);
  }
 } 
}

import java.util.*;

public class comparatorDemo {
 
 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 void main (String[] args) {
  Student std1 = new Student("摸鱼人生", 1, 16);
  Student std2 = new Student("多快乐", 2, 22);
  Student std3 = new Student("大海的对面", 3, 18);
  Student std4 = new Student("没有自由", 4, 25);
  
  Student[] stdArr = new Student[] {std1, std2, std3, std4};
  
  for (int i = 0; i < stdArr.length; i++) {
   System.out.println(stdArr[i].name + " " + stdArr[i].id + " " + stdArr[i].age);
  }
  System.out.println("============");
  
  Arrays.sort(stdArr, new studentComp());
 
  for (int i = 0; i < stdArr.length; i++) {
   System.out.println(stdArr[i].name + " " + stdArr[i].id + " " + stdArr[i].age);
  }
 }
 
 public static class studentComp implements Comparator<Student> {
  public int compare (Student std1, Student std2) {
   return std1.age - std2.age;
  }
 } 
}

第三种方式是以大根堆的结构弹出。

import java.util.*;

public class comparatorDemo {
 
 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 void main (String[] args) {
  Student std1 = new Student("摸鱼人生", 1, 16);
  Student std2 = new Student("多快乐", 2, 22);
  Student std3 = new Student("大海的对面", 3, 18);
  Student std4 = new Student("没有自由", 4, 25);
  
  Student[] stdArr = new Student[] {std1, std2, std3, std4};
  
  for (int i = 0; i < stdArr.length; i++) {
   System.out.println(stdArr[i].name + " " + stdArr[i].id + " " + stdArr[i].age);
  }
  System.out.println("============");
  
  // 以大根堆的结构弹出
  PriorityQueue<Student> heap = new PriorityQueue<> (new studentComp());
  heap.add(std1);
  heap.add(std2);
  heap.add(std3);
  heap.add(std4);
  
  while (!heap.isEmpty()) {
   Student curStd = heap.poll();
   System.out.println(curStd.name + " " + curStd.id + " " + curStd.age);
  }
 }
 
 public static class studentComp implements Comparator<Student> {
  public int compare (Student std1, Student std2) {
   return std2.age - std1.age;
  }
 }
}

3.2 桶排序思想下的具体排序：计数排序、基数排序

3.2.1 桶排序

计数排序假设了输入数据都属于一个小区间内的整数，而桶排序则假设输入数据是均匀分布的，即落入每个桶中的元素数量理论也是差不多的，不会出现很多数落入同一个桶内的情况。

3.2.2 计数排序

计数排序详解这篇详解更简洁一点

计数排序不是基于元素比较，而是利用数组下标来确定元素的正确位置。首先遍历待排序数组arr，得到数组的最大值与最小值；新建统计数组 countArr，其长度为：数列最大值和最小值的差 + 1，再统计arr中的元素个数；对 countArr 变形，使后面的元素等于前面的元素之和；最后倒序遍历 arr，从 countArr 找到正确位置，输出到结果数组 sortedArr。

时间复杂度： $O(N+M)$ ，N 是待排序数组 arr 的长度，最大最小整数的差值是M。
空间复杂度： $O(M)$

public static int[] countSort (int[] arr) {
 // 1. 得到数列的最大值与最小值，并算出差值d
 int max = 0;
 int min = 0;
 for (int i = 0; i < arr.length; i++) {
  if (max < arr[i]) {
   max = arr[i];
  }
  if (min > arr[i]) {
   min = arr[i];
  }
 }
 int d = max - min + 1;
 // 2. 创建统计数组countArr并计算统计对应元素个数
 int[] countArr = new int[d];
 for (int i = 0; i < arr.length; i++) {
  countArr[arr[i] - min]++;
 }
 // 3. 统计数组变形，后面的元素等于前面的元素之和
 int sum = 0;
 for (int i = 0; i < countArr.length; i++) {
  sum += countArr[i];
  countArr[i] = sum;
 }
 // 4. 倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组sortedArr
 int[] sortedArr = new int[arr.length];
 for (int i = arr.length - 1; i >= 0; i--) {
  int nowLocation = arr[i] - min;
  sortedArr[countArr[nowLocation] - 1] = arr[i];
  countArr[nowLocation]--;
 } 
 return sortedArr;
}

计数排序很简单，但是当数组最大最小值差距过大时 or 当数列元素不是整数时，并不适用于计数排序 。

3.2.3 基数排序

基数排序的要求：样本最好是十进制的正数。

以最大值是三位数的数组为例，准备10个桶，分别对应 0~9，首先根据个位数决定进哪个桶，对个位数进行排序；再以十位数决定进哪个桶，对个位数进行排序；最后以十位数决定进哪个桶，对百位数进行排序。

代码我是没有读懂，思想蛮简单的。

import java.util.*;

public class RadixSort {

 public static void main(String[] args) {
  int[] arr = new int[] {10, 2, 0, 3, 0, 33, 21};
  radixSort(arr);
  System.out.println(Arrays.toString(arr));
 }
 
 public static void radixSort (int[] arr) {
  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;
 }
 
 // digit 数组元素的最大位数
 public static void radixSort (int[] arr, int left, int right, int digit) {
  final int radix = 10;  // 基数
  int i =0, j = 0;
  int[] bucket = new int[right - left + 1];  // 有多少个数准备多少个辅助空间
  for (int d = 1; d <= digit; d++) {    // 有多少位就进出几次
   // 10个空间
      // count[0] 当前位(d位)是0的数字有多少个
   // count[1] 当前位(d位)是(0和1)的数字有多少个
   // count[2] 当前位(d位)是(0、1和2)的数字有多少个
   // count[i] 当前位(d位)是(0~i)的数字有多少个
   int[] count = new int[radix];
   for (i = left; i <= right; i++) {
    j = getDigit(arr[i], d);
    count[j]++;
   }
   for (i = 1; i < radix; i++) {
    count[i] = count[i] + count[i - 1];
   }
   for (i = right; i >= left; i--) {
    j = getDigit(arr[i], d);
    bucket[count[j] - 1] = arr[i];
    count[j]--;
   }
   for (i = left, j = 0; i <= right; i++, j++) {
    arr[i] = bucket[j];
   }
  }
 }
 
 // 获得当前位(d位)的数字
 public static int getDigit (int x, int d) {
  return (x / ((int) Math.pow(10, d - 1))) % 10;
 } 
}

3.3 排序算法总结

排序算法	时间复杂度	额外空间复杂度	稳定性
冒泡排序	O(N2)	O(1)	稳定
选择排序	O(N2)	O(1)	不稳定
插入排序	O(N2)	O(1)	稳定
希尔排序	O(N*logN)	O(1)	不稳定
归并排序	O(N*logN)	O(N)	稳定
堆排序	O(N*logN)	O(1)	不稳定
快速排序	O(N*logN)	O(logN)	不稳定
桶排序	O(N)	O(N)	稳定
计数排序	O(N)	O(N)	稳定
基数排序	O(N)	O(N)	稳定

不在乎数据的基础类型，不在乎稳定性，追求常数时间最优，使用快速排序。
追求最少的额外空间使用，使用堆排序。
追求稳定，使用归并排序。

左神算法基础班 第3章 第二周学习——详解桶排序以及排序内容大总结