基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

(1)初始状态：无序区为R[1..n]，有序区为空。

(2)第1趟排序: 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1] 交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

(3)第i趟排序: 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。 该趟排序从当前无序区中选出关键

贪心算法实现缩水处理的思想就是：

每次从待处理集合S中选择出一个能够覆盖集合S中最多字符串的一个字符串s1，将s1放入缩水处理后集合T中，将s1从S中删除掉，这样执行了一次选择过程；

再从S-{s1}中选择出一个能够覆盖集合S-{s1}中最多字符串的一个字符串s2，将s2放入到T中，并将s2从S中删除掉；

……

反复执行，直到S={}时计算终止，产生缩水处理的集合T为所求。

基于上面思想，实现的代码如下所示：

package org.shirdrn.shrink;

import java.util.ArrayList;

AprioriTid算法的思想，是在Apriori算法思想的基础上做了一点改进，就是增加了一个Tid集合，用来代替事务数据库，这样扫描统计支持计数的开销降低了。

在Apriori算法实现的基础上，AprioriTid算法实现还是比较容易的。下面是我使用Java语言实现的AprioriTid算法，实现了AprioriTidAlgorithm 类，包含了频繁项集的挖掘过程和频繁关联规则的挖掘过程。

算法实现

（一）核心类

package org.shirdrn.datamining.association;

AprioriTid算法是一个挖掘关联规则的算法，是在Apriori算法的基础上改进的算法。它也是采用两阶段挖掘的思想，并且同Apriori算法不同的是：

（1）Apriori算法多次扫描事务数据库D；AprioriTid算法只扫描一次事务数据库D，初始化一个所谓的事务集合T1。

（2）Apriori算法生成频繁k-项集，根据候选频繁k-项集Ck，扫描事务数据库统计Ck中项集支持计数；AprioriTid算法生成频繁(k-1)-项集之后，根据候选频繁k-项集Ck与Tk-1集合构造Tk集合，扫描Tk集合统计Ck中项集的支持计数。

T1 = D，此时T1最大，而在k>1

基本思想

堆的定义：

n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称堆性质)：

(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤FLOOR(n/2))

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满 足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若 存在)结点的关键字。

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。

根结点(亦称为堆顶)的关键

Apriori算法的思想还是很容易理解的，实现起来虽然麻烦，但是还是比较容易的。下面是我使用Java语言实现的Apriori算法，实现了AprioriAlgorithm 类，包含了频繁项集的挖掘过程和频繁关联规则的挖掘过程。

另外，有一个辅助类ProperSubsetCombination用于计算一个频繁项集的真子集，采用组合原理，基于数值编码原理实现的组合求解集合的真子集。

算法实现

（一）核心类

Apriori算法的核心实现类为AprioriAlgorithm，实现的Java代

Apriori算法是一个挖掘关联规则的算法，是Agrawal等设计的一个基本算法，这是一个采用两阶段挖掘的思想，并且基于多次扫描事务数据库来执行的。Apriori算法的设计可以分解为两步骤来执行挖掘：

1、从事务数据库（D）中挖掘出所有频繁项集。

支持度大于最小支持度minSup的项集（Itemset）称为频集（Frequent Itemset)。

首先需要挖掘出频繁1-项集；

然后，继续采用递推的方式来挖掘频繁k-项集（k>1），具体做法是：

在挖掘出候选频繁k-项集（Ck）之后，根据最小置信度minSup来筛选，得到频

基本思想

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

(1)初始状态：

无序区为R[1..n]，有序区为空。

(2)第1趟排序：

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1] 交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

(3)第i趟排序：

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。 该趟排

基本思想

设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：

(1) 分解：

在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间 中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos) 上，它无须参加后续的排序。

注意：

基本思想

将被排序的记录数组R[0..n-1]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根 据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其 向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

(1)初始: R[0..n-1]为无序区。

(2)第一趟扫描:从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者 在上，则交换二者的位置。即依次比较(R[n-1]，R[n-2])，(R[n-2]，R[n-

基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

算法实现(Java语言)

package org.shirdrn.internal.sort;

/**
* <p><B>希尔排序算法类</B>
* <p>基本思想：
* <p

基本思想

直接插入排序的基本思想是：

假设待排序的记录存放在数组R[0..n-1]中。初始时，R[0]自成1个有序区，无序区为R[1..n-1]。 从i=1起直至i=n-1为止，依次将R[i]插入当前的有序区R[0..i-1]中，生成含n个记录的有序区。

算法实现(Java语言)

直接插入排序算法的Java实现如下：

package org.shirdrn.internal.sort;

/**
* <p><B>直接插入排序算法类</B>
* <p>基本思想：
* <p>
* <p>假设待

网上拷贝一段：

60年代挪威数学家就开始研究TOTO式足球彩票缩水理论，自80到90年代，由于TOTO足球彩票在挪威、丹麦、瑞典及法国、意大利十分流行，因此有一批学者便潜心研究足彩的优化缩水问题。在90年代初13场比赛的TOTO最优解已被全部证明。美国人Gail Howard发明的“旋转矩阵”组合法是一个计算复杂且很有特色的组合方法，使用此方法造就了若干位大奖得主。这是对那些“彩票软件无用论”者的一个很好的反驳。在此简要介绍一下足彩缩水法的数学原理。在数学上，一个复式投注单假设有n个三

旋转矩阵（Rotation matrix）是在乘以一个向量的时候有改变向量的方向但不改变大小的效果的矩阵。旋转矩阵不

在矩阵论中，实数正交矩阵是方块矩阵 Q，它的