数据结构与算法
常用数据结构：数组、栈、队列、链表、树、哈希表、堆、图
| 数据结构 |
优点 |
缺点 |
| 数组 |
插入快 |
删除慢、大小固定、只能存储单一元素 |
| 有序数组 |
比无需数组查询快 |
插入删除慢、大小固定、只能存储单一元素 |
| 栈 |
先进后出 |
存储其他项很慢 |
| 队列 |
先进先出 |
存储其他项很慢 |
| 链表 |
插入快、删除慢 |
查找慢 |
| 二叉树 |
如果树是平衡的、则查找、插入、删除都快 |
删除算法复杂 |
| 红黑树 |
查找、插入、删除都快，树总是平衡的算法复杂 |
算法复杂 |
| 哈希表 |
如果关键字已知则存取快 |
删除慢。不知关键字存取慢，堆存储空间使用不充分 |
| 堆 |
插入、删除快，对最大数据项存取快 |
对其他数据存取慢 |
| 图 |
对现实世界建模 |
有些算法慢且复杂 |
算法
算法简单来说就是解决问题的步骤。
在Java中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算
法范畴的重要领域。
算法的五个特性
有穷性、确定性、可行性、有输入、有输出
算法的设计原则
正确性、可读性、健壮性、高效率与低存储量需求
冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static void main(String[] args) {
int [] arr={5,8,1,4,3,9,7,6,2};
for (int i=0;i<arr.length-1;i++){
for (int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
arr[j]=arr[j]+arr[j+1];
arr[j+1]=arr[j]-arr[j+1];
arr[j]=arr[j]-arr[j+1];
}
}
}
for(int m=0;m<arr.length;m++){
System.out.print(arr[m]+"\t");
}
}
|
插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public static void main(String[] args) {
int [] arr={5,8,1,4,3,9,7,6,2};
for (int i=1;i<arr.length;i++){
for (int j=i;j>0;j--){
if(arr[j-1]>arr[j]){
arr[j]=arr[j]+arr[j-1];
arr[j-1]=arr[j]-arr[j-1];
arr[j]=arr[j]-arr[j-1];
}else{
break;
}
}
}
for(int m=0;m<arr.length;m++){
System.out.print(arr[m]+"\t");
}
}
|
选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| for (int i=0;i<arr.length-1;i++){
int min=i;
for (int j =i; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min=j;
}
}
//最小值没放到最前面
if(min!=i){
arr[i]=arr[i]+arr[min];
arr[min]=arr[i]-arr[min];
arr[i]=arr[i]-arr[min];
}
System.out.println("第"+(i+1)+"次选择排序的值：");
System.out.println(Arrays.toString(arr));
}
|
用大 O 表示法都需要 O(N2) 时间级别。
一般不会选择冒泡排序，虽然冒泡排序书写是最简单的，但是平均性能是没有选择排序和插入排序好的。
选择排序把交换次数降低到最低，但是比较次数还是挺大的。当数据量小，并且交换数据相对于比较数据更加耗时的情况下，可以应用选择排序。
在大多数情况下，假设数据量比较小或基本有序时，插入排序是三种算法中最好的选择。
栈