java算法
最炫小小生；Java数据结构与算法[20讲]
note01 数组
note02
1.简单排序
1.1冒泡排序
1.2选择排序
1.3插入排序
1.1冒泡
//从小到大
int tmp=0;
for(int i=0;i<arr.length-1;i++){
for(int j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
tmp = arr[j];
arr[j] = arr[j-1];
arr[j] = tmp;
}
}
}
1.2选择排序
int k=0;
long tmp=0;
for(int i=0;i<arr.length-1;i++){
k=i;
for(int j=i;j<arr.length;j++){
if(arr[j]<arr[k]){
k=j;
}
}
tmp=arr[i];
arr[i]=arr[k];
arr[k]=tmp;
}
1.3插入排序
long tmp=0;
for(int i=1;i<arr.length;i++){
tmp=arr[i];
int j=i;
while(j>0 && arr[j]>=tmp){
arr[j]=arr[j-1];
j--;
}
arr[j]=tmp;
}
note03 栈和列队
//列队类，先进先出
public class MyQueue{}
note04 链表
/*
* 链节点，相当于是车厢
*/
public class Node{
//数据域
public long data;
//指针域
public Node next;
public Node(long value){
this.data = value;
}
//显示方法
public void display(){
sout(data + " ");
}
}
/*
* 链表，相当于火车
*/
public class LinkList{
//头结点
private Node first;
public LinkList(){
first = null;
}
...
}
note05 双端链表
note06 递归
分递和归，递归的return返回到开头
三角数字：1 3 6 10 15 21。。。
public static void getNumber(int){
int total = 0;
while(n > 0){
total = total + n;
n --;
}
return total;
}
public static int getNumberByRecursion(int n){
if(n == 1){
return 1;
}else{
return n + getNumberByRecursion(n - 1);
}
}//两者结果相同
Fibonacci
public static int getNumber(int n){
if(n == 1){
return 0;
}else if(n == 2){
return 1;
}else{
return getNumber(n - 1)+ getNumber(n - 2);
}
}
note07 递归的高级应用
汉诺塔
public class HanoiTower{
/*
* 移动盘子
* topN:移动的盘子数
* from:起始塔座
* inter:中间塔座
* to:目标塔座
*/
public static void doTower(int topN,char from,char inter,char to){
if(topN == 1){
sout("盘子1，从"+ from + "塔座到" + to + "塔座");
}else{
doTower(topN -1 , from , to, inter);
sout("盘子" + tonN + "，从"+ from + "塔座到" + to + "塔座");
doTower(topN -1, inter, from, to);
}
}
}
note08 希尔排序
基于插入排序
插入排序的缺陷，多次移动：
假如一个很小的数据在靠右端的位置上，那么要将该数据排序到正确的位置上，则所有的中间数据都需要向右移动一位
优点：
希尔排序通过加大插入排序中元素之间的间隔，并对这些间隔的元素进行插入排序，从而使得数据可以大幅度的移动。当完成该间隔的排序后，希尔排序会减少数据的间隔再进行排序。
间隔的计算：
间隔h的初始值为1，通过h=3*h+1来计算循环，直到该间隔大于数组的大小时停止。最大间隔为不大于数组大小的最大值。
间隔的减少：
可以通过公式h=(h-1)/3来计算
public class Shellsort{
public static void sort(long[] arr){
//初始化一个间隔
int h = 1;
//计算最大间隔
while(h < arr.length / 3){
h = h * 3 + 1;
}
while(h > 0){
//进行插入排序
long tmp = 0;
for (int i = h; i < arr.length; i ++){
tmp = arr[h];
int j = i;
while(j > h - 1 && arr[j - h] >= tmp){
arr[j] = arr[j - h];
j -= h;
}
arr[j] = tmp;
}
//减小间隔
h = (h - 1) / 3;
}
}
}
note09 快速排序
通常将一个数组划分成两个子数组，然后递归调用自身为每个子数组进行快排
一般将数组最右端的数据为关键字
//划分数组
public static int partition(long arr[],int left,int right,long point){
int leftPtr = left - 1;
int rightPtr = right;//因为从最右端前一个位置循环的，所以不用+1
while(true){
//循环,将比关键字大的留在左端
while(leftPtr < rightPtr && arr[++leftPtr] < point);
//循环，将比关键字大的留在右端
while(rightPtr > leftPtr && arr[--rightPtr] > point);
if(leftPtr >= rightPtr){
break;
}else{
long tmp = arr[leftPtr];
arr[leftPtr] = arr[rightPtr];
arr[rightPtr] = tmp;
return leftPtr;
}
}
//将关键字和当前leftPtr所指的这一个进行交换
long tmp = arr[leftPtr];
arr[leftPtr] = arr[right];
arr[right] = tmp;
}
public static void sort(long[] arr, int left, int right){
if(right - left <= 0){
return;
}else{
//设置关键字
long point = arr[right];
//获得切入点，同时对数组进行划分
int partition = partition(arr,left,right,point);
//对左边的子数组进行快速排序
sort(arr,left,partition-1);
//对右边的子数组进行快速排序
sort(arr,partition + 1, right);
}
}
note11 二叉树的基本操作
1.插入节点
从根节点开始查找一个相应的节点，这个节点将成为新插入节点的父节点。当父节点找到后，通过判断新节点的值比父节点的值大小来决定是连接到左子节点还是右子节点
2.查找节点
从根节点开始查找，如果查找的节点值比当前节点的值小，则继续查找其左子树，否则查找其右子树。
//二叉树类
public class Tree{
//根节点
public Node root;
//插入节点
public void insert(long value){
//封装节点
Node newNode = new Node(value);
//引用当前节点
Node current = root;
//引用父节点
Node parent;
//如果root为null，也就是第一插入的时候
if(root == null){
root = newNode;//这里把第一次插入当成了root
return;
}else{
//父节点指向当前节点
parent = current;
//如果当前指向的节点数据比插入的要大，则向左走
if(current.data > value){
current = current.leftChild;
if(current == null){
parent.leftChild = newNode;
return;
}
}else {
current = current.rightChild;
if(current == null){
parent.rightChild = newNode;
return;
}
}
}
}
//查找节点
public Node find(long value){
//引用当前节点，从根节点开始
Node current = root;
//循环，只要查找值不等于当前节点的数据项
while(current.data != value){
//进行比较，比较查找值和当前节点的大小
if(current.data > value){
current = current.leftChild;
}else{
current = current.rightChild;
}
if(current == null){
return null;
}
}
return current;
}
}
//二叉树节点
public class Node{
//数据项
public long data;
//数据项
public String sData;
//左子节点
public Node leftChild;
//右子节点
public Node rightChild;
//构造方法
public Node(long data,String sData){
this.data = data;
this.sData = sData;
}
}
note12 遍历二叉树
遍历树
前序遍历
1.访问根节点
2.前序遍历左子树
3.前序遍历右子树
中序遍历
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
后序遍历
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点
//二叉树类
public class Tree{
//前序遍历
public void frontOrder(Node localNode){
if(localNode != null){
//访问根节点
sout(localNode.data + "," + localNode.sData);
//前序遍历左子树
frontOrder(localNode.leftChild);
//前序遍历右子树
frontOrder(localNode.rightChild);
}
}
//中序遍历
public void inOrder(Node localNode){
if(localNode != null){
//中序遍历左子树
inOrder(localNode.leftChild);
//访问根节点
sout(localNode.data + ", " + localNode.sData);
//中序遍历右子树
inOrder(localNode.rightChild);
}
}
//后序遍历
public void afterOrder(Node localNode){
if(localNode != null){
//后序遍历左子树
afterOrder(localNode.leftChild);
//后序遍历左子树
afterOrder(localNode.rightChild);
//访问根节点
sout(localNode.data + ", " + localNode.sData);
}
}
}
note13 删除二叉树节点
删除节点是二叉树操作中最复杂的。在删除之前首先要查找药删的节点。找到节点后，这个要删除的节点可能会有三种情况需要考虑。
1.该节点是叶子节点，没有子节点
要删除叶节点，只需要改变该节点的父节点的引用值，将指向该节点的引用设置为null就可以了
2.该节点有一个子节点
改变父节点的引用，将其直接指向要删除节点的子节点
3.该节点有两个子节点
要删除有两个子节点的节点，就需要使用它的中序后继来替代该节点
//第13讲 02:00