原创

常见算法的动画展示

一、基本算法

1. 堆栈

栈是后进先出

数组实现

链表实现

2. 队列

队列是先进先出

数组实现

链表实现

二、递归

1. 阶乘

1 * 2 * 3 * 4 * n 求阶乘

1
2
3
4
5
6
7
8
public void factorial(int n){
if( n <= 1){
return 1;
}else{
subSolution = factorial(n - 1);
return subSolution * n;
}
}

2. 翻转字符串

1
2
3
4
5
6
public static String reverse(String originStr) {
if(originStr == null || originStr.length() <= 1) {
return originStr;
}
return reverse(originStr.substring(1)) + originStr.charAt(0);
}

三、树

这里模拟一串数字看不同的树是怎么存储的

12 12 12 11 9 6 5 3

1. 二叉树

2. AVL树

AVL树是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是。增加和删除元素的操作则可能需要借由一次或多次树旋转,以实现树的重新平衡。

3. 红黑树

红黑树(英语:Red–black tree)是一种自平衡二叉查找树。

4. 伸展树

在伸展树上的一般操作都基于伸展操作:假设想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法, 在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

根据伸展树的特性,我们对8进行查找就变成下面这样

5. B树

6. B+树

四、排序算法

1. 冒泡排序

特点:效率低,实现简单
原理:将待排序列中最大的数往后冒泡,成为新的序列,重复以上操作直到所有元素排列完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void maoPao(int []array){
int temp;//交换数据
System.out.println("\n冒泡排序:");
for(int i=1;i<array.length;i++) { //只需要比较数组元素个数减一次
for(int j=0;j<array.length-1;j++) {
if(array[j]>array[j+1]) {
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
System.out.print("第"+i+"次:");
for(int i=0;i<array.length;i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
}

2. 选择排序

特点:效率低,容易实现。
原理:每一趟从待排序序列选择一个最小的元素放到已排好序序列的首位,剩下的位待排序序列,重复上述步骤直到完成排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
*选择排序
*/
public static void xuanZe(int []array) {
int index,temp;
System.out.println("\n选择排序:");
for(int i=0;i<array.length-1;i++) {
index=i;//用来记住数组元素的下标
for(int j=i+1;j<array.length;j++) {
if(array[index]>array[j]) {
index=j;//只对index值改变,不交换元素位置
}
}
if(i!=index) {
temp=array[index];
array[index]=array[i];
array[i]=temp;
}//一轮排序进行一次数组位置交换
System.out.print("第"+i+"次:");
for(int i=0;i<array.length;i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
}

3. 插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
*插入排序
*/
public static void chaRu(int []array) {
int temp;
System.out.println("\n插入排序:");
for(int i=1;i<array.length;i++) {
int j=i;
temp = array[i];
while( j>0 && temp < array[j-1]) {
array[j] = array[j-1];
j--;
}
array[j] = temp;
System.out.print("第"+i+"次:");
show(array);
}
}

4. 快速排序

特点:高效,时间复杂度为nlogn。
原理:采用分治法的思想:首先设置一个中间值,然后以这个中间值为划分基准将待排序序列分成比该值大和比该值小的两部分,将这两部分再分别进行快速排序
直到序列只剩下一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**快速排序
* */
public static void kuaiSu(int []array,int left,int right){
if(left < right) {
int i=left,j=right;
int pivot = array[left];//选择最左边的元素作为中间值

/**
* 分治
*/
while(i < j) {
while(i < j && array[j] >= pivot) {
j--;
}
if(i < j) {
array[i] = array[j];
i++;
}
while(i < j&& array[i] < pivot){
i++;
}
if(i < j) {
array [j] =array [i];
j--;
}
}
array [i]=pivot;
//递归
kuaiSu(array,left,i-1);
kuaiSu(array,i+1,right);
}
}
分享