day1:线性表及其应用

一：线性表

包含：顺序存储结构跟链式存储结构

1.1顺序存储结构

顺序存储结构

• 优点：
  尾插效率高，支持随机访问。
• 缺点：
  中间插入或者删除效率低。
• 应用：数组、ArrayList
• 重要API：add(),remove()

1.1.1 蛮力法

蛮力法（brute force method，也称为穷举法或枚举法）
是一种简单直接地解决问题的方法，常常直接基于问题的描述，
所以，蛮力法也是最容易应用的方法。但是，用蛮力法设计的算法时间特性往往也是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的 。（即输入资料的数量依线性成长，所花的时间将会以指数成长）

冒泡排序

• 应用：数据量足够小，比如斗牛游戏的牌面排序
  多关键字排序

冒泡排序算法的原理如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个.
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

   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]);
        }
    }

麻将运行结果