数据结构与算法

1 线性存储与非线性存储

1.1 线性结构

1. 线性结构：特点数据元素直接存在一对一的线性关系
2. 线性结构有两种不同的存储结构，顺序存储（数组）和链式存储结构（链表）。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。
3. 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存方的数据元素以及相邻元素的地址信息。
4. 线性结构常见的有：数组，队列，链表和栈。

1.2 非线性结构

非线性结构：二维数组，多维数组，广义表，树结构，图结构。

2 数组

2.1 稀疏数组

当一个数组中大部分元素为0的时候，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组处理的方式：

1. 记录数组一共有几行几列，有多少个不同的值。
2. 把具有不同的元素的行列及值记录在一个小规模数组中，从而缩小程序的规模。

public class 稀疏数组 {
	
	public static void main(String[] args) {
		//创建一个原始的二维数组
		//0 ：表示没有棋子，1表示黑子，2表示白字
		int chessArr1[][] = new int [11][11];
		chessArr1[1][2] =1;
		chessArr1[2][3] = 2;
		//输出原始数组
		System.out.println("原始的二维为：");
		for(int [] row : chessArr1) {
			for(int data: row) {
				System.out.printf("%d   ",data);
			}
			System.out.println();
		}
		
		//将二维数组转稀疏数组
		// 1先遍历二维数组得到0数据的个数
		int sum = 0;
		for(int i = 0; i < 11 ; i++) {
			for(int j = 0; j < 11 ; j++) {
				if(chessArr1[i][j] != 0) {
					
					sum ++;
				}
			}
		}
		
		//创建对应的稀疏数组
		int sparseArr[][] = new int [sum +1][3];
		//给稀疏数组赋值
		sparseArr[0][0] = 11;
		sparseArr[0][1] = 11;
		sparseArr[0][2] = sum;
		
		int count = 0;
		//遍历二维数组，将非0的值存放到sparseArr中
		for(int i = 0; i < 11; i++) {
			for (int j = 0; j < 11; j++) {
				if(chessArr1[i][j] != 0) {
					count ++;
					sparseArr[count][0] = i; 
					sparseArr[count][1] = j;
					sparseArr[count][2] = chessArr1[i][j];
				}
			}
		}
		
		//输出稀疏数组的形式
		System.out.println();
		System.out.println("得到的稀疏数组");
		for(int i = 0; i < sparseArr.length ; i++) {
			System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
		}
		
		
		//将稀疏数组回复为原来的数组
		//第一步，先读取稀疏数组的第一行，根据第一行的数据创建原始的二维数组
		int chessArr2[][] = new int [sparseArr[0][0]][sparseArr[0][1]];
		//第二部，在稀疏数组后的几行的数据从第二行开始，并赋值给原始的二维数组

		for(int i =1; i < sparseArr.length; i++) {
			 chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
			 
		}
		
		
		//输出恢复后的二维数组
		System.out.println();
		System.out.println("恢复后的二维数组");
		for(int [] row : chessArr2) {
			for(int data: row) {
				System.out.printf("%d   ",data);
			}
			System.out.println();
		}
	}
}

3 队列

3.1 队列

1. 队列是一有序列表，可以使用数组或者是链表来实现.

2. 遵循先入先从的原则。

   ==一般我们采用rear 指针和front指针进行操作。==

3.2队列的模拟

队列是有序列表，使用数组结构来存储队列的数据。

队列的入队一般使用addQueue,addQueue的处理需要两个步骤。

public class ArrayQueueDemo {

	public static void main(String[] args) {
		//创建一个对象
		ArrayQueue  aq=new ArrayQueue(3);
		char key = ' ';//用于接收用户数据
		Scanner sc = new Scanner(System.in);
		boolean loop = true;
		//输出一个菜单
		while(loop) {
			System.out.println("s(show):显示队列");
			System.out.println("e(exit):退出队列");
			System.out.println("a(add):添加数据到队列");
			System.out.println("g(get):从队列取出数据");
			System.out.println("h(head):查看队列头的数据");
			key = sc.next().charAt(0);//接去第一个字符
			switch(key) {
			case 's':  //展示队列数据
				aq.showQueue();
				break;
			case 'a': //向队列添加数据
				System.out.println("请输入一个数");
				int value = sc.nextInt();
				aq.addQueue(value);
				break;
			case 'g': //获得队列的数据
				
				try {
					int res = aq.getQueue();
					System.out.printf("取出的数据实%d\n",res);
					aq.getQueue();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'h': //查看队列头的数据
				
				try {
					int res = aq.headQueue();
					System.out.printf("取出的数据实%d\n",res);

				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
			case 'e': //代表要退出
				sc.close();
				loop = false;
				break;
			default:
				break;
				
			}
				
		}
		System.out.println("程序退出");
	}

}


//使用数组模拟队列，编写一个ArrayQueue类
class ArrayQueue{
	private int maxSize;//设置数组的最大容量
	private int front;//队列头
	private int rear;//队列尾部
	private int [] arr;//该数据用于存放数据，模拟队列
	
	//创建队列的构造器
	public ArrayQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int [maxSize];
		front  = -1;  //指向队列头部，指向队列头的前一个位置
		rear = -1; //指向队列尾部，队列尾部包含对象最后一个数据，通俗的讲就是队列最后一个位置
	}
	
	//判断队列是否满
	public boolean isFull() {
		return rear == maxSize - 1;
	}
	
	//判断队列是否为空
	public boolean isNull() {
		return rear == front;
	}
	//数据是否添加到队列
	public void addQueue(int n) {
		//判读队列是否满
		if(isFull()) {
			System.out.println("队列满，不能加入数据");
			return;
		}
		rear ++ ; //让rear 后移动
		arr[rear] = n;
	}
	//判读队列的数据，出队列
	public int getQueue() {
		//判读队列是否为空
		if(isNull()) {
			//抛出异常
			throw new RuntimeException("队列为空，不能获取数据");
		}
		front ++;
		return arr[front];
	}
	
	//显示队列所有数据
	public void showQueue() {
		//将数组数据遍历
		if(isNull()) {
			System.out.println("队列为空，没有数据");
			return;
		}
		for(int i = 0; i < arr.length; i++ ) {
			System.out.printf("arr[%d]=%d\n",i,arr[i]);
		}
	}
	
	//显示队列的头数据，注意不是取出数据
	public int headQueue() {
		//判断
		if(isNull()) {
			throw new RuntimeException("队列空，没有数据");
		}
		return arr[front + 1];
	}
}

此处存在一个问题，就是我们只能使用一次，无法对队列进行多次使用。

将这个数组使用算法改变成为一个环形队列 方式，采用取模的方式。

3.3 判断队列为空队列为满

==front == rear 代表队列为空。==

当指针rear 小于队列的最大下标maxSize - 1,则将数据存入rear锁指向的数组元素中，否则无法存入数据

==rear == maxSize -1 代表队列已满==

3.4 使用数组模拟环形队列

思路：

1. front 变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素。

   front的初始值为0；

2. rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定。rear 的初始值为0；

3. 当队列满时，条件是(rear + 1)%maxSize == front 此时满。

4. 当队列为空的条件，rear == front 空

5. 当这样分析后，此时队列中有效的数据的个数是 (rear + maxSize - front)%maxSize //rear=1 front=0

6. 以上我们就可以按照我们的思路对原来的代码进行修改。

4. 链表

链表是有序的列表：

1. 链表是以节点的方式来存储的，是一种链式存储的方法存储。
2. 每个节点包含data域，next域，指向下一个节点。
3. 链表的各个节点不一定是连续存储
4. 链表分带头节点的链表和不带头结点的链表，根据实际的需求来确定。

4.1 单向链表

head 节点

单向链表的实现

1. 不存放具体的数据
2. 作用就是表示单链表头next

public class SingleLinkedListDemo {
	public static void main(String[] args) {
		//测试
		//创建节点
		HeroNode hero1 = new HeroNode(1,"松江","及时雨");
		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
		HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
		//创建链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);
		singleLinkedList.add(hero4);
		
		//显示链表
		singleLinkedList.list();
		
		
	}

}

//定义一个SingleLinkedList来管理我们的英雄
class SingleLinkedList{
	//先初始化一个头结点，一般上头结点不要动
	private HeroNode head = new HeroNode(0,"","");
	
	//添加节点到单向链表
	//思路，当不考虑编号顺序时
	//1 找到当前链表的最后节点
	//2,将最后这个节点的nex指向新节点
	public void add(HeroNode heroNode) {
		//因为head节点不能动，因此我们需要一个辅助遍历temo
		HeroNode temp = head;
		//遍历链表，找到最后
		while(true) {
			//找到链表的最后
			if(temp.next == null) {
				break;
			}
			//如果没有找到最后，将temp后移
			temp = temp.next;
		}
		//当退出while循环后，temp就指向链表的最后
		//将最后这个节点的next指向新的节点
		temp.next = heroNode;
	}
	//显示链表【遍历】
	public void list() {
		//判读是否为空
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		//因为头结点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode  temp = head.next;
		while(true) {
			//判断是否是否链表最后
			if(temp == null) {
				break;
			}
			//输出节点的信息
			System.out.println(temp);
			//将next后移,如果不后移将进入死循环
			temp = temp.next ;
		}
	}
}


//定义一个heroNode ,每个HeroNode对象就是一个节点

class HeroNode{
	public int no;
	public String name;
	public String nickName;
	public HeroNode next;//指向下一个节点
	
	//构造器
	public HeroNode(int no, String name, String nickName) {
		super();
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}

	public HeroNode() {
		super();
	}
}

目前，我们需要添加相关节点的进行有序添加。

有序添加

需要按照编号的顺序添加：

1. 首先找到新天节点的节点的位置，是通过辅助变量(指针)，通过遍历来搞定
2. 新的节点 next=temp.next
3. 将temp.next=新节点

public class SingleLinkedListDemo {
	public static void main(String[] args) {
		//测试
		//创建节点
		HeroNode hero1 = new HeroNode(1,"松江","及时雨");
		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
		HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
		//创建链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		/*
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);
		singleLinkedList.add(hero4);
		*/
		
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero2);
		
		//显示链表
		singleLinkedList.list();
	}
}

//定义一个SingleLinkedList来管理我们的英雄
class SingleLinkedList{
	//先初始化一个头结点，一般上头结点不要动
	private HeroNode head = new HeroNode(0,"","");
	
	//添加节点到单向链表
	//思路，当不考虑编号顺序时
	//1 找到当前链表的最后节点
	//2,将最后这个节点的nex指向新节点
	public void add(HeroNode heroNode) {
		//因为head节点不能动，因此我们需要一个辅助遍历temo
		HeroNode temp = head;
		//遍历链表，找到最后
		while(true) {
			//找到链表的最后
			if(temp.next == null) {
				break;
			}
			//如果没有找到最后，将temp后移
			temp = temp.next;
		}
		//当退出while循环后，temp就指向链表的最后
		//将最后这个节点的next指向新的节点
		temp.next = heroNode;
	}
	
	//第二种方式添加英雄时，根据排名将英雄插入到指定位置
	//如果有这个排名，则添加失败，并给出提示
	public void addByOrder(HeroNode heroNode) {
		//因为头结点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
		//因为单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
		HeroNode temp = head;
		boolean flag = false;  //false标记添加的编号是否存在，默认为false
		while(true) {
			if(temp.next == null) { //说明此时temp处于链表的最后
				break;
			}
			if(temp.next.no > heroNode.no) {
				//此时位置找到，就在temp的后边插入
				break;
			}else if(temp.next.no == heroNode.no) 
			{
				//说明希望添加的heroNode的编号已然存在
				flag = true;  //说明编号存在
				break;
			}
			temp = temp.next;  //后移，变量当前链表
		}
		//判断flag的值
		if(flag) {//不能添加，说明编号存在
			System.out.printf("准备插入的英雄的编号%d，已经存在,无法添加\n",heroNode.no);
			
		}else {
			//插入到链表中，temp后边
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}
	
	//显示链表【遍历】
	public void list() {
		//判读是否为空
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		//因为头结点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode  temp = head.next;
		while(true) {
			//判断是否是否链表最后
			if(temp == null) {
				break;
			}
			//输出节点的信息
			System.out.println(temp);
			//将next后移,如果不后移将进入死循环
			temp = temp.next ;
		}
	}
}


//定义一个heroNode ,每个HeroNode对象就是一个节点

class HeroNode{
	public int no;
	public String name;
	public String nickName;
	public HeroNode next;//指向下一个节点
	
	//构造器
	public HeroNode(int no, String name, String nickName) {
		super();
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}

	public HeroNode() {
		super();
	}
}

修改链表中的参数

1. 先找到该节点，通过遍历。
2. temp.name = newHeroNode.name;temp.nickName=newHeroNode.nickName;

public class SingleLinkedListDemo {
	public static void main(String[] args) {
		//测试
		//创建节点
		HeroNode hero1 = new HeroNode(1,"松江","及时雨");
		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
		HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
		//创建链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		/*
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);
		singleLinkedList.add(hero4);
		*/
		
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero2);
		
		System.out.println("修改之前的");
		singleLinkedList.list();

		//测试修改节点的代码
		HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟···");
		singleLinkedList.update(newHeroNode);
		
		System.out.println("修改之后的的链表情况");
		//显示链表
		singleLinkedList.list();
		
		
	}

}

