关键词:
目标
对全部类型的数据进行排序。
问题
排序函数怎样知道比較的是哪种类型的数据呢?
回调函数
这时候就须要引入回调函数的概念了。回调函数就是将可运行的代码作为參数进行传递。
实现回调的方法
在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
;
}
}
普林斯顿公开课算法1-2:观察
这章通过一个简单的样例。具体说明算法分析的步骤。算法问题给定N个不同的整数,从中随意取出三个整数。请问有几种情况,使得取出的3个整数之和为0?解法能够使用暴力算法,代码例如以下:123456789for(int i=0;i<N;i++){&... 查看详情
mit公开课:算法导论笔记
课程链接:http://open.163.com/special/opencourse/algorithms.html第一课:算法分析基础1.介绍插入排序与归并排序,计算并比较最坏运行时间2.算法分析重点与渐近分析方法以下为个人笔记,根据字幕整理 第一课算法分析总结解决问题... 查看详情
普林斯顿算法课part2第二周作业_seamcarving
作业地址:http://coursera.cs.princeton.edu/algs4/assignments/seamCarving.html作业难点:1、如何获取图形的RGB属性? 需要研习下Picture、Color类等,使用getRGB()、getRed()、getGreen()、getBlue()等函数;2、如何计算从顶端到底部的最低energy曲线(即... 查看详情
计算机公开课推荐2019.8
...序设计抽象视频UCBCS61b:数据结构(Java)主页中文版教材普林斯顿Algs4:算法主页MIT6.006:算法导论系统nand2tetris主页CMU15-213:CSAPP视频笔记MIT6.828:操作系统主页中文版教材UCBCS61c:计算机体系结构主页MIT6.824:分布式系统主页斯... 查看详情
常用排序算法总结(代码片段)
排序算法目录排序算法1.排序算法概述1.1什么是排序算法?1.2、排序术语1.3算法总结1.4算法分类1.5比较排序与非比较排序1.5.1比较排序1.5.2非比较排序2.排序算法具体实现2.1冒泡排序2.1.1算法思想2.1.2算法描述2.1.3算法实现(1)数组... 查看详情
浅谈算法和数据结构:一栈和队列
...因。另外普林斯顿大学在Coursera 上也有这本书同步的公开课,还有另外一门算法分析课,这门课程的作者也是这本书的作者,两门课都挺不错的。计算机程序离不开算法和数据结构,本文简单介绍栈(St 查看详情
北京大学肖臻老师《区块链技术与应用》公开课-eth(代码片段)
ETH部分北京大学肖臻老师《区块链技术与应用》公开课笔记-BTC文章目录14-ETH-以太坊概述15-ETH-账户16-ETH-数据结构17-ETH-交易树和收据树18-ETH-GHOST协议19-ETH-挖矿算法20-ETH-难度调整21-ETH-权益证明22-ETH-智能合约23-ETH-TheDAO24-ETH-反思25-E... 查看详情
c++26常用算法(代码片段)
目录 一、概述1.1常用遍历算法1.1.1算法简介1.1.2for_each遍历算法1.1.3transform遍历算法1.2常用查找算法1.2.1算法简介1.2.2find查找算法1.2.3find_if查找算法1.2.4adjacent_find查找算法1.2.5binary_search查找算法1.2.6count查找算法1.2.7count_if查找算法1... 查看详情
10点公开课:视频质量评价基础与实践
...deoStack邀请到了SSIMWAVE联合创始人与研究员曾凯,本次公开课主要概述视频质量评价的基础概念和相关算法,并以端到端的视频质量监控系统为例,来讲解质量评价解决方案在实 查看详情
网易公开课_算法导论_笔记a
http://open.163.com/special/opencourse/algorithms.html 个人理解 渐进分析istoignoremachine-dependentconstantsand,insteadoftheactualrunningtime lookatthegrowthoftherunningtime (以下=表近似、a=b=c、a与 查看详情
斯坦福公开课-机器学习1.机器学习的动机和应用(吴恩达andrewng)
文章目录0三个目标0先修课程要求基本工具1-网址2-邮箱3-本系列课程链接1机器学习的定义1-1非正式定义1-2正式的定义2监督学习(SupervisedLearning)2-1回归问题——连续拟合线(预测房子价格)2-2分类问题——离散数... 查看详情
机器学习公开课笔记第五周之优化机器学习算法
一,提高机器学习算法准确度的方法当我们的机器学习算法不能准确预测我们测试数据时,我们可以尝试通过以下方法提高我们机器学习的算法准确度1),获得更多的训练样例2),减少特征数3),增加特征数4),增加多项式特征5)... 查看详情
代码随想录算法公开课!
关注代码随想录的录友,基本都是跟着代码随想录一起刷题的。目前代码随想录的内容是完全开放在代码随想录网站,Github,和Gitee上,同时也出版了《代码随想录》纸质版。这套刷题顺序和题解帮助了非常多的... 查看详情
斯坦福公开课-机器学习1.机器学习的动机和应用(吴恩达andrewng)
文章目录0三个目标0先修课程要求基本工具1-网址2-邮箱3-本系列课程链接1机器学习的定义1-1非正式定义1-2正式的定义2监督学习(SupervisedLearning)2-1回归问题——连续拟合线(预测房子价格)2-2分类问题——离散数... 查看详情
网易公开课对我影响最深的五门课
耶鲁大学公开课:心理学导论你的梦应该如何解析?男人和女人在两性需求的性质和程度是否不同?猩猩能否学习手语?为什么我们不能胳肢自己?本课程试图回答这些以及其他诸如此类的问题,并提供了思想和行为科学的研究... 查看详情
人工智能免费公开课
本周四,人工智能免费公开课!1月18日(本周三),诚邀您参加唐宇迪老师的免费公开课~唐宇迪老师,计算机博士,专注于机器学习与计算机视觉领域,深度学习领域一线实战专家。参与多个国家级计算机视觉项目,多年数据... 查看详情
排序算法之计数排序
概述简单来说,计数排序就是申请一个相同数据范围的数组空间,计算每个数字各有几个,如此即可.如一个数组为:[5,2,3,4,6,3,1,0]申请一个长度为6的数组(因为数组范围为0-5),其中的值为:[1,1,1,2,1,1,1]其数组意思就是,0有1个,1有1个,类推... 查看详情
union-find(代码片段)
并查集前言来自知乎,Coursera上普林斯顿大学的算法公开课,稍微来博客上写写记记。课程资源:1.Algorithms,PartI2.Algorithms,PartII3.Algorithms,4thEditiondynamicconnectivity动态连通性问题,这里的连通是一个等价关系,满足:symmetric:自反性... 查看详情