首页 > 代码库 > 普林斯顿公开课 算法2-1:排序概述
普林斯顿公开课 算法2-1:排序概述
目标
对所有类型的数据进行排序。
问题
排序函数如何知道比较的是哪种类型的数据呢?
回调函数
这时候就需要引入回调函数的概念了。回调函数就是将可执行的代码作为参数进行传递。
实现回调的方法
在Java中可以通过接口来实现,在C语言中可以通过函数指针来实现,C++中可以通过class-type functor,也就是重载操作符operator ()的类,在C#中可以使用Delegate委托,在Python/Perl/ML/javascript中可以直接传递函数。
JDK中提供了Comparable<T>接口,用于比较两个对象的大小。
比较函数需要满足的性质
比较函数需要满足如下性质才能让排序函数正常执行:
反对称性:a<=b且b<=a推出a=b
传递性:a<=b且b<=c推出a<=c
整体性:要么a<=b要么b<=a,要么两种情况都有
小数容差
假设a=1.16,b=1.08,c=1.00,容差是0.1。
那么a和b比较得出a=b,b和c比较得出b=c,a和c比较得出a>c,因此不符合传递性。
所以对小数进行排序时不能使用容差技术。
辅助函数
小于:判断两个Comparable函数是否小于
交换:交换Comparable数组中的两个元素
顺序检查:检查一个Comparable数组是否已经排序
当一个排序函数通过顺序检查时,就说明排序函数的算法是正确的。
代码
public
class
SortUtil {
/**
* 判断元素a是否小于元素b。
*/
public
static
boolean
less(Comparable a, Comparable b) {
return
a.compareTo(b) <
0
;
}
/**
* 交换数组中的两个元素
*/
public
static
void
exch(Comparable[] li,
int
a,
int
b) {
Comparable swap = li[a];
li[a] = li[b];
li[b] = swap;
}
/**
* 判断一个数组是否有序
*/
public
static
boolean
sorted(Comparable[] li) {
for
(
int
i =
0
; i < li.length -
1
; i++) {
if
(li[i].compareTo(li[i+
1
]) >
0
) {
return
false
;
}
}
return
true
;
}
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。