//定义一个SingleLinkedList来管理我们的英雄
class SingleLinkedList{
	//先初始化一个头结点，一般上头结点不要动
	private HeroNode head = new HeroNode(0,"","");
	
	//添加节点到单向链表
	//思路，当不考虑编号顺序时
	//1 找到当前链表的最后节点
	//2,将最后这个节点的nex指向新节点
	public void add(HeroNode heroNode) {
		//因为head节点不能动，因此我们需要一个辅助遍历temo
		HeroNode temp = head;
		//遍历链表，找到最后
		while(true) {
			//找到链表的最后
			if(temp.next == null) {
				break;
			}
			//如果没有找到最后，将temp后移
			temp = temp.next;
		}
		//当退出while循环后，temp就指向链表的最后
		//将最后这个节点的next指向新的节点
		temp.next = heroNode;
	}
	
	//第二种方式添加英雄时，根据排名将英雄插入到指定位置
	//如果有这个排名，则添加失败，并给出提示
	public void addByOrder(HeroNode heroNode) {
		//因为头结点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
		//因为单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
		HeroNode temp = head;
		boolean flag = false;  //false标记添加的编号是否存在，默认为false
		while(true) {
			if(temp.next == null) { //说明此时temp处于链表的最后
				break;
			}
			if(temp.next.no > heroNode.no) {
				//此时位置找到，就在temp的后边插入
				break;
			}else if(temp.next.no == heroNode.no) 
			{
				//说明希望添加的heroNode的编号已然存在
				flag = true;  //说明编号存在
				break;
			}
			temp = temp.next;  //后移，变量当前链表
		}
		//判断flag的值
		if(flag) {//不能添加，说明编号存在
			System.out.printf("准备插入的英雄的编号%d，已经存在,无法添加\n",heroNode.no);
			
		}else {
			//插入到链表中，temp后边
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}
	//修该节点的信息，根据no编号来修改，即no编号不能更改
	//说明
	//1 根据newHeroNode的no来修改便可
	public void update(HeroNode newHeroNode) {
		//判断是否为空
		if(head.next == null) {
			System.out.println("链表为空。。。");
		}
		
		//找到需要修改的节点，根据no编号
		//定义一个辅助变量
		HeroNode temp = head.next;
		boolean flag = false;//表示是否找到该节点
		while(true) {
			if(temp == null) {
				break;//已经变量完链表
			}
			if(temp.no == newHeroNode.no) {
				//找到了
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//根据flag判断是否找到要修改的节点
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		}else {
			//没有找到
			System.out.printf("没有找到编号%d的节点，不能修改\n",newHeroNode.no);
		}
		
	}
	
	
	//显示链表【遍历】
	public void list() {
		//判读是否为空
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		//因为头结点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode  temp = head.next;
		while(true) {
			//判断是否是否链表最后
			if(temp == null) {
				break;
			}
			//输出节点的信息
			System.out.println(temp);
			//将next后移,如果不后移将进入死循环
			temp = temp.next ;
		}
	}
}


//定义一个heroNode ,每个HeroNode对象就是一个节点

class HeroNode{
	public int no;
	public String name;
	public String nickName;
	public HeroNode next;//指向下一个节点
	
	//构造器
	public HeroNode(int no, String name, String nickName) {
		super();
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}

	public HeroNode() {
		super();
	}
}

删除节点

从单链表中删除一个节点的思路

1. 删除节点之前，我们需要将有关节点先找到需要删除的这个节点的前一个节点temp
2. temp.next = temp.next.next;
3. 被删除的节点将不会有其他的指向，会被JVM垃圾回收机制回收。

代码如下：

public class SingleLinkedListDemo {
	public static void main(String[] args) {
		//测试
		//创建节点
		HeroNode hero1 = new HeroNode(1,"松江","及时雨");
		HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
		HeroNode hero3 = new HeroNode(3,"吴用","智多星");
		HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
		//创建链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		/*
		singleLinkedList.add(hero1);
		singleLinkedList.add(hero2);
		singleLinkedList.add(hero3);
		singleLinkedList.add(hero4);
		*/
		
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero2);
		
		System.out.println("修改之前的");
		singleLinkedList.list();

		//测试修改节点的代码
		HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟···");
		singleLinkedList.update(newHeroNode);
		
		System.out.println("修改之后的的链表情况");
		//显示链表
		singleLinkedList.list();
		
		
		//删除一个节点
		singleLinkedList.del(4);
		singleLinkedList.del(1);
		singleLinkedList.del(1);
		//删除后的链表情况
		System.out.println("删除后的链表情况。。。");
		singleLinkedList.list();
		
	}

}

//定义一个SingleLinkedList来管理我们的英雄
class SingleLinkedList{
	//先初始化一个头结点，一般上头结点不要动
	private HeroNode head = new HeroNode(0,"","");
	
	//添加节点到单向链表
	//思路，当不考虑编号顺序时
	//1 找到当前链表的最后节点
	//2,将最后这个节点的nex指向新节点
	public void add(HeroNode heroNode) {
		//因为head节点不能动，因此我们需要一个辅助遍历temo
		HeroNode temp = head;
		//遍历链表，找到最后
		while(true) {
			//找到链表的最后
			if(temp.next == null) {
				break;
			}
			//如果没有找到最后，将temp后移
			temp = temp.next;
		}
		//当退出while循环后，temp就指向链表的最后
		//将最后这个节点的next指向新的节点
		temp.next = heroNode;
	}
	
	//第二种方式添加英雄时，根据排名将英雄插入到指定位置
	//如果有这个排名，则添加失败，并给出提示
	public void addByOrder(HeroNode heroNode) {
		//因为头结点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
		//因为单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
		HeroNode temp = head;
		boolean flag = false;  //false标记添加的编号是否存在，默认为false
		while(true) {
			if(temp.next == null) { //说明此时temp处于链表的最后
				break;
			}
			if(temp.next.no > heroNode.no) {
				//此时位置找到，就在temp的后边插入
				break;
			}else if(temp.next.no == heroNode.no) 
			{
				//说明希望添加的heroNode的编号已然存在
				flag = true;  //说明编号存在
				break;
			}
			temp = temp.next;  //后移，变量当前链表
		}
		//判断flag的值
		if(flag) {//不能添加，说明编号存在
			System.out.printf("准备插入的英雄的编号%d，已经存在,无法添加\n",heroNode.no);
			
		}else {
			//插入到链表中，temp后边
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}
	//修该节点的信息，根据no编号来修改，即no编号不能更改
	//说明
	//1 根据newHeroNode的no来修改便可
	public void update(HeroNode newHeroNode) {
		//判断是否为空
		if(head.next == null) {
			System.out.println("链表为空。。。");
		}
		
		//找到需要修改的节点，根据no编号
		//定义一个辅助变量
		HeroNode temp = head.next;
		boolean flag = false;//表示是否找到该节点
		while(true) {
			if(temp == null) {
				break;//已经变量完链表
			}
			if(temp.no == newHeroNode.no) {
				//找到了
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//根据flag判断是否找到要修改的节点
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		}else {
			//没有找到
			System.out.printf("没有找到编号%d的节点，不能修改\n",newHeroNode.no);
		}
	}
	
	//删除节点
	//TODO 思路
	//1. head不动，故而我们需要一个temp辅助节点找到等待删除节点的前一个节点
	//2.我们在比较的时候，是temp.next.no和需要删除的节点的no比较
	public void del(int no) {
		HeroNode temp = head;
		boolean flag = false;//标志是否找到待删除节点的
		while(true) {
			if(temp.next == null) {//已经到链表的最后
				break;
			}
			if(temp.next.no == no) {
				//找到待删除节点的前一个节点temp
				flag = true;
				break;
			}
			temp = temp.next;//temp后移，遍历
		}
		//判断flag
		if(flag) {//找到
			//可以删除
			temp.next = temp.next.next;
		}else {
			System.out.printf("要删除的节点%d不存在\n",no);
		}
	}
	
	
	//显示链表【遍历】
	public void list() {
		//判读是否为空
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		//因为头结点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode  temp = head.next;
		while(true) {
			//判断是否是否链表最后
			if(temp == null) {
				break;
			}
			//输出节点的信息
			System.out.println(temp);
			//将next后移,如果不后移将进入死循环
			temp = temp.next ;
		}
	}
}


//定义一个heroNode ,每个HeroNode对象就是一个节点

class HeroNode{
	public int no;
	public String name;
	public String nickName;
	public HeroNode next;//指向下一个节点
	
	//构造器
	public HeroNode(int no, String name, String nickName) {
		super();
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}
	
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}
	
	public HeroNode() {
		super();
	}
}

链表面试题：

面试题，获取单链表的节点个数(如果是带头结点的链表，需求不统计头结点)

/**
	 * 
	 * @param head 链表的头节点
	 * @return 返回的就是有效节点的个数
	 */
	public static int getLength(HeroNode head) {
		if(head.next == null) { //空链表
			return 0;
		}
		int length = 0;
		//定义一个辅助的变量,这里我们没有统计头结点
		HeroNode cur = head.next;
		while(cur != null) {
			length ++ ;
			cur = cur.next; //遍历
		}
		return length;
	}
main:
//测试一下头节点的个数
		System.out.println("有效的节点个数为： "+getLength(singleLinkedList.getHead()));
		

查找单链表中的倒数第k个节点【新浪面试题】

//思路：
	/**
	 * 编写一个方法，接受head节点，同时接受一个index
	 * index表示倒数第index个节点
	 * 先将链表从头到尾遍历，得到链表的总的长度getLength
	 * 得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
	 * 如果找到了，则返回该节点，否则返回null
	 */
	public static HeroNode findLastIndexNode(HeroNode head,int index) 
	{
		//判断如果链表为空，则返回null
		if(head.next == null) {
			return null;
		}
		//第一个遍历得到的链表的长度的个数(节点个数)
		int size = getLength(head);
		//第二次遍历size-index位置，就是我们倒数的第k个节点
		//先做一个index的校验
		if(index <= 0 || index > size) {
			return null;
		}
		//定义给辅助变量 for循环定位倒数的index
		HeroNode cur = head.next;
		for(int i = 0; i < size - index; i++) {
			cur = cur.next;
		}
		return cur;
	}
main:
//测试一些看是否得到倒数第k个节点
		HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 1);
		System.out.println("res=" + res);

单链表的反转【腾讯面试，难度适中】

1. 先定义一个节点reverseHead = new HeroNodeHead的最前端。
2. 从头到尾便利原来的指针，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端。
3. 原来的链表head.next = reverseHead.next。

//将单链表反转
	public static void reverseList(HeroNode head) {
		//如果当前链表为空，或者只有一个节点，无需反转，直接返回就行。
		if(head.next == null || head.next.next == null) {
			return ;
		}
		//定义一个辅助的指针(变量)，帮助我们遍历原来的链表
		HeroNode cur = head.next;
		HeroNode next = null; //指向当前节点[cur]的下一节点
		HeroNode reverseHead = new HeroNode(0,"","");
		//遍历原来的链表，每遍历一个节点，就将其取出，并在新的链表reverseHead的最前端
		
		//TODO 思考
		while(cur != null) {
			next = cur.next; //先暂时保存当前节点的下一节点，因为后面需要使用
			cur.next = reverseHead.next; //将cur的下一个节点指向新的链表的最前端
			reverseHead.next = cur; //将cur链接到新的链表上
			cur = next; //让cur后移
		}
		//将head.next指向reverseHead.next，此时就实现单链表的反转
		head.next = reverseHead.next;
	}

main:
//测试一下单链表的反转功能
		System.out.println("此时这个时候是原先链表");
		singleLinkedList.list();
		
		//反转链表
		System.out.println("反转后的单链表");
		reverseList(singleLinkedList.getHead());
		singleLinkedList.list();

从尾到头打印单链表 【方式1，反向遍历，方式2：stack栈】

思路：

1. 上面的题要求就是逆序打印单链表。

2. 方式1：先将单链表进行反转，然后在遍历就行，但是这样会破坏原来的单链表的结构，不可取。

3. 方式2：可以利用栈这个数据结构，将各个节点压入栈中，然后利用栈的先进后出的特点，实现逆序打印的效果。此方式不会影响链表的结构。

   	// 从尾到头打印单链表
   	//使用方式2：也就是将链表中所有元素添加到栈中，然后通过栈将所有元素反转，利用栈的特点，实现逆序打印
   	public static void reversePrint(HeroNode head) {
   		if(head.next == null) {
   			return ; //空链表，不能打印
   		}
   		//创建要给的一个栈，将各个节点压入栈便可。
   		Stack<HeroNode> stack = new Stack<HeroNode>();
   		HeroNode cur = head.next;
   		//将链表的所有节点压入栈中
   		while(cur != null) {
   			stack.push(cur);
   			cur = cur.next; // cur后移，这样就可以压入下一个节点
   		}
   		//将栈中的节点进行打印，pop 出栈
   		while(stack.size() > 0 ) {
   			System.out.println(stack.pop());  //stack的特点是先进后出的特点
   		}
   	}
   
