左神算法-基础03

比较器的使用

1）比较器的实质就是重载比较运算符

2）比较器可以很好的应用在特殊标准的排序上

3）比较器可以很好的应用在根据特殊标准排序的结构上

public static class MyComp implements Comparator<Integer> {
	//实现Comparator 接口，重写compare（）方法，实现自己的比较逻辑
   	//返回负数时，第一个参数排前面
    //返回正数时，第二个参数排前面
    //返回0 时，谁在前面无所谓
   @Override
   public int compare(Integer o1, Integer o2) {
      return o2 - o1;
   }

}

桶排序思想下的排序

1）计数排序

2）基数排序

分析：

​ 1) 桶排序思想下的排序都是不基于比较的排序

​ 2) 时间复杂度为O(N)，额外空间负载度O(M)

​ 3) 应用范围有限，需要样本的数据状况满足桶的划分

// only for 0~200 value	计数排序
public static void countSort(int[] arr) {
   if (arr == null || arr.length < 2) {
      return;
   }
   int max = Integer.MIN_VALUE;
   for (int i = 0; i < arr.length; i++) {
       //找到最大值
      max = Math.max(max, arr[i]);
   }
   int[] bucket = new int[max + 1];	//申请桶子
   for (int i = 0; i < arr.length; i++) {
      bucket[arr[i]]++;	//在桶子里放数
   }
   int i = 0;
   for (int j = 0; j < bucket.length; j++) {
      while (bucket[j]-- > 0) {	//按顺序将每个桶子里的数字，还原到数组中
         arr[i++] = j;
      }
   }
}

// 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;	//返回最大的进制位数
}

public static void radixSort(int[] arr, int begin, int end, int digit) {
   final int radix = 10;	//默认是十进制，十个基数：0，1，2，3，4，5，6，7，8，9
   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++) {
         j = getDigit(arr[i], d);	//得到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];	//<=j 的数有count[j]个，将arr[i]放到count[j]-1的位置上去
         count[j]--;	//<=j 的数减一
      }
      for (i = begin, j = 0; i <= end; i++, j++) {
         arr[i] = bucket[j];	//从bucket 放回原数组
      }
   }
}

public static int getDigit(int x, int d) {	//计算d 位上的基数，也就是取余操作
   return ((x / ((int) Math.pow(10, d - 1))) % 10);
}

排序算法的稳定性及其汇总

同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定性的；否则就没有。

不具备稳定性的排序：

​ 选择排序、快速排序、堆排序

具备稳定性的排序：

​ 冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

目前没有找到时间复杂度O(N*logN)，额外空间复杂度O(1)，又稳定的排序。

排序算法常见的坑

1，归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，有兴趣可以搜“归并排序 内部缓存法”

2，“原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成O(N^2)

3，快速排序可以做到稳定性问题，但是非常难，不需要掌握， 可以搜 “01 stable sort”

4，所有的改进都不重要，因为目前没有找到时间复杂度O(N*logN)，额外空间复杂度O(1)，又稳定的排序。

5，有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官。

工程上对排序的改进

1）充分利用O(N*logN)和O(N^2)排序各自的优势

2）稳定性的考虑

• 样本量小于六十的时候用插入排序
• 基础类型用快速排序，非基础类型用归并排序