Java架构师鲁班二期学习笔记

1.两层for循环实现插入排序

public static ArrayList<Integer> sort(ArrayList<Integer> a) {
        for (int i = 1; i < a.size(); i++) {//从第二个元素开始，往前找到属于自己的位置下标
            int tmp = a.get(i);//当前要插入有序数组的元素tmp
            int j = i - 1;
            for (; j >= 0; j--) {
                if (a.get(j)<tmp) {//目前拿到的a[j]值小于tmp，结束本轮
                    break;
                } else
                   a.set(j + 1, a.get(j));//否则有序的a[0]~a[j]中a[j]后移让出一个位置
            }
            a.set(j + 1, tmp);//将tmp插在j+1
        }
        return a;
    }

2.使用自定义简单的栈来实现2个栈的插入排序

Stack自定义内容：

package day01;
import java.util.ArrayList;

public class Stack {
    public ArrayList<Integer> a;//核心内容区a列表
    public Stack(){
        a = new ArrayList<Integer>(10);
;    }
    public int pop(){
        if(a.size()<=0){
            return -1;//-1表示栈为空
        }else {
          return a.remove(a.size()-1);//弹出栈顶元素，返回它
        }
    }
    public void push(int val){
          a.add(val);//增加val元素
    }
    public int top(){
        return a.size()>0?a.get(a.size()-1):-1;//返回栈顶元素
    }
    public ArrayList<Integer> print(){
        return a;//打印核心数组
    }
}

插入排序实现部分：

Stack s = new Stack();//有序部分
Stack r = new Stack();//待排部分
//输入部分 r栈元素随机初始化
for(int in=0;in<100;in++) {
        r.push((int)(Math.random()*1000));
   }
   
 //核心算法部分
 while((tmp=r.pop())!=-1){//待排部分还有元素时
            i=0;
            while(s.top()>tmp){//有序部分的栈顶比tmp大则弹出，让tmp找到合适的位置
                r.push(s.pop());弹出的元素放r里面寄存
            }
            s.push(tmp);//放入S栈
        }
 //