一：线性表
包含：顺序存储结构跟链式存储结构
1.1顺序存储结构
顺序存储结构
- 优点：
尾插效率高，支持随机访问。 - 缺点：
中间插入或者删除效率低。 - 应用：数组、ArrayList
- 重要API：add(),remove()
1.1.1 蛮力法
蛮力法（brute force method，也称为穷举法或枚举法）
是一种简单直接地解决问题的方法，常常直接基于问题的描述，
所以，蛮力法也是最容易应用的方法。但是，用蛮力法设计的算法时间特性往往也是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的 。（即输入资料的数量依线性成长，所花的时间将会以指数成长）
冒泡排序
- 应用：数据量足够小，比如斗牛游戏的牌面排序
多关键字排序
冒泡排序算法的原理如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个.
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
public static void bubbleSort(int[] array){
//3 1 5 8 2 9 4 6 7 n*(n-1)/2 n
//第一轮比较结果：1 3 5 2 8 4 6 7 9 数字最大的沉到最低
for(int i=array.length-1;i>0;i--) {
boolean flag=true;
for (int j = 0; j < i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag=false;
}
}
if(flag){
break;
}
}
}
平均时间复杂度为O(n^2)
选择排序
（以第一个元素为基准，下标index先固定在第一个元素下，然后面的元素循环依次跟第一个元素比较，如果找到比第一个元素小的，则下标index跑到这个小的数下面，然后其数据在跟当前index下标的数据比较，直到第一轮结束找到数组中最小的元素，下标固定在最小元素的位置，然后最小元素跟第一个元素呼唤位置。）
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
int[] array=new int[]{3,2,5,8,1,9,4,6,7}
public static void selectSort(int[] array){
for(int i=0;i<array.length-1;i++) {
int index = i;
for (int j = i+1; j < array.length; j++) {
if (array[j] < array[index]) {
index = j;
}
}
//{1,2,5,8,3,9,4,6,7};
if(index!=i) {//如果已经是最小的，就不需要交换
int temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}
}
链式存储结构
链式存储结构
- 应用：LinkedList
- 优点：
插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活。 - 缺点：
不能随机查找，必须从第一个开始遍历，查找效率低
链表的应用.png
public class Mahjong {
public int suit;//筒，万，索
public int rank;//点数 一 二 三
public Mahjong(int suit, int rank) {
this.suit = suit;
this.rank = rank;
}
@Override
public String toString() {
return "("+this.suit+" "+this.rank+")";
}
}
@Test
public void addition_isCorrect() throws Exception {
LinkedList<Mahjong> list=new LinkedList<Mahjong>();
list.add(new Mahjong(3,1));
list.add(new Mahjong(2,3));
list.add(new Mahjong(3,7));
list.add(new Mahjong(1,1));
list.add(new Mahjong(3,8));
list.add(new Mahjong(2,2));
list.add(new Mahjong(3,2));
list.add(new Mahjong(1,3));
list.add(new Mahjong(3,9));
System.out.println(list);
radixSort(list);
System.out.println(list);
}
public static void radixSort(LinkedList<Mahjong> list){
//先对点数进行分组
LinkedList[] rankList=new LinkedList[9];
for (int i = 0; i < rankList.length; i++) {
rankList[i]=new LinkedList();
}
//把数据一个个放到对应的组中
while(list.size()>0){
//取一个
Mahjong m=list.remove();
//放到组中 下标=点数减1的
rankList[m.rank-1].add(m);
}
//把9组合并在一起
for (int i = 0; i < rankList.length; i++) {
list.addAll(rankList[i]);
}
//先花色进行分组
LinkedList[] suitList=new LinkedList[3];
for (int i = 0; i < suitList.length; i++) {
suitList[i]=new LinkedList();
}
//把数据一个个放到对应的组中
while(list.size()>0){
//取一个
Mahjong m=list.remove();
//放到组中 下标=点数减1的
suitList[m.suit-1].add(m);
}
//把3个组合到一起
for (int i = 0; i < suitList.length; i++) {
list.addAll(suitList[i]);
}
}
麻将运行结果
网友评论