首页 > 代码库 > 普林斯顿公开课 算法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:排序概述