Table of contents
介绍
现在计算机的广泛使用使得数据无处不在,而整理数据的第一步通常就是进行排序
所有的计算机都实现了各种排序算法以供系统和用户使用
为什么学它
即使你只是使用标准库中的排序算法,学习排序算法仍然有三大实际意义
- 对排序算法的分析将有助于你全面理解比较算法性能的方法
- 类似的技术也能有效解决其他类型的问题
- 排序算法常常是我们使用算法解决其他问题的第一步
排序算法类的模板
package algorithms4.sort;
import edu.princeton.cs.algs4.In;
public class Example {
public static void sort(Comparable[] a){
//排序算法
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
//在单行中打印数组
for (int i = 0; i < a.length; i++) {
System.out.println(a[i] + " ");
}
System.out.println();
}
public static boolean isSorted(Comparable[] a){
//测试数组元素是否有序
for (int i = 0; i < a.length; i++) {
if (less(a[i], a[i -1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
//从标准输入读取字符串,将他们排序并输出
String[] a = new In("需要排序的数据文件").readAllStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
我们会将排序算法放在类的sort()方法中,该类还将包含辅助函数less类()和exch()(可能还会有其他辅助函数)以及一个示例用例main()
为了区别不同的排序算法,我们为相应的类取了不同的名字,例如Insertion.sort(),Merge.sort(),Quick.sort()等
这个类展示的是数组排序实现的框架,对于我们学习的每种排序算法,我们都会为这样一个类实现一个sort()方法并将example改为算法的名称
验证
通过assert isSorted(a);来确认排序后的数组元素都是有序的,尽管一般都会做简单地测试,并从数学上证明算法的正确性,但是实现每个算法时加上这条语句仍是必要的
如果我们只使用exch()来交换数组的元素,这个测试就足够了
但是当我们直接将值存入数组的方式(也就是原数组不变,得到另一个排序数组)
这条语句就无法提供足够的保证了(例如,凭空造出一个1,2,3数组,哈哈)
性能评估
运行时间.评估算法的性能,计算各个排序算法在不同的随机输入下的基本操作的次数(包括比较和交换,或者是读写数组的次数)
在研究排序算法时,我们需要计算比较和交换的数量,对于不交换的算法,我们会计算访问数组的次数
-
额外的内存使用
排序算法的额外内存开销和运行时间是同样重要的
排序算法可以分为两类
- 除了函数调用所需的栈和固定数量的实例变量之外无须额外内存的原地排序算法
- 以及需要额外内存来存储另一份数组副本的其他排序算法
数据类型
我们的排序算法模板适用于任何实现了Comparable接口的数据类型,遵循java惯例的好处是,很多你希望排序的数据都实现了comparable接口,例如基本类型,以及String和其他许多高级数据类型,(如file和url)都实现了comparable接口
因此,可以直接使用这些类型的数组作为参数调用我们的排序方法
在创建自己的数据类型时,我们只需要实现Comparable接口就能保证用例代码将其排序
实现compatable接口中的compareTo方法来定义目标对象类型的自然排序规则
如下面的date数据类型(@Data注解转向另一篇博客lombok)
package algorithms4.sort;
import lombok.Data;
@Data
public class DateExample implements Comparable<DateExample> {
private final int month;
private final int day;
private final int year;
public DateExample(int d, int m, int y){
day = d;
month = m;
year = y;
}
@Override
public int compareTo(DateExample that) {
if (this.year < that.year) {
return -1;
} else if (this.year > that.year) {
return 1;
} else if (this.month < that.month) {
return -1;
} else if (this.month > that.month) {
return 1;
} else if (this.day < that.day) {
return -1;
} else {
return this.day > that.day ? 1 : 0;
}
}
@Override
public String toString(){
return year + "/" + month + "/" + day;
}
}
compareto必须实现一个完整的比较接口
数学意义上
当两个元素满足
1.自反性,对于所有的v,v=v
2.反对称性,有v<w情况的存在,都有v>w的情况存在
3.传递性,如果v<=w,且w<=x,则v<=x
compareto实现了我们的主键抽象,它给出了实现了comparable接口的任意数据类型的对象的大小顺序的定义