   main:
   System.out.println("逆序打印单链表,此时没有改变链表的结构。。。");
   		reversePrint(singleLinkedList.getHead());

合并两个有序的单链表，合并之后的链表仍然井然有序【习题】

单链表存在的问题：

1. 单链表不能实现自我删除，其查找的方向只能是一个方向而双向链表可以向前或者向后查找
2. 单向链表不能自我删除，需要靠辅助节点，而双向链表，可以自我删除，所以前面我们单链表删除时节点，总是找到temp的下一个节点来删除。

4.2 双向链表

双向链表：

所谓双向链表

通俗的讲就是可以从两端进行查找。

分析双向链表的遍历，添加，修改，删除的操作思路

1. 遍历的方式和单链表一样，只是可以向前查找，也可以向后查找。
2. 添加（默认添加搭配双向链表的最后）
   1. 先找到双向链表的最后这个节点
   2. temp.next = newHeroNode
   3. newHeroNode.pre = temp;
3. 修改的思路和原理的单向链表一样
4. 删除
   1. 因为是双向链表，因此我们可以实现自我删除某个节点
   2. 直接找到要删除的这个节点，比如temp
   3. temp.pre.next = temp.next;
   4. temp.next.pre = temp.pre;

代码实现：

public class DoubleLinkListDemo {
	//双向链表的测试
	public static void main(String[] args) {
		System.out.println("双向链表的测试：");
		//先创建节点
		HeroNode2 hero1 = new HeroNode2(1,"张三","黑脸麻瓜");
		HeroNode2 hero2 = new HeroNode2(2,"李四","红脸堇瓜");
		HeroNode2 hero3 = new HeroNode2(3,"王五","白脸冬瓜");
		HeroNode2 hero4 = new HeroNode2(4,"赵六","绿脸西瓜");

		DoubleLinkList doubleLinkList = new DoubleLinkList();
		doubleLinkList.add(hero1);
		doubleLinkList.add(hero2);
		doubleLinkList.add(hero3);
		doubleLinkList.add(hero4);

		//遍历
		doubleLinkList.list();
		//修改
		HeroNode2 newHeroNode = new HeroNode2(2,"得力","自研菲亚");
		doubleLinkList.update(newHeroNode);
		System.out.println("修改后的结果：");
		doubleLinkList.list();
		//删除
		doubleLinkList.del(2);
		System.out.println("删除后的结果：");
		doubleLinkList.list();
	
	}

}
//创建一个双向链表的类
class DoubleLinkList{
	//通单向链表一样,创建一个头节点，头结点不要动，不存放具体数据
	private HeroNode2 head = new HeroNode2(0,"","");

	public HeroNode2 getHead() {
		return head;
	}

	//遍历双向链表的方法和单向链表一样。
	//显示链表【遍历】
	public void list() {
		//判读是否为空
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		//因为头结点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode2  temp = head.next;
		while(true) {
			//判断是否是否链表最后
			if(temp == null) {
				break;
			}
			//输出节点的信息
			System.out.println(temp);
			//将next后移,如果不后移将进入死循环
			temp = temp.next ;
		}
	}

	//添加一个节点到双向链表的最后
	public void add(HeroNode2 heroNode) {
		//因为head节点不能动，因此我们需要一个辅助遍历temo
		HeroNode2 temp = head;
		//遍历链表，找到最后
		while(true) {
			//找到链表的最后
			if(temp.next == null) {
				break;
			}
			//如果没有找到最后，将temp后移
			temp = temp.next;
		}
		//当退出while循环后，temp就指向链表的最后
		//此时形成一个双向链表
		temp.next = heroNode;
		heroNode.pre = temp;
	}

