128kj
- 浏览: 600409 次
- 来自: ...
-
最新评论
-
lgh1992314：
相同的元素呢
一种离散化方法 -
HelloSummerR：
圆心的位置是随机的，于是圆的部分会落到canvas外，那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio：
好久没见到sokuban了，这有个java版的，带源码，可以参 ...
求推箱子的最小步数（java) -
肖泽文：
太好了，谢谢你。。有中文注释！
HTML5 推箱子游戏过关演示动画 -
swm8023：
删除操作，将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)（JAVA）
文章列表
基数排序可以说是扩展了的桶式排序，比如当待排序列在一个很大的范围内，比如0到999999内，那么用桶式排序是很浪费空间的。而基数排序把每个排序码拆成由d个排序码，比如任何一个6位数（不满六位前面补0）拆成6个排 ...
我们最常用的快速排序和堆排序等算法需要对序列中的数据进行比较，因为被称为基于比较的排序。
而非基于比较的排序有计数排序，桶排序，和在此基础上的基数排序。要注意的是，非基于比较的排序算法的使用都是有条件限制的，例如元素的大小限制。
假设待排序数据是一个随机过程产生，该过程将元素一致地分布在某区间上。
桶排序的思想就是把区间划分成n个相同大小的子区间，或称桶，然后将输入数分布到各个桶中去。因为输入数均匀分布，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。
举个例子：一年的全国高考考生人数为500万，分数 ...
容易理解的堆排序代码（JAVA）
- 博客分类：
- 排序
import java.util.Scanner;
public class Heap {
private int[] data;
/*输入数组元素,数组下标从1开始*/
public void input() {
System.out.println("请输入数组大小");
Scanner scanner = new Scanner(System.in);
...
从0到n-1，两两比较数组中的元素，如果前者大于后者，则交换之（如a[0]>a[1]，则交换a[0]和a[1]）。作一趟冒泡排序后，最大值就在最后一个位置a[n-1]上了。然后对余下的0到n-2个元素作第二趟冒泡排序，次最大值就去到倒数第二个位置a[n-2]上了，如此类推。
例如对10，-3，5，34，-34，5，0，9进行排序
第一趟：-3，5，10，-34，5，0，9，34
第二趟：-3，5，-34，5，0，9，10，34
第三趟：-3，-34，5，5，0，9，10，34
第四趟：-34，-3，5，0，5，9，10，34
第五趟：-34，-3，0，5，5，9 ...
二分查找又称折半查找，它是一种效率较高的查找方法。
折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
算法步骤描述
① 首先 ...
单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。
一.最短路径的最优子结构性质
该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。
假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的 ...
当每个任务有前后置关系时，需要找到一种满足前后置关系的路线，将任务完成。
如果将每个任务看成一个节点，任务之间的前后置关系表示为有向图时，这种路线顺序叫做为图进行拓扑排序。也叫关键路径分析。
比如有很多任务T1,T2,....
这些任务又是相互关联的，比如Tj完成前必须要求Ti已完成，这样T1,T2....序列关于这样的先决条件构成一个图，其中如果Ti必须要先于Tj完成，那么<Ti,Tj>就是该图中的一条路径，路径长度为1的就是一条边。拓扑排序就是把这些任务按照完成的先后顺序排列出来。显然，这样的顺序可能不是唯一的，比如Tk，Tl如果没有在一条路径上，那么他们之间的 ...
快速排序是典型的使用分治策略的一种交换排序.
一般步骤：
1）选择一个枢纽元素(关键点）；
2）使用该枢纽元素分割数组，使得比该元素小的元素在它的左边，比它大的在右边。并把枢纽元素放在合适的位置；
3）根据枢纽元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序算法即可。
由于关键点是用来比较的基准所以如果基准选择得当可以减少交换的次数, 从而提高算法效率 , 是比较有技巧的部分), 以该关键点元素作为基准, 从数组两头分别与之比较, 大的放右边,小的放左边,相等的无论哪边都成(干脆不动). 最后当遍历完数组一遍(即两头的标志指向同一个 ...
算法描述：Kruskal（克鲁斯卡尔）算法需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系。
算法过程：
1.将图各边按照权值进行排序
2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，寻找下一个最小权值的边。
3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。
import java.util.Scanner;
import java.util.Arrays;
public cl ...
import java.util.Scanner;
方法一：时间复杂度O(n^3)
class Edge {
/**
* 边的起点
*/
char vexa;
/**
* 边的终点
*/
char vexb;
/**
* 边的权植
*/
int weight;
Edge(char vexa, char vexb, int weight) {
this.vexa = vexa;
this.vexb = vexb;
...
优先级队列是不同于先进先出队列的另一种队列。每次去队列的是具有最高优先权的元素。
import java.util.Comparator;
public class PriorityQ<T>
{
private final int SIZE = 20;
private T[] queArray;
private int size;
private final Comparator<? super T> comparator;
public PriorityQ(Comparator<? su ...
并归排序：
将两个或两个以上的有序数组组合成一个新的有序数组，叫并归排序
排序过程
1、 设初始数组有n个数据，则可看成n个有序的子数组， 每个子数组长度为1；
2、 两两合并，得到n/2或n/2+1 个长度为2 或1 的有序子数组；
3、 再两两合并，…… 如此重复，直至得到一个长度为n 的有序数组为止。
下面是归并排序的一个简单的例子:
初始值 【49】 【38】 【65】 【97】 【76】 【13】 【27】
public class MergeSort {
public static void sort(int[] arr) {
...
import java.util.Queue;
import java.util.ArrayDeque;
// 顶点类
class Vertex
{
public char label;
public boolean wasVisited;//顶点是否被访问过的标志
public Vertex(char lab)
{
label = lab;
wasVisited = false;
}
}
//图的邻接矩阵表示实现
class Graph
...
遍历，直到图中所有顶点都被访问到为止。
import java.util.Stack;
// 图的邻接矩阵实现及深度优先搜索图dfs.java
//顶点类
class Vertex
{
public char label;
public boolean wasVisited;//此顶点是否被访问过
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
}
//图 ...
一、概念。
图： 是一种复杂的非线性数据结构。
图的二元组定义：
图G由两个集合V和E组成，记为：
G=(V, E) 其中： V 是顶点的有穷非空集合,
E是V中顶点偶对(称为边)的有穷集。
通常，也将图G的顶点集和边集分别记为V(G)和E(G) 。 E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。
有向图： 若图G中的每条边都是有方向的，则称G为有向图 (Digraph) 。
无向图： 若图G中的每条边都是没有方向的，则称G为无向图 (Undigraph) 。
完全图： 若无向图中的每个顶点之间存在着一条边，有向图中的每两个定点之间都存在着方向相反的两条边，则称 ...