2.5应用

2.5.1将各种数据排序

Java的回调机制使得我们可以将任意实现Comparable接口的数据类型排序,只需重写compareTo(),在其中定义该数据的大小关系.

2.5.1.2指针排序

Java中,指针操作是隐式的,除了原始类型,我们的操作总是数据的引用(指针).指针排序增加了一层间接性.

2.5.1.4廉价的交换

使用引用的一个好处是不必移动整个元素,如果键值很长,交换的成本甚至大于比较的成本.

2.5.1.5-7 Comparable和Comparator

  • Comparable

可以看做内比较器,当一个类支持和自己比较时,只需实现此接口,而比较的规则在compareTo()中定义,而Java中很多类都已经实现了此接口并定义了比较规则

以堆优先队列中的less(int i, int j)为例

  1. private boolean less(int i, int j){
  2.     return pq[i].compareTo(pq[j]) < 0;
  3. }

由于public class MaxPQ<Key extends Comparable<Key>>且pq为Key对象数组,测试中Key也为基本数据类型,此处直接compareTo().

  • Comparator

可以看做外比较器,当一个类不支持和自己比较,或是对已有的内比较规则不满意,或想要有有针对多个不同键的比较方式可以自己构造外比较器

用法

  1. 编写一个外部类T的内部类xxxComparator并实现Comparator;
  2. 内部类中实现int compare(T a, T b)方法,根据自己确定的键种类和比较规则,返回int值;
  3. 外部类编写less(Comparator C, T v, T w)方法,调用c.compare(v, w)由返回值确定大小;
  1. public class Person {
  2.     int height;
  3.     double weight;
  5. //身高比较器
  6.     public class heightComparator implements Comparator<Person>{
  7.         public int compare(Person a, Person b){
  8.             if(a.height > b.height) return 1;
  9.             else if(a.height == b.height) return 0;
  10.             else return  -1;
  11.         }
  12.     }
  13. //体重比较器
  14.     public class weightComparator implements Comparator<Person>{
  15.         public int compare(Person a, Person b){
  16.             if(a.weight > b.weight) return 1;
  17.             else if(a.weight == b.weight) return 0;
  18.             else return  -1;
  19.         }
  20.     }
  21. }

2.5.1.8稳定性

能保留数组中重复元素相对位置的排序算法称为稳定算法

2.5.2 排序算法选择

算法 是否稳定 是否原地排序 时间复杂度 空间复杂度 备注
选择排序 否 是 N² 1
插入排序 是 是 介于N和N² 1 与输入有关
希尔排序 否 是 无法准确描述 1
快速排序 否 是 NlogN lgN 与概率有关
三向快排 否 是 介于N和NlogN lgN 与概率和输入分布有关
归并排序 是 否 NlogN N
堆排序 否 是 NlogN 1
  • 与概率有关表示排序的性能保证依赖于随机的切分元素
  • 归并排序需要辅助数组aux[]作为额外空间,故非原地排序
  • 人们根据不同的递增序列改进希尔排序最坏情况比较次数(N5/4…),但实际中递增序列生成函数差别不明显
  • 快速排序是最快的通用排序算法

2.5.2.1将原始类型数据排序

一些应用将数字排序,更合理的做法是跳过引用将原始类型数据排序,例如排序double数组和Double数组,前者可以直接交换元素,后者交换引用.对于原始类型数据的排序,后者更低效.

2.5.2.2 Java系统库的排序算法

Java系统库的主要排序方法java.util.Arrays.sort(),根据不同的参数类型,实际上代表了一系列的排序方法:

  • 每种原始数据类型有不同的排序方法
  • 一个适用于所有实现了Comparable接口的数据类型排序方法
  • 一个适用于实现了比较器Comparator的数据类型的排序方法

Java系统对原始数据类型使用(三向切分)快速排序,对引用类型使用归并排序,这些选择暗示着用速度和空间(对原始数据类型)来换取稳定性(对引用类型)

2.5.3 问题归约

归约指的是为解决某个问题而发明的算法应用于另一种问题.

2.5.3.1找出重复元素

小数组可以双层循环遍历查找,但较大数组不行,这时只能排序后记录重复元素个数

2.5.3.2逆序对数/Kendall tau距离

两个排列之间的Kt距离就是两组数列中顺序不同的数对数目,如0316254和1036425间的Kt距离就是4,因为0-1,3-1,2-4,5-4这四对相对顺序不一样.

2.5.3.4第k小元素

一般解决方式可以排序后找到第k个元素,但时间普遍在NlogN级别.

  1. public static Comparable select(Comparable[] a, int k){
  2.     StdRandom.shuffle(a);
  3.     int lo = 0, hi = a.length-1;
  4.     while(hi > lo){
  5.         int j = partition(a, lo, hi);
  6.         if(j == k) return a[k];
  7.         else if(j > k) hi = j-1;
  8.         else if(i < k) lo = j+1;
  9.     }
  10.     return a[k];
  11. }

select()采用归并排序中的partition(),使得a[j]左侧都是小于a[j]的元素,右侧都是大于a[j]的元素,当恰好j==k,问题解决,否则当j>k就继续二分左边数组,反正二分右边数组,最终会只剩下第k个元素,a[k]含有最小的(k+1)个元素.算法的增长级是线性的,假设每次都是二分,(N+N/2+N/4+…)知道找到第k小元素,和显然小于2N,比快排效率要高.

平均来说,基于切分的选择算法运行时间都是线性级别的