首页 > 代码库 > 普林斯顿公开课 算法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; }}普林斯顿公开课 算法2-1：排序概述
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。