排序

数组排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int[] arr = {5,2,66,3,7};

int temp;

for(int i=0;i<arr.length;i++){
    for(int j=0;j<arr.length-i-1;j++){
        if(arr[j]>arr[j+1]){
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }

    }

}

双重 for 循环，当前元素与下一个元素对比，将较大值放于右侧，
时间复杂度：O(n^2)
空间复杂度：O(1)

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int[] selectSort(int[] args){//选择排序算法
    for (int i=0;i<args.length-1 ;i++ ){
        int min=i;
        for (int j=i+1;j<args.length ;j++ ){
            if (args[min]>args[j]){
                min=j;
            }
        }
        if (min!=i){
            int temp=args[i];
            args[i]=args[min];
            args[min]=temp;
        }
    }
    return args;
}

双重 for 循环，取出最小值或者最大值，交互数组位置，使最值位于数组两侧，最后得出一个升序/降序数组
时间复杂度：O(n^2)
空间复杂度：O(1)

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] insertSort(int[] args){//插入排序算法
    for(int i=1;i<args.length;i++){
        for(int j=i;j>0;j--){
            if (args[j]<args[j-1]){
                int temp=args[j-1];
                args[j-1]=args[j];
                args[j]=temp;
            }else break;
        }
    }
    return args;
}

时间复杂度：O(n^2)
空间复杂度：O(1)

快排

使用系统自带的排序方法 sorts
时间复杂度：O(nlogn)
空间复杂度：O(n)

树

树的遍历一般根据节点可分为三种：前序、中序、后序遍历
根据树的层级又有层级遍历

下面的代码就是一个树结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Node {
	private int no;
	private String name;
	private Node left;
	private Node right;
	//构造方法
	public Node(int no, String name) {
		this.no = no;
		this.name = name;
	}
	@Override
	public String toString() {
		return "Node[ no = " + no + ", name =" + name + " ]";
	}
}

前序

先取父节点，再取左节点，再取右节点

1
2
3
4
5
6
7
8
9
10
11
12
// 前序遍历
public void DLR() {
    System.out.println(this);// 先输出根节点
    // 左子树递归
    if (this.left != null) {
        this.left.DLR();
    }
    // 右子树递归
    if (this.right != null) {
        this.right.DLR();
    }
}

中序

先取左节点，再取父节点，再取右节点
中序遍历可以得出一个升序结构

1
2
3
4
5
6
7
8
9
10
11
12
// 中序遍历
public void LDR() {
    // 左子树递归
    if (this.left != null) {
        this.left.LDR();
    }
    System.out.println(this);// 先输出根节点
    // 右子树递归
    if (this.right != null) {
        this.right.LDR();
    }
}

后序

先取左节点，再取右节点，再取父节点

1
2
3
4
5
6
7
8
9
10
11
12
// 后序遍历
public void LRD() {
    // 左子树递归
    if (this.left != null) {
        this.left.LRD();
    }
    // 右子树递归
    if (this.right != null) {
        this.right.LRD();
    }
    System.out.println(this);// 先输出根节点
}

二叉树

红黑树

B树

B+树