	//修改一个节点的内容
	//双向链表的节点内容修改和单向链表几乎一样
	//只是节点的类型改成了HeroNode2
	public void update(HeroNode2 newHeroNode) {
		//判断是否为空
		if(head.next == null) {
			System.out.println("链表为空。。。");
		}

		//找到需要修改的节点，根据no编号
		//定义一个辅助变量
		HeroNode2 temp = head.next;
		boolean flag = false;//表示是否找到该节点
		while(true) {
			if(temp == null) {
				break;//已经变量完链表
			}
			if(temp.no == newHeroNode.no) {
				//找到了
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//根据flag判断是否找到要修改的节点
		if(flag) {
			temp.name = newHeroNode.name;
			temp.nickName = newHeroNode.nickName;
		}else {
			//没有找到
			System.out.printf("没有找到编号%d的节点，不能修改\n",newHeroNode.no);
		}
	}

	//从双向链表中删除一个节点
	//说明
	//1 对于双向链表，我们可以直接找到要删除的这个节点
	//2 找到后，自我删除即可
	public void del(int no) {
		//判断当前链表是否为空
		if(head.next == null) {
			System.out.println("链表为空，无法删除");
		}
		HeroNode2 temp = head.next; //辅助变量(指针)
		boolean flag = false;//标志是否找到待删除节点的
		while(true) {
			if(temp == null) {//已经到链表的最后
				break;
			}
			if(temp.no == no) {
				//找到待删除节点的前一个节点temp
				flag = true;
				break;
			}
			temp = temp.next;//temp后移，遍历
		}
		//判断flag
		if(flag) {//找到
			//可以删除
			//temp.next = temp.next.next; 【单向链表的删除方式】
			temp.pre.next = temp.next;
			//此时以下代码存在问题，如果是下一个节点，就不需要执行下边语句，否则将会产生空指针问题。

			if(temp.next != null) {
				temp.next.pre = temp.pre;
			}

		}else {
			System.out.printf("要删除的节点%d不存在\n",no);
		}
	}
}

class HeroNode2{
	public int no;
	public String name;
	public String nickName;
	public HeroNode2 next; //指向后一个节点，默认为null
	public HeroNode2 pre; //指向前一个节点,默认为null

	public HeroNode2(int no, String name, String nickName) {
		super();
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}

	public HeroNode2() {
		super();
	}

	@Override
	public String toString() {
		return "HeroNode2 [no=" + no + ", name=" + name + ", nickName=" + nickName 
				+ "]";
	}
}

习题：

双向链表的第二种添加方式，按照编号顺序（提示，按照单链表的顺序进行添加即可，稍作修改）;

4.3 单向环形链表：

约瑟夫问题：设编号为1,2,….n,的n个人围坐在一圈，约定编号为k(1<= k <=m)的人从1开始报数，数到从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

n = 5,即有5个人

k =1，从第一个人开始报数

m=2,数2下。

思路：

1. 先创建第一个节点，让first指向该节点，并形成环形
2. 后面当我们没创建一个新的节点，就将该节点加入到已有的环形链表即可。

遍历环形链表：

1. 先让一个辅助指针（变量） curBoy，指向first节点

2. 然后通过一个while循环该环形链表即可，curBoy.next == first;

3. 根据用户的输入，生成一个小孩出圈的顺序，事先应该指向环形链表的最后这个节点。

   ​ 补充：小孩报数之前，先让first和helper移动 k -1 次

4. 当小孩报数时，让first和helper指针同时移动m -1次

5. 这个时候就可以将first指向的小孩节点出圈；

   1. first = first.next
   2. helper.next =first;

   原来first指向的节点就没有任何引用，就会被垃圾回收机制回收

public class Josepfu {
	public static void main(String[] args) {
		//测试看构建环形队列和遍历是否正确
		CircleSinglelinkedList circleSinglelinkedList = new CircleSinglelinkedList();
		circleSinglelinkedList.addBoy(10); //加入5个小孩节点
		circleSinglelinkedList.showBoy();
		
		//测试小孩出圈是否正确
		circleSinglelinkedList.countBoy(1, 2, 10);
	}
}

//创建一个环形的单向链表
class CircleSinglelinkedList{
	//创建一个first节点，当前没有编号
	private Boy first = new Boy(-1);
	//添加小孩节点，构建一个环形的链表
	public void addBoy(int nums) {
		//nums 做一个数据校验
		if(nums < 1) {
			System.out.println("nums的值不正确");
			return;
		}
		Boy curBoy = null;// 辅助指针，帮助构建环形链表
		
		//使用for来创建我们的环形链表
		for(int i = 1; i <= nums; i++) {
			//根据编号创建小孩节点
			Boy boy = new Boy(i);
			//如果是第一个小孩
			if(i == 1) {
				first = boy;
				first.setNext(first); //构成循环
				curBoy = first; // 让curBoy指向第一个小孩
				
			}else {
				curBoy.setNext(boy);//
				boy.setNext(first);
				curBoy = boy;
			}
		}
	}
	//遍历当前环境
	public void showBoy() {
		//判断链表是否为空
		if(first == null) {
			System.out.println("没有任何小孩...");
			return ;
		}
		//因为first不能动，因此我们仍然使用一个辅助指针完成遍历
		Boy curBoy = first;
		while(true) {
			System.out.printf("小孩的编号 %d \n",curBoy.getNo());
			if(curBoy.getNext() == first) { //说明已经遍历完成
				break;
			}
			curBoy = curBoy.getNext(); //将curBoy后移
		}
	}
	
	//根据用户的输入，计算出小孩出圈的顺序
	/**
	 * 
	 * @param startNo 表示第几个小孩开始计数
	 * @param countNum 表示数多少下
	 * @param nums 表示最初有多少个小孩子在圈中
	 */
	public void countBoy(int startNo,int countNum, int nums) {
		//先对数据进行校验
		if(first == null || startNo < 1 || startNo > nums) {
			System.out.println("参数输入错误，请重写输入：");
			return;
		}
		//创建要给辅助指针，帮助完成小孩出圈
		Boy helper = first;
		//需求创建一个辅助指针(变量) helper，事先应该指向环形链表的最后这个节点
		while(true) {
			if(helper.getNext() == first) {
				break;
			}
			helper = helper.getNext();
		}
		//小孩报数前，先让first和helper移动 k - 1次
		for(int j = 0; j < startNo - 1; j++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		//当小孩报数的时候，让first和helper指针同时移动 m - 1次，然后出圈
		//这里是一个循环操作，知道圈中只有一个节点
		while(true) {
			if(helper == first) {
				//说明圈中只有一个节点
				break;
			}
			//让first和helper指针同时移动countNum - 1;
			for(int j = 0; j < countNum -1; j++ ) {
				first = first.getNext();
				helper = helper.getNext();
			}
			//这时first指向的节点，就是要出圈的小孩节点
			System.out.printf("小孩%d出圈\n",first.getNo());
			//此时将first指向的小孩节点出圈
			first = first.getNext();
			helper.setNext(first); //
		}
		System.out.printf("最后留在圈中的小孩编号%d\n",first.getNo());
	}
}
class Boy{
	private int no;//编号
	private Boy next; //指向下一个节点，默认为null
	
	public Boy(int no) {
		super();
		this.no = no;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public Boy getNext() {
		return next;
	}
	public void setNext(Boy next) {
		this.next = next;
	}
	@Override
	public String toString() {
		return "Boy [no=" + no + ", next=" + next + "]";
	}
}

5.栈

1. 栈的英文Stack
2. 栈是一种先入后出(FILO - First in Last Out)的有序列表
3. 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行特殊线性表。允许插入和删除的一端，为变化的一端称为栈顶（Top）,另一端为固定的一端，称为栈底（Bottom）;
4. 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最后放入的元素最后删除。

5. 入栈push,出栈pop。

   1. 子程序的调用：在跳往子程序前，会先加个下一个指令的地址存放到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
   2. 处理递归调用，所谓递归，就是方法自己调用自己本身。与子程序的调用类似，只是除了存储下一个指令的地址外，也将参数，区域变量等数据存入堆栈中。
   3. 表达式的转换[中缀表达式转后缀表达式]与求值。
   4. 二叉树的变量
   5. 图形的深度优先(depth-first)搜索法。

5.1 栈的模拟实现

实现栈的思路：

1. 使用数组来模拟栈
2. 定义一个top来模拟栈顶，初始化为 -1；
3. 入栈的操作，当有数据加入栈时，top++ ; stack[top] = data;
4. 出栈的操作，int value = stack[top]; top -- ;return value;

反正有错误，bug一直都有。

public class ArrayStackDemo {
	public static void main(String[] args) {
		//测试一下ArrayStack是否正确
		//先创建一个ArrayStack对象，表示栈
		ArrayStack stack = new ArrayStack(4);
		String key = "";
		boolean loop = true; //控制是否退出菜单
		Scanner sc = new Scanner(System.in);
		while(loop) {
			System.out.println("show：表示展示栈");
			System.out.println("exit：表示退出栈");
			System.out.println("push：表示添加数据到栈");
			System.out.println("pop：表示从栈取出数据");
			System.out.println("请输入你的操作");
			key = sc.next();
			switch(key) {
			case "show":
				stack.list();
				break;
			case "push":
				System.out.println("请输入一个数");
				int value = sc.nextInt();
				stack.push(value);
				break;
			case "pop":
				try {
					int res = stack.pop();
					System.out.printf("出栈的数据是%d\n",res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case "exit":
				sc.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println("程序退出了");
	}
}

//定义一个ArrayStack表示栈
class ArrayStack{
	private int maxSize;//栈的大小
	private int[] stack;//数组，数组模拟栈，数据就房子该数组
	private int top =-1; //top表示栈顶，初始化为-1;
	
	//构造器
	public ArrayStack(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	//堆满
	public boolean isFull() {
		return top == maxSize -1;
	}
	
	//栈空
	public boolean isEmpty() {
		return top == -1;
	}
	//入栈-push
	public void push(int value) {
		//先判断栈是否满
		if(isFull()) {
			System.out.println("栈满");
			return ;
		}
		top ++;
		stack[top] = value;
	}
	//出栈-pop,将栈顶的数据进行返回
	public int pop() {
		//先判断是否为空
		if(isEmpty()) {
			//抛出异常
			throw new RuntimeException("栈空，没有数据···");
		}
		int value = stack[top];
		top --;
		return value;
		
	}
	//显示栈的情况【遍历栈】，遍历是需要从栈顶开始显示数据
	public void list() {
		if(isEmpty()) {
			System.out.println("栈空，没有数据···");
			return;
		}
		//需要从栈顶开始显示数据
		for(int i = top; i >= 0 ; i--) {
			System.out.printf("stack[%d]=%d\n",i,stack[i]);
		}
	}
}

5.2 使用栈实现计算机

试题： 使用栈完成表达式7 2 2 - 5 + 1 - 5 + 3 - 4 =？

思路：

1. 通过一个index值(索引).来变量我们的表达式
2. 如果我们发现是一个数字就直接入栈
3. 如果发现扫描到的是一个符号，就分如下情况进行分析
   1. 如果发现当前符号为空，则直接入栈
   2. 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符。这个时候就需要从数栈中pop出两个数，在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符插入符号栈
   3. 如果当前符号栈中有操作符，就进行比较，如果当前操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，在从符号栈中pop一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈。
4. 当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行。
5. 最后在数栈只有一个数子，就是表达式的结果。

public class Calculator1 {
	public static void main(String[] args) {
		//根据前面老师思路，完成表达式的运算
		String expression = "3-2*1+1"; // //如何处理多位数的问题？
		//创建两个栈，数栈，一个符号栈
		ArrayStack2 numStack = new ArrayStack2(10);
		ArrayStack2 operStack = new ArrayStack2(10);
		//定义需要的相关变量
		int index = 0;//用于扫描
		int num1 = 0;
		int num2 = 0;
		int oper = 0;
		int res = 0;
		char ch = ' '; //将每次扫描得到char保存到ch
		String keepNum = ""; //用于拼接 多位数
		//开始while循环的扫描expression
		while(true) {
			//依次得到expression 的每一个字符
			ch = expression.substring(index, index+1).charAt(0);
			//判断ch是什么，然后做相应的处理
			if(operStack.isOper(ch)) {//如果是运算符
				//判断当前的符号栈是否为空
				if(!operStack.isEmpty()) {
					//如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
					//在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
					if(operStack.priority(ch) <= operStack.priority(operStack.peek())) {
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = numStack.cal(num1, num2, oper);
						//把运算的结果如数栈
						numStack.push(res);
						//然后将当前的操作符入符号栈
						operStack.push(ch);
					} else {
						//如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
						operStack.push(ch);
					}
				}else {
					//如果为空直接入符号栈..
					operStack.push(ch); // 1 + 3
				}
			} else { //如果是数，则直接入数栈

				//numStack.push(ch - 48); //? "1+3" '1' => 1
				//分析思路
				//1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
				//2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
				//3. 因此我们需要定义一个变量 字符串，用于拼接

				//处理多位数
				keepNum += ch;

				//如果ch已经是expression的最后一位，就直接入栈
				if (index == expression.length() - 1) {
					numStack.push(Integer.parseInt(keepNum));
				}else{
					//判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
					//注意是看后一位，不是index++
					if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
						//如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
						numStack.push(Integer.parseInt(keepNum));
						//重要的!!!!!!, keepNum清空
						keepNum = "";
					}
				}
			}
			//让index + 1, 并判断是否扫描到expression最后.
			index++;
			if (index >= expression.length()) {
				break;
			}
		}
		//当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
		while(true) {
			//如果符号栈为空，则计算到最后的结果, 数栈中只有一个数字【结果】
			if(operStack.isEmpty()) {
				break;
			}
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.cal(num1, num2, oper);
			numStack.push(res);//入栈
		}
		//将数栈的最后数，pop出，就是结果
		int res2 = numStack.pop();
		System.out.printf("表达式 %s = %d", expression, res2);
	}
}

//先创建一个栈,直接使用前面创建好
//定义一个 ArrayStack2 表示栈, 需要扩展功能
class ArrayStack3 {
	private int maxSize; // 栈的大小
	private int[] stack; // 数组，数组模拟栈，数据就放在该数组
	private int top = -1;// top表示栈顶，初始化为-1

	//构造器
	public ArrayStack3(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}

	//增加一个方法，可以返回当前栈顶的值, 但是不是真正的pop
	public int peek() {
		return stack[top];
	}

	//栈满
	public boolean isFull() {
		return top == maxSize - 1;
	}
	//栈空
	public boolean isEmpty() {
		return top == -1;
	}
	//入栈-push
	public void push(int value) {
		//先判断栈是否满
		if(isFull()) {
			System.out.println("栈满");
			return;
		}
		top++;
		stack[top] = value;
	}
	//出栈-pop, 将栈顶的数据返回
	public int pop() {
		//先判断栈是否空
		if(isEmpty()) {
			//抛出异常
			throw new RuntimeException("栈空，没有数据~");
		}
		int value = stack[top];
		top--;
		return value;
	}
	//显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
	public void list() {
		if(isEmpty()) {
			System.out.println("栈空，没有数据~~");
			return;
		}
		//需要从栈顶开始显示数据
		for(int i = top; i >= 0 ; i--) {
			System.out.printf("stack[%d]=%d\n", i, stack[i]);
		}
	}
	//返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示
	//数字越大，则优先级就越高.
	public int priority(int oper) {
		if(oper == '*' || oper == '/'){
			return 1;
		} else if (oper == '+' || oper == '-') {
			return 0;
		} else {
			return -1; // 假定目前的表达式只有 +, - , * , /
		}
	}
	//判断是不是一个运算符
	public boolean isOper(char val) {
		return val == '+' || val == '-' || val == '*' || val == '/';
	}
	//计算方法
	public int cal(int num1, int num2, int oper) {
		int res = 0; // res 用于存放计算的结果
		switch (oper) {
		case '+':
			res = num1 + num2;
			break;
		case '-':
			res = num2 - num1;// 注意顺序
			break;
		case '*':
			res = num1 * num2;
			break;
		case '/':
			res = num2 / num1;
			break;
		default:
			break;
		}
		return res;
	}
}

5.3 前缀、中缀、后缀表达式（逆波兰表达式）

从右往左扫描表达式，遇到数子时，将数字压入栈中，遇到运算符时，弹出栈顶的两个数，用运算符对他们做相应的计算。一般情况中缀表达式是我们人为确定的表达式，但是计算机无法识别，故而我们需要将中缀表达式调整为后缀表达式。

从左到右表达式最右端，最后运算得出的值即为表达式的结果。

​ * 思路：

 * 1.从左到右扫描，将3和4压入栈中
 * 2.遇到 + 运算符，因此弹出4和3(4为栈顶元素，3为次顶元素)，计算出3+4的值，得到7，在将7压入栈中
 * 3.将5入栈
 * 4.接下来是*运算符，因此弹出5和7，计算7*5=35，将35入栈。
 * 5.将6入栈
 * 6.最后是 - 运算符，计算出35 -6 的值，即29，由此得出最终结果

public class 逆波兰表达式 {
	public static void main(String[] args) {
		//先定义给逆波兰表达式
		//(3+4)*5-6 => 3 4 + 5 * 6 -
		//说明为了方便，逆波兰表达式的数字和符号使用空格隔开
		String suffixExpression = "15 4 + 5 * 6 -";
		//思路
		// 1. 先将 3 4 + 5 * 6 -  => 放到ArrayList中
		// 2 将 ArrayList 传递给一个方法，遍历ArrayList 配合栈完成计算
		List<String> rpnList = getListString(suffixExpression);
		System.out.println("逆波兰表达式：" + rpnList);
		int res = calculate(rpnList);
		System.out.println("计算的结果为：" + res);		
	}
	//将一个逆波兰表达式，依次将数据和运算符放到ArrayList中
	public static List<String> getListString(String suffixExpression){
		//将suffixExpression 分割
		String [] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for(String ele : split) {
			list.add(ele);
		}
		return list;
	}
	//完成对逆波兰表达式的运算。
	/**
	 * 思路：
	 * 1.从左到右扫描，将3和4压入栈中
	 * 2.遇到 + 运算符，因此弹出4和3(4为栈顶元素，3为次顶元素)，计算出3+4的值，得到7，在将7压入栈中
	 * 3.将5入栈
	 * 4.接下来是*运算符，因此弹出5和7，计算7*5=35，将35入栈。
	 * 5.将6入栈
	 * 6.最后是 - 运算符，计算出35 -6 的值，即29，由此得出最终结果
	 */
	public static int calculate(List<String> ls) {
		//创建给栈，只需要一个栈即可
		Stack<String> stack = new Stack();
		//遍历 ls
		for(String item : ls) {
			//这里使用正则表达式来读取数
			if(item.matches("\\d+")) { //匹配的是多位数
				//入栈
				stack.push(item);
			}else {
				//pop出两位数，并运算，再入栈
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.pop());
				int res = 0;
				if(item.equals("+")) {
					res = num1 + num2;
				}else if(item.equals("-")) {
					res = num1 - num2;
				}else if(item.equals("*")) {
					res = num1 * num2;
				}else if(item.equals("/")) {
					res = num1 / num2;
				}else {
					throw new RuntimeException("运算符有误");
				}
				//把res入栈
				stack.push("" + res);
			}
		}
		//最后留在stack中的数据是运算结果
		return Integer.parseInt(stack.pop());
	}
}

5.4 中缀表达式转换为后缀表达式

实际开发中，我们需要将中缀表达式转换为后缀表达式

中缀表达式转后缀表达式的思路步骤

1. 初始化两个栈，运算符s1和存储中间结果的栈s2
2. 从左到右扫描中缀表达式；
3. 遇到操作运算符时，将其压s2;
4. 遇到运算符时，比较其与s1栈顶运算符的优先级
   1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将次运算符入栈；
   2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1
   3. 否则将s1栈顶的运算符弹出并压入到s2中，再次转到（4-1）与s1中新的栈顶运算符相比较；
5. 遇到括号
   1. 如果是左括号“（”,则直接压入s1
   2. 如果是右括号“）”,则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃。
6. 重复步骤2至5，直到表达式的最右边
7. 将s1中剩余的运算符依次弹出并压入s2
8. 依次弹出s2中元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。

public class 逆波兰表达式 {
	public static void main(String[] args) {

		//先定义给逆波兰表达式
		//(3+4)*5-6 => 3 4 + 5 * 6 -
		//说明为了方便，逆波兰表达式的数字和符号使用空格隔开
		String suffixExpression = "15 4 + 5 * 6 -";
		//思路
		// 1. 先将 3 4 + 5 * 6 -  => 放到ArrayList中
		// 2 将 ArrayList 传递给一个方法，遍历ArrayList 配合栈完成计算

		List<String> rpnList = getListString(suffixExpression);
		System.out.println("逆波兰表达式：" + rpnList);

		int res = calculate(rpnList);
		System.out.println("计算的结果为：" + res);


		System.out.println("=========================以上是中缀表达式====================");
		//此时我们完成一个中缀表达式转成后缀表达式的功能
		//说明
		//1.  1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
		//2 因为直接对str进行操作，不方便，因此将1+((2+3)*4)-5 中缀表达式转换为对应的List
		// 即"1+((2+3)*4)-5" => ArrayList[1,+,(,(,2,+,3),*,4),-,5]
		//3 将 得到的中缀表达式对应的List =>后缀表达式对应的List
		//即ArrayList[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]=>ArrayList[1,2,3,+,4,*,+,5,-]

		String experssion = "1+((2+3)*4)-5";
		List<String> infixExpressionList = toInfixExpressionList(experssion);
		System.out.println("中缀表达式对应的List " + infixExpressionList);
		List<String> parseSuffixExpressionList = parseSuffixExpressionList(infixExpressionList);
		System.out.println("后缀表达式对应的List" + parseSuffixExpressionList);
		
		System.out.printf("expression=%d",calculate(parseSuffixExpressionList));

	}
	//	 将 得到的中缀表达式对应的List =>后缀表达式对应的List
	//即ArrayList[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]=>ArrayList[1,2,3,+,4,*,+,5,-]
	public static List<String> parseSuffixExpressionList(List<String> ls){
		//定义两个栈
		Stack<String> s1 = new Stack<String>(); //符号栈
		//说明：因为s2这个栈，在整个转换过程中，没有pop()操作，后面我们还需要逆序排序
		//因此这样比较麻烦，此时我们就不同Stack<String> 直接使用List<String> s2
		//Stack<String> s2  = new Stack<String>();//存储中间结果的栈S2
		List<String> s2 = new ArrayList<String>();//存储中间结果的List2
		//遍历ls
		for(String item : ls) {
			//如果是一个数，加入s2
			if(item.matches("\\d+")) {
				s2.add(item);
			}else if(item.equals("(")) {
				s1.push(item);
			}else if(item.equals(")")) {
				//如果是右括号")"，则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃
				while(!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				s1.pop();  //将（弹出s1栈，消除小括号
			}else {
				//当item的优先级小于栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，再次转到（4.1）与s1中新的栈顶运算符相比较
				while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
					s2.add(s1.pop());
					}
				//还需要将item压入栈
				s1.push(item);
				
			}
		}
		//将s1中剩余的运算符依次弹出并加入s2
		while(s1.size() != 0) {
			s2.add(s1.pop());
		}
		return s2;  //注意是因为存放到List，因此按顺序输出
	}

	//方法：将中缀表达式转换为对应的List
	/**
	 * 
	 * @param s
	 * @return
	 */
	public static List<String> toInfixExpressionList(String s){
		//定义一个List,存放中缀表达式 对应的内容
		List<String> ls = new ArrayList<String>();
		int i = 0; //这个是个指针，用于遍历中缀表达式字符串
		String str;//对多位数的拼接到一个字符，就放入到c
		char c; //每遍历到一个字符，就放入到c
		do {
			//如果c是一个非数字，则需要加入的ls中	
			if((c=s.charAt(i)) < 48 || (c=s.charAt(i))> 57){
				ls.add(""+c );
				i++;//i需要后移
			}else {
				//如果是一个数，需要考虑多位数问题
				str = "";//先将str置成"" '0'[48]-> '9'[57]
				while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
					str += c; //拼接
					i++;
				}
				ls.add(str);
			}
		}while(i < s.length());
		return ls;

	}

	//将一个逆波兰表达式，依次将数据和运算符放到ArrayList中
	public static List<String> getListString(String suffixExpression){
		//将suffixExpression 分割
		String [] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for(String ele : split) {
			list.add(ele);
		}
		return list;
	}

	//完成对逆波兰表达式的运算。
	/**
	 * 思路：
	 * 1.从左到右扫描，将3和4压入栈中
	 * 2.遇到 + 运算符，因此弹出4和3(4为栈顶元素，3为次顶元素)，计算出3+4的值，得到7，在将7压入栈中
	 * 3.将5入栈
	 * 4.接下来是*运算符，因此弹出5和7，计算7*5=35，将35入栈。
	 * 5.将6入栈
	 * 6.最后是 - 运算符，计算出35 -6 的值，即29，由此得出最终结果
	 */
	public static int calculate(List<String> ls) {
		//创建给栈，只需要一个栈即可
		Stack<String> stack = new Stack();
		//遍历 ls
		for(String item : ls) {
			//这里使用正则表达式来读取数
			if(item.matches("\\d+")) { //匹配的是多位数
				//入栈
				stack.push(item);
			}else {
				//pop出两位数，并运算，再入栈
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.pop());
				int res = 0;
				if(item.equals("+")) {
					res = num1 + num2;
				}else if(item.equals("-")) {
					res = num1 - num2;
				}else if(item.equals("*")) {
					res = num1 * num2;
				}else if(item.equals("/")) {
					res = num1 / num2;
				}else {
					throw new RuntimeException("运算符有误");
				}
				//把res入栈
				stack.push("" + res);
			}
		}
		//最后留在stack中的数据是运算结果
		return Integer.parseInt(stack.pop());
	}

}

//编写一个类来返回一个运算符对应的优先级
class Operation{
	private static int ADD = 1;
	private static int SUB = 1;
	private static int MUL = 2;
	private static int DIV = 2;

	//写一个方法，返回对应的优先级数字
	public static int getValue(String operation) {
		int result  = 0;
		switch(operation) {
		case "+":
			result = ADD;
			break;
		case "-":
			result = SUB;
			break;
		case "*":
			result = MUL;
			break;
		case "/":
			result = DIV;
			break;
		default:
			System.out.println("不存在该运算符");
			break;
		}
		return result;
	}
}

6.递归

1. 递归就是方法自己调用自己

2. 递归调用规则：

   1. 当程序执行到一个方法时，就会开辟一个独立的空间（栈）
   2. 方法的局部变量是独立的，不会相互影响，比如n变量
   3. 如果方法中使用的是引用类型变量(比如说数组)，就会共享该引用类型的数据
   4. 递归必须向退出递归的条件逼近，否则就是无限递归，出现栈溢出也就是StackOverFlowError。
   5. 当一个方法执行完毕，或者遇到return,就会返回，遵循谁调用，就将结果返回给谁，同时当方法执行完毕后返回时，该方法也就执行完毕。

6.1 使用递归解决迷宫问题：

public class MiGong {

	public static void main(String[] args) {
		//创建一个二维数组模拟迷宫
		//地图
		int [][] map = new int [8][7];
		//使用1表示墙
		//上下全是墙壁
		for(int i = 0; i < 7; i++) {
			map[0][i] = 1;
			map[7][i] = 1;
		}
		//左右全是墙壁
		for(int i = 0; i < 8; i++ ) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		map[3][1] = 1;
		map[3][2] = 1;

		//输出地图
		System.out.println("当前地图为：");
		for(int i = 0; i < 8 ; i ++) {
			for(int j = 0 ;j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		/*
		//使用递归回溯给小球找路
		setWay(map, 1, 1);
		//输出地图
		System.out.println("小球走过，并标识：");
		//输出新的地图，小球走过，并标识
		for(int i = 0; i < 8 ; i ++) {
			for(int j = 0 ;j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		 */
		
		//使用递归回溯给小球找路
		setWay1(map, 1, 1);
		//输出地图
		System.out.println("小球改变方式，并标识：");
		//输出新的地图，小球走过，并标识
		for(int i = 0; i < 8 ; i ++) {
			for(int j = 0 ;j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}


	}

	//使用递归回溯来给小球找路
	//说明：
	//1.如果小球能到map[6][5]的位置说明通路找到了。
	//当map[i][j]为0说明该点没有走过   当为1，表示墙;2 表示通路可以走，3表示该位置以及走过，但是走不通
	//在走迷宫的时候，需要确定一个策略(方法)下 ->右 ->上->左边，如果改点走不通，在回溯
	/**
	 * 
	 * @param map 表示传如的地图
	 * @param i 表示从哪个位置开始找，表示横坐标
	 * @param j 表示坐标，表示纵坐标
	 * @return 如果找到通路，就返回为true，否则返回false
	 */
	public static boolean setWay(int [][] map,int i , int j) {
		if(map[6][5] == 2) { //通路已经找到
			return true;
		}else {
			if(map[i][j] == 0) {  //如果当前这个点还没有走过
				//按照策略 下 -> 右 ->上->左走
				map[i][j] = 2;//假定该点是可以走通
				if(setWay(map,i+1,j)) { //往下走
					return true;
				}else if(setWay(map, i, j + 1)) {//向右
					return true;
				}else if(setWay(map, i - 1, j)) {//向上
					return true;

				}else if(setWay(map, i, j -1)) {  //向左走
					return true;
				}else {
					//说明该点走不通
					map[i][j] = 3;
					return false;

				}
			}else {
				//如果map[i][j] != 0,可能是 1,2,3
				return false;
			}
		}
	}


	//使用递归回溯来给小球找路
	//说明：
	//1.如果小球能到map[6][5]的位置说明通路找到了。
	//当map[i][j]为0说明该点没有走过   当为1，表示墙;2 表示通路可以走，3表示该位置以及走过，但是走不通
	//在走迷宫的时候，需要确定一个策略(方法)上 ->右 ->下->左边，如果改点走不通，在回溯
	/**
	 * 
	 * @param map 表示传如的地图
	 * @param i 表示从哪个位置开始找，表示横坐标
	 * @param j 表示坐标，表示纵坐标
	 * @return 如果找到通路，就返回为true，否则返回false
	 */
	public static boolean setWay1(int [][] map,int i , int j) {
		if(map[6][5] == 2) { //通路已经找到
			return true;
		}else {
			if(map[i][j] == 0) {  //如果当前这个点还没有走过
				//按照策略 上 -> 右 ->下->左走
				map[i][j] = 2;//假定该点是可以走通
				if(setWay1(map, i - 1,j)) { //往上走
					return true;
				}else if(setWay1(map, i, j + 1)) {//向右
					return true;
				}else if(setWay1(map, i + 1, j)) {//向下
					return true;

				}else if(setWay1(map, i, j -1)) {  //向左走
					return true;
				}else {
					//说明该点走不通
					map[i][j] = 3;
					return false;

				}
			}else {
				//如果map[i][j] != 0,可能是 1,2,3
				return false;
			}
		}
	}
}

6.2 八皇后问题递归思路和实现

八皇后问题算法思路分析：

1）第一个皇后先放第一行第一列

2）第二个皇后放在第二行第一列、然后判断是否OK，如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适

3）继续第三个皇后，还是第一列、第二列…….直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解

4）当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.

5）然后回头继续第一个皇后放第二列，后面继续循环执行1，2，3，4的步骤

说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题.

/**
 * 八皇后问题
 * 描述，要求每个皇后不在同一行，同一列，并且不在同一斜线上
 * @author 老胡
 * @date 2023年4月8日
 * Company 暂无
 * Email 2844135670@qq.com
 */
public class EightQueenQuestions {
	//定义一个max表示有多少个皇后
	int max = 8;
	//定义数组array,保存皇后位置放置的结果，比如arr={0,4,7,5,2,6,1,3}
	int [] array = new int[max];
	//定义一共有多少种解法
	static int count = 0 ; 
	public static void main(String[] args) {
		//测试一把，8皇后是否正确
		EightQueenQuestions queue8 = new EightQueenQuestions();
		System.out.println("哪行哪列代表数字,"
				+ "比如0 4 7 5 2 6 1 3，"
				+ "0表示第0行0列，"
				+"4表示第1行4列，"
				+"5表示第2行6列，"
				+"以此类推。");
		queue8.check(0);
		System.out.printf("共计有%d种解法",count);
	}
	
	//编写一个方法，放置第n个皇后
//注意到：check是每一次递归时，进入check中都有for(int i = 0; i < max ; i ++)，因此会有回溯
	private void check(int n) {
		if(n == max ) {
			//n = 8 ，其实是8个皇后就放好了
			print();
			return ;
		}
		//依次放入皇后，并判断是否冲突
		for(int i = 0 ; i < max; i ++) {//不冲突
			//先把当前这个皇后n,放到该行的第1列
			array[n] = i;
			if(judge(n)) {
				//接着放置n + 1皇后，即开始递归
				check(n+1); //如果有8个皇后，我们将调用8次
			}
			//如果是冲突就继续执行array[n] = i; 即将第n个皇后放置在本行的后移一个位置
		}
	}
	
	//查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
	/**
	 * @param n 表示第n个皇后
	 * @return
	 */
	private boolean judge(int n) {
		for(int i = 0 ; i < n ; i ++) {
			//说明一下
			//array[i] == array[n] 表示判断第n个皇后是否和前面的n-1个皇后在同一列
			//Math.abs(n-i) == Math.abs(array[n] -  array[i]) 表示判断第n个皇后时候和第i个皇后是否在同一斜线
			// n = 1 放置第2列 n = 1 array[1] = 1
			//Math.abs(1 - 0)  == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1;
			//判断是否在同一行，其实没有必要，因为每次都在递增
			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] -  array[i])) {
				return false;
			}
		}
		return true;
	}
	
	//写一个方法，可以将皇后摆放的位置输出
	private void print() {
		count ++;
		for(int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " " );
		}
		System.out.println();
		System.out.println("===============");
	}
}

7. 排序

7.1 8种基本排序

1. 排序也称为排序算法，排序是一组数据，按照指定的顺序进行排列的过程。
2. 排序的分类：
   1. 内部排序：将需要处理的所有数据都加载到内部存储器中进行排序
   2. 外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序
3. 常见的排序算法的分类：
   1. 内部排序：
      1. 插入排序：
         1. 直接插入排序
         2. 希尔排序
      2. 选择排序
         1. 简单选择排序
         2. 堆排序
      3. 交换排序
         1. 冒泡排序
         2. 快速排序
      4. 归并排序
      5. 基数排序
   2. 外部排序：内存和外存排序

7.2时间复杂度

算法的时间复杂度

一般我们度量一个程序执行时间的两种方法

1. 事后统计：这种方法可行，但是存在两个问题，一是想要对设计的算法的运行性能进行评测，需要实际运行该程序，二是所得时间的统计量依赖于计算机的硬件，软件等环境因素，这种方式要求在同一台计算机的相同状态下运行，才能比较那个算法速度更快。

2. 事前估算法：通过分析某个算法的时间复杂度来判断哪个算法更优。

1）一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用f(n）表示，若有某个辅助函数f(n），便得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O(f(n))，称O(f(n))为算法的渐进间复杂度，简称时间复杂度。

2）T（n）不同，但时间复杂度可能相同。如：T（n）=n^2+7n+6与T（n）=3n^2+2n+2它们的（n）不同，但时间复杂度相同，都为O(n^2)。

3）计算时间复杂度的方法：

• 用常数1代替运行时间中的所有加法常数 T(n) = n^2 + 7n + 6; =>T(n) = n^2 + 7n + 1

• 修改后的运行次数函数中，只保留最高阶项

  T(n) = n^2 + 7n + 1 => T(n) = n^2

• 去除最高阶项的系数T(n) =3n^2 =>O(n^2)

1. 常数阶O(1)

   int i = 1;
   int j = 2;
   ++ i;
   j++ ;
   int m = i + j;

1. 对数阶O(log2n)

   int i  = 1;
   while(i<n){
       i=i*2;
   }

1. 线性阶O(n)

   for(int i = 1; i <= n ; ++ i){
       j = i;
       j ++;
   } 

1. 线性对数阶O(nlog2n)

   for(int i = 1; m < n; m++ ){
       i = 1;
       while(i < n){
           i *= 2;
       }
   }

1. 平方阶O(n^2)

   for( int i = 0; i<= n; i ++){
       for(int j = 0 ; j <= n; j++){
           j = i;
           j ++ ;
       }
   }

1. 立方阶O(n^3)

   for(){
       for(){
           for(){
               
           }
       }
   }

1. k次方阶O(n^k)

   n层for(){
       for(){
           for(){
               ......
           }
       }
   }

1. 指数阶O(2^n)

依次往下时间复杂度增长

排序法	平均时间	最差情况	稳定度	空间复杂度	备注
冒泡	O(n^2)	O(n^2)	稳定	1	n小比较好
交换	O(n^2)	O(n^2)	不稳定	1	n小比较好
选择	O(n^2)	O(n^2)	不稳定	1	n小比较好
插入	O(n^2)	O(n^2)	稳定	1	大部分已排序的较好
基数	O(logRB)	O(logRB)	稳定	1	B是真数(0-9),R是基数（个十百）
shell	O(nlogn)	O(n^s) 1<s<2	不稳定	1	s是所选分组
快速	O(nlogn)	O(n^2)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时候较好

7.3 排序算法的实现与设计

7.3.1 冒泡排序

思想：

冒泡排序通过对排序序列从前往后(从下标较小的元素开始)，依次比较相邻元素的值，若发现逆序则交换，使值较大大元素慢慢从前往后移，就像水底气泡一样慢慢往上冒。

优化：

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

public class BubbleSort {
	public static void main(String[] args) {
		int arr[] = {3,9,-1,10,-2};
		//冒泡排序的过程

		//第一趟排序，就是将最大的数排在最后
		int temp = 0; //临时变量
		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]) {
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		System.out.println(Arrays.toString(arr));
		/*System.out.println("第一回排序后的数组");
		System.out.println(Arrays.toString(arr));

		//第二会排序，就是将第二大的数排在倒数第二位
		for(int j = 0 ; j < arr.length -1 - 1; j ++ ) {
			//如果前面这个数比后面的数更大，则交换
			if(arr[j]>arr[j+1]) {
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}

		}
		System.out.println("第二回排序后的数组");
		System.out.println(Arrays.toString(arr));

		//第三会排序，就是将第三大的数排在倒数第三位
		for(int j = 0 ; j < arr.length -1 - 2; j ++ ) {
			//如果前面这个数比后面的数更大，则交换
			if(arr[j]>arr[j+1]) {
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}

		}
		System.out.println("第三回排序后的数组");
		System.out.println(Arrays.toString(arr));
		//第四会排序，就是将第四大的数排在倒数第四位
		for(int j = 0 ; j < arr.length -1 - 3; j ++ ) {
			//如果前面这个数比后面的数更大，则交换
			if(arr[j]>arr[j+1]) {
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
		System.out.println("第四回排序后的数组");
		System.out.println(Arrays.toString(arr));
		 */
	}
}

---

冒泡排序的优化：

因为在排序过程中

public class BubbleSortOptimize {
	public static void main(String[] args) {
		/*
		int arr[] = {3,9,-1,10,-2};
		//冒泡排序的过程
		System.out.println("排序前的数组：");
		System.out.println(Arrays.toString(arr));
		System.out.println("=============================");
		*/
		
		//测试一下冒泡排序的速度O(n^2),给8万个数据，测试
		//创建要给80000个数据
		int [] arr = new int [80000];
		for(int i = 0 ; i < 80000 ; i ++) {
			arr[i] = (int)(Math.random() * 80000); //生成一个[0,80000)的随机数
		}
		Date date1 = new Date();
		//输出一个日期格式
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String dateStr = simpleDateFormat.format(date1);
		System.out.println("排序前的时间为=" + dateStr);
		
		
		
		//测试冒泡排序
		bubbleSort(arr);
		Date date2 = new Date();
		String dateStr2 = simpleDateFormat.format(date2);
		System.out.println("输出排序后的时间" + dateStr2);
		//System.out.println(Arrays.toString(arr));

	}

	//将前面冒泡排序算法封装成一个方法
	public static void bubbleSort(int [] arr) {
		//第一趟排序，就是将最大的数排在最后
		int temp = 0; //临时变量
		boolean flag = false; //定义一个标识符
		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]) {
					flag = true;
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
			//System.out.println("第"+(i+1)+"躺排序后的数组");
			//System.out.println(Arrays.toString(arr));
			if(flag == false) { //在一趟排序中一次交换都没发生过
				break;
			}else {
				flag = false; //重置flag！！！，进行下次判断
			}
		}
	}
}

核心代码：

int temp = 0; //临时变量
		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]) {
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		System.out.println(Arrays.toString(arr));

7.3.2 选择排序

选择排序也是一种简单的排序方式，其基本思想在于：第一次从数组(arr[0]-arr[n-1])中选择最小的值，然后与数组第一个元素(arr[0])进行交换，第二次从arr[1]-arr[n-1]中选取最小值，与arr[1]交换,……,知道将数组排序好，总共通过n-1次，得到一个按照排序码从小到大的有序序列。

思路：

原始数组 ： 101,34,119,1；

第一轮排序：1,34,119,101；

第二轮排序：1,34,119,101；

第三轮排序：1,34,101,119;

1. 选则排序一共有数组大小-1轮排序
2. 每1轮排序，又是一个循环，循环的规则。
   1. 假定当前这个数是最小数
   2. 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
   3. 当遍历到数组的最后，就得到本轮最小数和下标
   4. 交换数组的位置

public class SelectSort {
	public static void main(String[] args) {
		//int [] arr =  {101,34,119,1};
		//创建要给80000个数据
		int [] arr = new int [80000];
		for(int i = 0 ; i < 80000 ; i ++) {
			arr[i] = (int)(Math.random() * 80000); //生成一个[0,80000)的随机数
		}
		Date date1 = new Date();
		//输出一个日期格式
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String dateStr = simpleDateFormat.format(date1);
		System.out.println("排序前的时间为=" + dateStr);
		selectSort(arr);
		//测试冒泡排序
		Date date2 = new Date();
		String dateStr2 = simpleDateFormat.format(date2);
		System.out.println("输出排序后的时间" + dateStr2);
		/*
		System.out.println("排序前：");
		System.out.println(Arrays.toString(arr));
		selectSort(arr);
		System.out.println("排序后");
		System.out.println(Arrays.toString(arr));
		*/
	}
	//选择排序
	public static void selectSort(int [] arr) {
		//在推到的过程中，我们发现规律，因此可以使用for来解决
		for(int i = 0 ; i < arr.length ; i ++ ) {
			int minIndex = i;
			int min = arr[i];
			for(int j = i +1 ; j < arr.length ; j++) {
				if(min > arr[j]) { //说明假定的最小值，并非最小
					min = arr[j]; //重置min
					minIndex = j ;  //重置minInde
				}
			}
			if(minIndex != i) {
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
			/*
			 * System.out.println("第"+(i+1)+"轮后~~");
			 * System.out.println(Arrays.toString(arr));
			 */
		}
		//使用逐步推导，进行选择排序y
		/*
		 * 原始的数组： 101,34,119,1
		 * 第一轮排序：1,34,119,101；
		      第二轮排序：1,34,119,101；
		      第三轮排序：1,34,101,119;
		 * 
		 */
		/*	

		int minIndex = 0;
		int min = arr[0];
		for(int j = 0 +1 ; j < arr.length ; j++) {
			if(min > arr[j]) { //说明假定的最小值，并非最小
				min = arr[j]; //重置min
				minIndex = j ;  //重置minInde
			}
		}
		//此时将最小值，放在arr[0]中，此时就是交换
		if(minIndex != 0) {
			arr[minIndex] = arr[0];
			arr[0] = min;
		}
		System.out.println("第一轮后~~");
		System.out.println(Arrays.toString(arr));
		//第二轮
		minIndex = 1;
		min = arr[1];
		for(int j = 0 +1 ; j < arr.length ; j++) {
			if(min > arr[j]) { //说明假定的最小值，并非最小
				min = arr[j]; //重置min
				minIndex = j ;  //重置minInde
			}
		}
		//此时将最小值，放在arr[0]中，此时就是交换
		if(minIndex != 1) {
			arr[minIndex] = arr[1];
			arr[1] = min;
		}
		System.out.println("第二轮后~~");
		System.out.println(Arrays.toString(arr));
		//第三轮
		minIndex = 2;
		min = arr[2];
		for(int j = 0 +1 ; j < arr.length ; j++) {
			if(min > arr[j]) { //说明假定的最小值，并非最小
				min = arr[j]; //重置min
				minIndex = j ;  //重置minInde
			}
		}
		//此时将最小值，放在arr[0]中，此时就是交换
		if(minIndex != 2) {
			arr[minIndex] = arr[2];
			arr[2] = min;
		}
		System.out.println("第三轮后~~");
		System.out.println(Arrays.toString(arr));
		 */
	}
}

对比冒泡排序发现，选择排序速度比冒泡排序快。

核心代码层：

//选择排序
	public static void selectSort(int [] arr) {
		//在推到的过程中，我们发现规律，因此可以使用for来解决
		for(int i = 0 ; i < arr.length ; i ++ ) {
			int minIndex = i;
			int min = arr[i];
			for(int j = i +1 ; j < arr.length ; j++) {
				if(min > arr[j]) { //说明假定的最小值，并非最小
					min = arr[j]; //重置min
					minIndex = j ;  //重置minInde
				}
			}
			if(minIndex != i) {
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
        }

7.3.3 插入排序

插入排序的基本思想： 把n个待排序的元素看成一个有序表和一个无序表，开始时，有序表只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把他的排序码依次与有序元素的排序码进行比较，将他插入到有序表中的适当位置，使之成为新的有序表。

public class InsertSort {


	public static void main(String[] args) {
		int arr [] = {101,34,-1,119,1,89};
		insertSort(arr);
	}

	//插入排序
	public static void insertSort(int [] arr) {
		//使用for循环来将代码简化
		for(int i = 1 ; i < arr.length; i++) {
			//使用逐步推到的方式来
			//定义待插入的数据
			int insertVal = arr[i];
			int insertIndex = i - 1; //也就是arr[1]的前面这个数的下标

			//给insertVal找到插入的位置
			//说明 insertIndex >= 0 保证在给insertVal 找插入位置，不越界
			//insertVal < arr[insertIndex]待插入的数，还没有找到插入位置
			//需要将arr[insertIndex]
			while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
				arr[insertIndex +  1] = arr[insertIndex];
				insertIndex -- ;
			}
			//当退出while循环时候，说明插入的位置找到，insertIndex + 1;
			arr[insertIndex + 1] = insertVal;
			System.out.println("第"+i+"轮");
			System.out.println(Arrays.toString(arr));

		}

		/*
		//使用逐步推到的方式来
		//定义待插入的数据
		int insertVal = arr[1];
		int insertIndex = 1 - 1; //也就是arr[1]的前面这个数的下标

		//给insertVal找到插入的位置
		//说明 insertIndex >= 0 保证在给insertVal 找插入位置，不越界
		//insertVal < arr[insertIndex]待插入的数，还没有找到插入位置
		//需要将arr[insertIndex]
		while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex +  1] = arr[insertIndex];
			insertIndex -- ;
		}
		//当退出while循环时候，说明插入的位置找到，insertIndex + 1;
		arr[insertIndex + 1] = insertVal;
		System.out.println("第一轮");
		System.out.println(Arrays.toString(arr));

		//第二轮
		insertVal = arr[2];
		insertIndex = 2 -1;
		while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex +  1] = arr[insertIndex];
			insertIndex -- ;
		}
		arr[insertIndex + 1] = insertVal;
		System.out.println("第二轮");
		System.out.println(Arrays.toString(arr));

		//第二轮
		insertVal = arr[3];
		insertIndex = 3 -1;
		while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex +  1] = arr[insertIndex];
			insertIndex -- ;
		}
		arr[insertIndex + 1] = insertVal;
		System.out.println("第三轮");
		System.out.println(Arrays.toString(arr));
		 */
	}

}

核心代码：

//使用for循环来将代码简化
		for(int i = 1 ; i < arr.length; i++) {
			//使用逐步推到的方式来
			//定义待插入的数据
			int insertVal = arr[i];
			int insertIndex = i - 1; //也就是arr[1]的前面这个数的下标

			//给insertVal找到插入的位置
			//说明 insertIndex >= 0 保证在给insertVal 找插入位置，不越界
			//insertVal < arr[insertIndex]待插入的数，还没有找到插入位置
			//需要将arr[insertIndex]
			while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
				arr[insertIndex +  1] = arr[insertIndex];
				insertIndex -- ;
			}
			//当退出while循环时候，说明插入的位置找到，insertIndex + 1;
			if(insertIndex + 1 != i) {
				arr[insertIndex + 1] = insertVal;
			}
			//System.out.println("第"+i+"轮");
		//System.out.println(Arrays.toString(arr));
		}

通过时间比较，我们发现插入排序比选择排序时间更短，也就是说插入排序的效率高于选择排序。

缺点： 当插入的数是最小的数时，后移的次数明显增多，对效率有影响。

7.3.4 希尔排序

也是一种插入排序，其是在插入排序的一种优化。希尔排序是在插入排序上的缺点的一种解决办法，其完美解决了插入排序的缺点。

基本思想是对数组进行分组，按照分组排序后再排序

第一种思路：

public class ShellSort {

	public static void main(String[] args) {
		//希尔排序，对有序序列在插入时采用交换法，并测试排序速度
		//对有序序列在插入式采用移动法，并测试排序速度
		int []arr = {8,9,1,7,2,3,5,4,6,0};
		shellSort(arr);

	}
	//创建一个算法
	public static void shellSort(int [] arr) {
		//使用for循环简化代码
		//希尔排序的第一轮排序
		int temp = 0;
		int count =0;
		for(int gap = arr.length / 2; gap > 0 ;gap /=2 ) {
			//因为是第一轮排序，将n个数据分成gap组
			for(int i = gap; i < arr.length ; i++) {
				//遍历各组中所有的元素（共计gap组，每组n/gap个元素）步长为gap
				for(int j = i -gap ; j >= 0; j -= gap) {
					//如果当前元素大于加上步长后的那个元素，说明要交换
					if(arr[j] > arr[j + gap]) {
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
			System.out.println("希尔排序后的第"+(++count)+"轮结果为：" + Arrays.toString(arr));
		}


		/*
		//希尔排序的第一轮排序
		int temp;
		//因为是第一轮排序，将10个数据分成5组
		for(int i = 5; i < arr.length ; i++) {
			//遍历各组中所有的元素（共计5组，每组2个元素）步长为5
			for(int j = i -5 ; j >= 0; j -= 5) {
				//如果当前元素大于加上步长后的那个元素，说明要交换
				if(arr[j] > arr[j + 5]) {
					temp = arr[j];
					arr[j] = arr[j + 5];
					arr[j + 5] = temp;
				}
			}
		}
		System.out.println("希尔排序后的第一轮结果为：" + Arrays.toString(arr));


		//因为是第二轮排序，将10个数据分成5/2 = 2组
		for(int i = 2; i < arr.length ; i++) {
			//遍历各组中所有的元素（共计5组，每组2个元素）步长为5
			for(int j = i -2 ; j >= 0; j -= 2) {
				//如果当前元素大于加上步长后的那个元素，说明要交换
				if(arr[j] > arr[j + 2]) {
					temp = arr[j];
					arr[j] = arr[j + 2];
					arr[j + 2] = temp;
				}
			}
		}
		System.out.println("希尔排序后的第2轮结果为：" + Arrays.toString(arr));

		//因为是第三轮排序，将10个数据分成5/2/2 = 1组
		for(int i = 1; i < arr.length ; i++) {
			//遍历各组中所有的元素（共计5组，每组2个元素）步长为5
			for(int j = i -1 ; j >= 0; j -= 1) {
				//如果当前元素大于加上步长后的那个元素，说明要交换
				if(arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		System.out.println("希尔排序后的第3轮结果为：" + Arrays.toString(arr));
		 */
	}
}

第二种方式移位法：

//对希尔排序进行优化，我们使用位移法
	public static void shellSort2(int [] arr) {
		for(int gap = arr.length / 2 ; gap > 0 ; gap /= 2) {
			//从第gap个元素，逐个对其所在的组进行直接插入排序
			for(int i = gap ; i < arr.length; i++) {
				int j = i;
				int temp = arr[j];
				if(arr[j] < arr[j - gap]) {
					while(j - gap >= 0 && temp < arr[j - gap]) {
						//移动
						arr[j] = arr[j-gap];
						j -= gap;
					}
					//当退出while后，就给temp找到插入的位置
					arr[j] = temp;
				}
			}
		}
		//System.out.println(Arrays.toString(arr));
	}

使用移位法后，我们发现时间快了很多倍。

7.3.5 快速排序

快速排序是对冒泡排序的一种改进，其基本思想设计:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后按照次方法对这两部分数据分别进行快速排序，整个排序过程都可以递归进行，依此达到整个数据变成有序序列。

1. 快速排序，在序列中找一个基准数，然后将所有比基数小的放到基数的左边，所有比基数大的数放到基准数的右边。然后再对左右两个子序列重复这个过程，知道序列中所有的数都排序好。
2. 我的理解，找到一个中位数，比中位数小的放左边，比中位数大的放右边，直到所有的数都排好序为止。

快速排序的思路：

public class QuickSort {
	public static void main(String[] args) {

		//int [] arr = {-9,78,0,23,-567,70};
		int [] arr = new int [80000];
		for(int i = 0 ; i < 80000 ; i ++) {
			arr[i] = (int)(Math.random() * 80000); //生成一个[0,80000)的随机数
		}
		Date date1 = new Date();
		//输出一个日期格式
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String dateStr = simpleDateFormat.format(date1);
		System.out.println("排序前的时间为=" + dateStr);

		quickSort(arr, 0,arr.length - 1);
		//	shellSort(arr);
		//测试冒泡排序
		Date date2 = new Date();
		String dateStr2 = simpleDateFormat.format(date2);
		System.out.println("输出排序后的时间" + dateStr2);
		//System.out.println("arr:" + Arrays.toString(arr));
	}
	
	//快速排序总代码
	public static void quickSort(int [] arr ,int left,int right) {
		int l = left;//左下标
		int r = right ;// 右下标
		int temp = 0;
		// pivot 中值
		int pivot = arr[(left + right) /2 ];
		//while循环的目的是让pivot值小放到右边
		
		while(l < r) {
			while(arr[l] < pivot) {
				l += 1;
			}
			//在pivot的右边一直找，找到小于等于pivot值，才退出
			while(arr[r] > pivot) {
				r -= 1;
			}
			
			//如果 l >= r 说明pivot的左右两边的值,已经按照左边全部是
			//小于等于pivot值，右边全部是大于等于pivot的值
			if( l >= r) {
				break;
			}
			//交换
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
			
			//如果交换完后，发现这个arr[l] == pivot值相等 -- ，前移
			if(arr[l] == pivot) {
				r -= 1;
			}
			//如果交换完后，发现这个arr[r] == pivot值相等 l ++ ,后移
			if(arr[r] == pivot) {
				l += 1;
			}
		}
		
		//如果l == r,必须l++,r-- ,否则出现栈溢出
		if(l == r) {
			l += 1;
			r -= 1;
		}
		//向左递归
		if(left < r) {
			quickSort(arr, left, r);
		}
		//向右递归
		if(right > l) {
			quickSort(arr, l, right);
		}
	}
}

7.3.6 归并排序

归并排序是一种分治算法。

它的基本思想是将两个已经排序的序列合并成一个序列。具体来说，就是将一个序列分成两个子序列，然后对这两个子序列分别进行排序，最后将排好序的两个子序列合并成一个有序序列。

归并排序的过程可以分为两个步骤：分解和合并。

在分解步骤中，我们将序列不断分解成更小的子序列，直到每个子序列只包含一个元素。这时，每个子序列都是有序的。

在合并步骤中，我们将两个有序的子序列合并成一个有序的序列。具体来说，我们从两个子序列的开头开始比较它们的元素，每次取出较小的元素放入结果序列中，并将指向该元素的指针后移一位。重复这个过程，直到其中一个子序列为空。然后再将另一个子序列中剩余的元素全部放入结果序列中。

public class MergetSort {

	public static void main(String[] args) {
		System.out.println();
		int arr [] = {8,4,5,7,1,3,6,2};
		int temp [] = new int [arr.length] ;//归并排序需要一个额外空间
		mergeSort(arr, 0, arr.length - 1, temp);
		System.out.println("归并排序后 = " + Arrays.toString(arr));
	}
	
	//分+和的方法
	public static void mergeSort(int [] arr,int left, int right, int [] temp) {
		if(left < right) {
			int mid = (left + right) /2 ;//中间索引
			//向左递归进行分解
			mergeSort(arr, left, mid, temp);
			//向右递归进行分解
			mergeSort(arr, mid+1, right, temp);
			
			//到合并
			merget(arr, left, mid, right, temp);
		}
	}

	//合并的方法
	/**
	 * 
	 * @param arr 排序的原始数据
	 * @param left 左边有序序列的初始索引
	 * @param mid 中间索引
	 * @param right 右边索引
	 * @param temp 做中转的数组
	 */
	public static void merget(int [] arr, int left , int mid, int right, int [] temp) {
		int i = left; //初始化i,左边有序序列的初始索引
		int j = mid + 1;  //初始化j,右边有序序列的初始索引
		int t = 0; //指向temp数组的当前索引

		//（1）
		//先把左右两边的(有序)的数据按照规则填充到temp数组
		//直到左右两边的有序序列，有一边处理完毕为止
		while(i <= mid && j <= right) {  //继续
			//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
			//即将左边的当前元素，拷贝到temp数组
			//然后
			if(arr[i] <= arr[j]) {
				temp [t] = arr[i];
				t += 1;
				i += 1;
			}else {
				//反之，将右边的有序序列的当前元素，填充到temp数组
				temp[t] = arr[j];
				t += 1;
				j += 1;
			}
		}
		//(2) 把有剩余数据的一边的数据依次全部填充到temp
		while(i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
			temp[t]  = arr[i];
			t += 1;
			i += 1;
		}
		
		while(j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp中
			temp[t] = arr[j];
			t += 1;
			j += 1;
		}
		//(3)将temp数组的元素拷贝到arr
		//注意，并非每次都拷贝所有
		 t = 0;
		 int tempLeft = left;
		 System.out.println("tempLeft=" + tempLeft + ",right=" + right);
		 while(tempLeft <= right) {  
			 ////第一次合并tempLeft = 0,right = 1// tempLeft = 2  right = 3;// tL = 0,right = 3
			 //最后一次，tL = 0,right = 7;
			 arr[tempLeft] = temp[t];
			 t += 1;
			 tempLeft += 1;
		 }
	}
}

在经过时间测试我们发现其速度很快。

7.3.7 基数排序

1. 基数排序属于一种分配式排序，又称为桶子法，bin sort ，顾名思意，是通过键值的各个位的值，将要排序的元素分配到某些桶中，达到排序的作用。
2. 基数排序是一种稳定的排序，基数排序法的是效率高的稳定性排序法
3. 基数排序是桶排序的扩展
4. 基数排序起源于1887年赫尔曼.何乐礼发明的，将整数按照位数切割成不同的数字，然后按每个位数分别比较。
5. 所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

思路：

1. 使用基数排序，进行升序排序
2. 将每个元素的各位数取出，然后看这个数应该放在哪个对应的桶
3. 按照这个桶的顺序(一维数组的下标取出数据，放入原来数组）

public class RadixSort {

	public static void main(String[] args) {
		int[] arr={53, 3, 542, 748, 14, 214};
		bucketSort(arr);
	}

	public static void bucketSort(int[] arr){

		//定义一个一维数组，得到每个下标下的个数
		int[] bucketRecord=new int[10];
		//定义桶空间，初始化二维数组
		int[][] bucket=new int[arr.length][10];

		for (int i = 0; i < arr.length; i++) {
			//个位数的下标
			int sub=arr[i]/1%10;
			//给桶里面赋值
			bucket[bucketRecord[sub]][sub]=arr[i];
			//并且记录当前桶里面元素个数，加1
			bucketRecord[sub]= bucketRecord[sub]+1;
		}

		//排列各个桶，从第一列开始
		//第1轮
		int index=0;
		for (int i = 0; i < bucketRecord.length; i++) {
			if (bucketRecord[i]>0){
				for (int j = 0; j < bucketRecord[i]; j++) {
					arr[index++]=bucket[j][i];
					bucket[j][i]=0;
				}
				bucketRecord[i]=0;
			}
		}
		index=0;
		System.out.println("第1次排序后得到的结果："+ Arrays.toString(arr));


		//第2轮
		for (int i = 0; i < arr.length; i++) {
			//十位数的下标
			int sub=arr[i]/10%10;
			//给桶里面赋值
			bucket[bucketRecord[sub]][sub]=arr[i];
			//并且记录当前桶里面元素个数，加1
			bucketRecord[sub]= bucketRecord[sub]+1;
		}

		//排列各个桶，从第一列开始
		for (int i = 0; i < bucketRecord.length; i++) {
			if (bucketRecord[i]>0){
				for (int j = 0; j < bucketRecord[i]; j++) {
					arr[index++]=bucket[j][i];
					bucket[j][i]=0;
				}
				bucketRecord[i]=0;
			}
		}
		index=0;
		System.out.println("第2次排序后得到的结果："+ Arrays.toString(arr));


		//第3轮
		for (int i = 0; i < arr.length; i++) {
			//百位数的下标
			int sub=arr[i]/100%10;
			//给桶里面赋值
			bucket[bucketRecord[sub]][sub]=arr[i];
			//并且记录当前桶里面元素个数，加1
			bucketRecord[sub]= bucketRecord[sub]+1;
		}
		//排列各个桶，从第一列开始
		for (int i = 0; i < bucketRecord.length; i++) {
			if (bucketRecord[i]>0){
				for (int j = 0; j < bucketRecord[i]; j++) {
					arr[index++]=bucket[j][i];
					bucket[j][i]=0;
				}
				bucketRecord[i]=0;
			}
		}
		index=0;
		System.out.println("第3次排序后得到的结果："+ Arrays.toString(arr));

	}
}

使用for循环：

public class RadixSort2 {

	public static void main(String[] args) {
		int[] arr={53, 3, 542, 78, 14, 214,12,24,56,66,70};
		bucket(arr);
	}
	public static int maxLength(int[] arr){
		int max=arr[0];
		for (int i = 0; i < arr.length; i++) {
			if (max<arr[i]){
				max=arr[i];
			}
		}
		int length=(max+"").length();
		return length;
	}
	public static void bucket(int[] arr){
		//定义一个二维数组作为桶
		int[][] bucket=new int[arr.length][10];
		//每一个桶里面有几个元素
		int[] bucketRecord=new int[10];
		int length = maxLength(arr);
		for (int z = 0, n=1; z < length; n=n*10,z++) {
			for (int i = 0; i < arr.length; i++) {
				//个位数的下标
				int sub=arr[i]/n%10;
				//给桶里面赋值
				bucket[bucketRecord[sub]][sub]=arr[i];
				//并且记录当前桶里面元素个数，加1
				bucketRecord[sub]= bucketRecord[sub]+1;
			}
			//排列各个桶，从第一列开始
			int index=0;
			for (int i = 0; i < bucketRecord.length; i++) {
				if (bucketRecord[i]>0){
					for (int j = 0; j < bucketRecord[i]; j++) {
						arr[index++]=bucket[j][i];
						bucket[j][i]=0;
					}
					bucketRecord[i]=0;
				}
			}
			System.out.println("第"+z+"次排序后得到的结果："+Arrays.toString(arr));
		}
	}
}

基数排序是对传统桶排序的扩展，速度很快.

基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造OutOfMemoryError 基数排序时稳定的。

[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的] 有负数的数组

7.3.8 堆排序

8. 查找

8. 1 线性查找

很简单的查找方式,通过逐一比对，得到目标值，然后呢返回下标

public class SeqSearch{
    public static void main(String [] args){
        int [] arr = {7,3,4,11,434,55,0,23};
        int index = seqSearch(arr,55);
        if(index == -1){
			System.out.println("没有查找到");
        }else{
            System.out.println("找到了，下标为：" + index);
			System.out.println("此时输出的结果为：" + arr[index]);
        }
    }
    public static int seqSearch(int [] arr ,int value){
        for(int i = 0 ; i < arr.length ; i ++){
            if(value == arr[i]){
                return i;
            }
        }
        return -1;
    }
}

8.2 二分查找

1. 确定数中间的下标 mid = (right + left) / 2;
2. 然后让需要查找的数findValue和arr[mid] 比较
   1. findVal > arr[mid]，说明你要查找的数，在mid的右边，因此需要递归的向右查找
   2. 如果findVal < arr[mid],说明你要查找的数在mid的左边，因此需要递归的向左边查找
   3. findVal == arr[mid] 说明找到，就返回
3. 什么时候我们需要结束递归
   1. 找到就结束递归
   2. 递归完整整个数组，仍然没有找到findVal，也需要结束递归，当left > right就需要退出

public class BinarySearch {
	public static void main(String[] args) {
		int [] arr = {1,4,6,7,9,12,24,56,78};
		int resIndex = binarySearch(arr, 0, arr.length -1, 78);
		if(resIndex == -1) {
			System.out.println("此时没找到");
		}else {
			System.out.println("找到了，其下标为：" + resIndex);
		}
	}

	//二分查找算法
	/**
	 * 
	 * @param arr 数组
	 * @param left  左边的索引
	 * @param right 右边的索引
	 * @param findVal 要查询的值
	 * @return 如果杂找到就返回下标，如果没找到就返回-1
	 */
	public static int binarySearch(int [] arr ,int left,int right,int findVal) {
		
		//这里有个bug ，如果找不到值，那么递归就不会种植导致异常
		if(left > right) {
			return -1;
		}
		int mid = (left + right) / 2;
		int midVal = arr[mid];

		if(findVal > midVal) {  //向右递归
			return 	binarySearch(arr, mid +1, right, findVal);
		}else if(findVal < midVal){ //向左递归
			return 	binarySearch(arr, left, mid - 1, findVal);
		}else {
			return mid;
		}
	}
}

例题：

当一个有序数组中，有多个相同的数据时，如果将所有的数值都查找到，比如这里的1000

arr={12,23,34,44,45,46,46,46,47,48};

1. 在找到mid索引值，不要马上返回
2. 向mid索引值的左边扫描，将所有满足46的元素的下标，加入到arrayList
3. 向mid索引值的右边扫描，将所有满足46的元素的下标，加入到arrayList
4. 将ArrayList返回

public class BinarySearch {
	public static void main(String[] args) {
		int [] arr = {1,4,6,7,9,12,12,24,56,78};
		/*
		int resIndex = binarySearch(arr, 0, arr.length -1, 12);
		if(resIndex == -1) {
			System.out.println("此时没找到");
		}else {
			System.out.println("找到了，其下标为：" + resIndex);
		}
		*/
		BinarySearch2(arr, 0, arr.length -1, 12);
	}

	//二分查找算法
	/**
	 * 
	 * @param arr 数组
	 * @param left  左边的索引
	 * @param right 右边的索引
	 * @param findVal 要查询的值
	 * @return 如果杂找到就返回下标，如果没找到就返回-1
	 */
	public static int binarySearch(int [] arr ,int left,int right,int findVal) {

		//这里有个bug ，如果找不到值，那么递归就不会种植导致异常
		if(left > right) {
			return -1;
		}
		int mid = (left + right) / 2;
		int midVal = arr[mid];

		if(findVal > midVal) {  //向右递归
			return 	binarySearch(arr, mid +1, right, findVal);
		}else if(findVal < midVal){ //向左递归
			return 	binarySearch(arr, left, mid - 1, findVal);
		}else {
			return mid;
		}
	}

	//查找有多个相同数值的全部返回
	public static void BinarySearch2(int[] array,int left,int right, int value) {
		int mid = (left + right)/2;
		ArrayList<Integer> resIndexlist = new ArrayList<Integer>();


		if(value < array[mid]) {
			BinarySearch2(array,left,mid-1,value);
		}else if(value > array[mid]) {
			BinarySearch2(array,mid+1,right,value);
		}else {
			System.out.println(mid);

			int temp = mid -1;
			while(true) {
				if(temp < 0 ||array[temp]!= value) {
					break;
				}
				resIndexlist.add(temp);
				temp--;
			}
			resIndexlist.add(mid);

			temp = mid + 1;

			while(true) {
				if(array[temp]!= value || temp > array.length-1) {
					break;
				}
				resIndexlist.add(temp);
				temp++;

			}
			System.out.println(resIndexlist.toString());
		}
		//return resIndexlist.toString();
	}
}

8.3 差值查找

差值查找算法是在二分查找算法的基础上进行进一步进行的，其是在二分查找的基础上做了一点小小的优化，其基本思路是将原先公式1的方式变成公式2的方式，由于其取中点值的方式不同，造成其效率也不同，

$$公式1 ： mid = (low+hight)/2 = low + (hight - low)/2$$ $$公式2： mid = low + (high - low)*( (key - a[low]))/(a[hight] - a[low])$$

由于二分查找需要的条件将数组进行有序排列，故而再在此low代表左边，hight代表右边。

public class InterpolationSearch {
	public static void main(String[] args) {
		System.out.println("======== 差值查找分布略微不均匀数组 ===========");
		int arr[] = {1 ,4, 9, 15, 27, 49, 128, 157};
		int result = interpolationSearch(arr, 9, 0, arr.length - 1);
		System.out.println(result==-1?"未找到元素！":"查找成功！" + 9 + "对应下标： " + result);

		System.out.println("======== 差值查找分布均匀数组 ===========");
		int arr1[] = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ,20};
		int target = 8;
		int result1 = interpolationSearch(arr1, target, 0, arr1.length - 1);
		System.out.println(result1==-1?"未找到元素！":"查找成功！" + target + "对应下标： " + result1);

		System.out.println("======== 差值查找分布极其不均匀数组 ===========");
		int arr2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,99999};
		int target2 = 8;
		int result2 = interpolationSearch(arr2, target2, 0, arr2.length - 1);
		System.out.println(result2==-1?"未找到元素！":"查找成功！" + target2 + "对应下标： " + result2);

	}
	public static int interpolationSearch(int []arr, int target ,int left , int right) {
		if(target < arr[left] || target > arr[right] || left > right) {
			return -1;
		}

		int leftToTarget = target - arr[left];
		int rightToLeft = arr[right] - arr[left];
		int num = right - left;
		//中间的值的下标，注意此行与二分查找的区别
		int mid  = left + (leftToTarget * num) /rightToLeft;
		System.out.println("找了一次，中间值为：" + mid);
		//目标值小于中间值， 取得左侧
		if(arr[mid] > target && left <= right) {
			//递归左侧
			return interpolationSearch(arr, target, left, mid - 1);
		}else if(arr[mid] < target && left <= right) {
			//目标值大于中间的值取得右侧，并且递归
			return interpolationSearch(arr, target, mid + 1, right);
		}else {
			//不大于也不小于 则是等于
			return mid;
		}
	}
}

8.4 斐波那契查找

斐波那契查找算法，又被称为黄金分割法，是一种有序的查找算法。斐波那契数列被称为黄金分割数列，其数列如： 1,1,2,3,5,8,13,31…….。在数学上，其递归方法被定义为

$$F(n) = F(n-1) + F(n - 2) (n>=2).$$

该数列越往后的两个数的比值趋向于黄金比例0.618

斐波那契查找是在二分查找的基础上根据斐波那契数列进行分割。在斐波那契数列找一个等于大于查找表中元素个数的数F(n),将原查找表扩展为长度为F(n)(如果要补充元素，则补充重复最后一个元素，直到满足F(n)个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F(n-1)个元素，后半部分F(n-2)个元素，找出要查找的元素在那一部分并递归，直到找到。斐波那契查找的时间复杂度是O(log2n)。

1）由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1；

2）每一子段也可以用相同的方式分割；

3）若顺序表长度n不一定刚好等于F[k]-1，则需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可。

例如：原数组为{1,5,6,33,55,233,455}，长度n为7，若 F[ k ] - 1等于9，则应该将原数组扩容到9，多出的位置使用high位置的455填充，即得到{1,5,6,33,55,233,455,455,455}。

代码实现

（1）我们需要先递归实现斐波拉契数列，然后根据原数组的大小计算斐波拉契数列的k值；

（2）数组扩容条件是：增大 k 值（索引从 0 开始），使得数组长度刚好大于或者等于斐波那契数列中的 F[k]-1 ，我们定义临时数组 temp ，temp 后面为 0 的元素都按照数组最大元素值填充；

（3）mid值的确定：mid = low + f[k - 1] - 1 ，即用黄金分割点确定 mid 的值；

（4）value<temp[mid] ：目标值在黄金分割点的左边，因为全部元素 = 前面的元素 + 后边元素即 f[k] = f[k-1] + f[k-2]，又前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]，即下次循环有mid=low+f[k-1-1]+1，即需要k-=1；

value> temp[mid] ：目标值在黄金分割点的右边。因为全部元素 = 前面的元素 + 后边元素即 f[k] = f[k-1] + f[k-2]，又前面有 f[k-2]个元素,所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]，即下次循环有mid=low+f[k-1-2]+1，即需要k-=2；

value== temp[mid] ：找到目标值，因为数组经历过扩容，后面的值其实有些是多余的，mid 可能会越界（相对于原数组来说）则有： 1）mid <= high ：证明 mid 索引在原数组中，返回 mid； 2）mid > high 时，证明 mid 索引已经越界（相对于原数组来说），返回 high；

（5）若没有找到则返回-1。

public class FibonacciSearch {
	
	public static void main(String[] args) {
		int arr[] = {1,5,6,33,55,233,455};
		Arrays.sort(arr); //既然是二分查找衍生出来的，那么就需要先对数组排序，无论数组是否排好序，这样做总共是一种方式
		int value = 55;//要查找的值
		int temp = fibonacciSearch(arr, value);
		System.out.println(temp == -1 ? "没找到你所要的值，可能你要查找的值并不在斐波那契数列之中,你要查找的值为:"+value :"您查找的值为"+value+"其下标为"+temp );
	}
	
	public static final int maxSize = 20; //斐波那契数列的大小
	
	public static int [] fibonacci() { //构建一个斐波那契数列
		int[] fib = new int [maxSize];
		fib[0] = 1;
		fib[1] = 1;
		for(int i = 2; i < maxSize ; i++ ) {
			fib[i] = fib[i - 1] + fib [i -2];
		}
		return fib;
	}
	
	public static int fibonacciSearch(int [] arr ,int value ) {
		int low = 0; //指针low表示待查元素所在范围的下界，下界索引从0开始
		int high = arr.length - 1 ; //指针high表示待查元素所在范围的上界
		int k = 0 ;// 表示斐波那契分割数值的下标
		int mid = 0;
		int fib[] = fibonacci(); //获取到斐波那契数列
		
		while(high > fib[k] - 1) {//获取到斐波那契分割数值的下标
			k ++;
		}
		//因为f[k]值，可能大于a的长度，因此我们需要使用Arrays.copyOf方法，构造一个新的数组，并指向temp[]
		int [] temp = Arrays.copyOf(arr, fib[k]);
		for(int i = high + 1; i < temp.length ; i++ ) {
			//使用arr数组最后的数填充temp
			temp[i] = arr[high];
		}
		
		while(low < high) {
			mid = low + fib[k - 1] -1; //斐波那契中值公式
			if(value < temp[mid]) {
				//关键子值小于中间值，应该向左扫描即使high = mid - 1
				high = mid - 1;
				k -= 1;
			}else if(value > temp[mid]) { //关键字值大于中间值，应该向右扫描，即使low = mid + 1
				low = mid + 1;
				k -= 2;
			}else { //找到时需要返回哪个下标
				if(mid <= high) { //证明mid索引在原数组中，返回mid
					return mid;
				}else {
					//证明mid索引已经越界（相对于原数组来说），返回high
					return high;
				}
			}
		}
		return - 1; //没有找到即返回 - 1
	}
}