算法

Java程序的基本结构

原始数据类型与表达式

语句

简便记法

数组

静态方法

Java库

标准库

自己编写的库

API

字符串

命令和参数

标准输出

格式化输出

标准输入

重定向与管道

基于文件的输入输出

标准绘图库（基本方法）

标准绘图库（控制方法）

标准输入/输出

二分查找（Binary Search）也称为折半查找，是一种在有序数组中查找特定元素的算法。该算法每次都将待查找的区间缩小一半，直到找到目标元素或者区间为空为止。

二分查找

Java基础

基础编程模型

对象知识（略）

数据抽象

public class Stats{    public static void main(String[] args)    {      Bag＜Double＞ numbers = new Bag＜Double＞();      while (! StdIn.isEmpty())          numbers.add(StdIn.readDouble());      int N = numbers.size();      double sum = 0.0;      for (double x : numbers)          sum += x;      double mean = sum/N;      sum = 0.0;      for (double x : numbers)          sum += (x - mean)＊(x - mean);      double std = Math.sqrt(sum/(N-1));      StdOut.printf(\"Mean: %.2f\\

背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中元素的数量）。

背包

子主题

先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型。

队列

下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型。

栈

定容栈

泛型

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。

private class Node{    Item item;    Node next;}

结构

在表头插入结点

从表头删除结点

在表尾插入结点

其他位置的插入和删除操作

删除指定的结点

在指定结点前插入一个新结点

for (Node x = first; x ! = null; x = x.next){    // 处理x.item}

遍历

增删改查

操作

public class Stack＜Item＞ implements Iterable＜Item＞{    private Node first; // 栈顶（最近添加的元素）    private int N;       // 元素数量    private class Node    {  // 定义了结点的嵌套类      Item item;      Node next;    }    public boolean isEmpty() {  return first == null; }  // 或：N == 0    public int size()         {  return N; }    public void push(Item item)    {  // 向栈顶添加元素      Node oldfirst = first;      first = new Node();      first.item = item;      first.next = oldfirst;      N++;    }    public Item pop()    {  //从栈顶删除元素      Item item = first.item;      first = first.next;      N--;      return item;    }    // iterator()的实现请见算法1.4    // 测试用例main()的实现请见本节前面部分}

下压堆栈（链表实现）

栈的实现

public class Queue＜Item＞ implements Iterable＜Item＞{    private Node first; // 指向最早添加的结点的链接    private Node last;  // 指向最近添加的结点的链接    private int N;       // 队列中的元素数量    private class Node    {  // 定义了结点的嵌套类      Item item;      Node next;  }  public boolean isEmpty() {  return first == null;  }  // 或： N == 0.  public int size()         {  return N;  }  public void enqueue(Item item)  {  // 向表尾添加元素      Node oldlast = last;      last = new Node();      last.item = item;      last.next = null;      if (isEmpty()) first = last;      else            oldlast.next = last;      N++;  }  public Item dequeue()  {  // 从表头删除元素      Item item = first.item;      first = first.next;      if (isEmpty()) last = null;      N--;      return item;  }  // iterator()的实现请见算法1.4  // 测试用例main()的实现请见前面}

先进先出队列

队列的实现

import java.util.Iterator;public class Bag＜Item＞ implements Iterable<Item>{    private Node first;  //链表的首结点    private class Node    {        Item item;        Node next;    }    public void add(Item item)    {  // 和Stack的push()方法完全相同      Node oldfirst = first;      first = new Node();      first.item = item;      first.next = oldfirst;    }    public Iterator<Item> iterator()    {  return new ListIterator();  }    private class ListIterator implements Iterator<Item>    {        private Node current = first;        public boolean hasNext()        {  return current ! = null;  }        public void remove() { }        public Item next()        {            Item item = current.item;            current = current.next;            return item;        }    }}

背包的实现

链表

集合类数据类型的实现

背包、队列和栈

时间复杂度

空间复杂度

算法分析

基础

初级排序算法

归并排序

快速排序

优先队列

应用

排序

符号表

二叉查找树

平衡查找树

散列表

查找

无向图

有向图

最小生成树

最短路径

图

低位优先排序

MSD

高位优先排序

分类

count[]

数组统计分组的频率

频率统计

count[r+1]=count[r]

频率转换为索引

aux[count[a[i].key()]++] = a[i]

数据分类

回写

步骤

键索引计数法

字符串排序

单词查找树

子字符串查找

正则表达式

数据压缩

背景

导读

参考资料

算法