数据结构简要"/>
数据结构简要
目录
一、算法
1、数据结构
1、数据结构基本操作
2、数据结构的逻辑结构
3、数据结构的物理结构【存储】
4、存储方式
2、算法
二、动态数组
1、数组
2、线性表的实现
创建ArrayList类实现List接口
3、栈的实现
栈的一般操作——与线性表相似
2）栈实现中缀表达式
3)双端栈
4、队列
队列的基本操作
优化队列【循环队列】
三、动态链表
1、单向链表的实现
单向链表的基本操作
2、单向循环链表
3、双向链表
四、分治回溯
1.算法
2、递归
3、分治算法
三个操作
四个条件
4、回溯算法
五、查找算法
1、顺序查找算法
2、二分查找
3、插值查找
六、排序算法
1、比较类排序比较
2、非比较类排序
3、相关概念
4、一些具体排序
冒泡排序
插入排序
希尔排序
归并排序
堆排序
快速排序
计数排序
桶排序
一、算法
程序 = 数据结构 + 算法
1、数据结构
1、数据结构基本操作
数据之间的关系，将离散的数据规整划一
将数据间的关系实现并储存到计算机中
基于关系对数据进行操作（增删改查）
2、数据结构的逻辑结构
线性结构——数据元素一一对应
树形结构——数据元素一对多的层次关系
图形结构——数据元素多对多关系
3、数据结构的物理结构【存储】
顺序存储结构——开辟一组连续的空间【常用数组】
链式存储结构——开辟一组随机的空间存储数据【常用节点】
4、存储方式
线性结构——数组
树形结构——数组（按顺序进行存储，对于没有的数据以空格代替）
【LiftChild = 2*parent +1;RightChild = 2*parent + 2; parent = (Child - 1)/2】——二叉树
图形结构——顺序存储【矩阵】（1代表直连，0代表未直连）
——链式存储【邻接表】（直连的数据连接在数据后）
2、算法
1）算法——解决特定问题求解步骤
一个程序的运行时间主要依赖于算法的好坏和问题的输入规模（数据量的多少）
2）算法时间复杂度
常数阶o(1)——无循环，无递归。语文题输入规模N无关、逐行执行的代码。
线性阶o(n)——与输入规模有关，主要是一层循环代码，多个一层循环可以并列但不能包含。
线性阶o(n+m)——有两个数据输入规模
平方阶o(n^2)——与问题输入规模有关，主要为二层嵌套循环代码。
平方阶o(n*m)——两种数据规模输入。
对数阶o(log^n)——与问题输入规模有关，主要是一层循环迭代或递归代码；
时间复杂度简单计算方法【忽略常数，只保留最高项，且忽略最高项的系数】
二、动态数组
1、数组
1）数组的长度一旦确定则不可更改
2）数组只能存储同一类型的数据
3）数组中每个存储空间的地址是连续且相等的
4）数组提供角标的方式来访问元素
动态数组就是顺序存储结构具体实现的核心思想
2、线性表的实现
线性表——领个货多个元素的有限序列
除第1个a1以外，其他元素都有唯一直接前驱。
除第n个an以外，其他元素都有唯一直接后继
n表示线性长度，n=0时为空表。
1）线性表的实现arrayList
ArrayList是线性结构顺序的存储方式的具体实现。
创建ArrayList类实现List接口
public void add(E element);//在末尾添加元素public void add(int index,E element);//在角标为index的位置添加元素【插入】public void remove(E element);//删除指定元素public E remove(int index);//删除指定角标元素bong返回public E get(int index,E element);//获取角标处元素public E set(int index,E element);//修改角标处元素public int size();//获取元素个数public int indexOf(E element);//获取元素下标public boolean contains(E element);//查找元素是否在表里public boolean isEmpty();//表是否为空public void clear();//清空public void sort(Comparator<E> C);//排序,COMPARATOR是比较器，比较元素大小public List<E> subList(int formindex,int toindex);//获取从from到同的一段线性表
定义相关成员属性和构造函数
public class ArrayList<E> implements List {private static int DEFAULT_CAPACITY = 10;//在创建data时指定长度private E[] data;//线性表的我储存容器，data.length为最大容量private int size;//线性表的有效个数。且新元素默认在尾部添加角标public ArrayList(){/* data = (E[])new Object[DEFAULT_CAPACITY];//data<object,强转为一维数组size = 0;//设置个数为0*/this(DEFAULT_CAPACITY);//由于两个过程相同，可在无参中调用有参，传入指定容量}public ArrayList(int capacity){//设置一个指定容量为capaci的线性表if (capacity < 0){throw new IllegalArgumentException("参数必须大于0");}data = (E[])new Object[DEFAULT_CAPACITY];//data<object,强转为一维数组size = 0;}public ArrayList(E[] arr){//将一维数组传入线性表//data = arr 【data不能直接引用外部传入的数组arr；否则修改外部arr是会引起ArrayList内部的问题if(arr == null){throw new IllegalArgumentException("数组不能为空")；}data = (E[])new Object[arr.length];for(int i=0;i<arr.length;i++){size = arr.length;data[i]=arr[i];}}
数组的扩容
先创建一个长度位原数组两倍的数组，再把原数组数据复制。当i=size时，让data指向新数组。
@Overridepublic void add(E element) {add(size,element);}@Overridepublic void add(int index, E element) {//index的范围[0,size]if(index < 0 || index > size ){throw new IndexOutOfBoundsException("角标越界");}if(size >= data.length){size(data.length*2);//给袁术组扩容2倍}//先元素后移在添加for(int i = size-1;i>=index;i--) {data[i+1]=data[i];}data[index] = element;//在index位置添加elementsize ++;}private void size(int newlength) {//创建一个新数组,长度是原来的两倍E[] newData = (E[])new Object[newlength];//复制原来数组的数据for (int i=0;i<size;i++){newData[i] = data[i];}data = newData;//data指向新数组}数组的缩容
因为扩容与缩容，size总会在新长度的中间位置，所以可以共用一个size操作
@Overridepublic void remove(E element) {int index =indexOf(element);if(index != -1){//判断元素是否存在，如果存在，则删除remove(index);}}public E remove(int index) {//删除元素并返回if(index < 0 || index >=size){throw new IndexOutOfBoundsException("remove index pout of bound");}//先删除，在缩容E ret = data[index];for(int i=index +1;i<size;i++){data[i-1] = data[i];}size --;//缩容不能无限缩小，可以设置为 DEFAULT_CAPACITYif(size == data.length/4 && data.length >= DEFAULT_CAPACITY){size(data.length/2);}return ret;}@Overridepublic int indexOf(E element) {//index of 在线性表中查找指定元素的角标并返回//从做往右，找到第一次出现的那个for(int i= 0;i<size;i++){if(element.equals(data[i])){//判断的元素有可能是对象。return i;}}return -1;}对已知角标的数组进行修改
//获取角标处元素并返回原数public E get(int index, E element) {if(index < 0 ||index >size) {throw new IndexOutOfBoundsException("set index out of bounds");}return data[index];}@Override//修改角标处元素public E set(int index, E element) {if(index < 0 ||index >size){throw new IndexOutOfBoundsException("set index out of bounds");}E ret =data[index];data[index]=element;return ret;}获取线性表的长度和容量
@Overridepublic int size() {return size;}//获取线性表的容量public int getCapacity(){return data.length;}@Overridepublic int indexOf(E element) {//index of 在线性表中查找指定元素的角标并返回//从做往右，找到第一次出现的那个for(int i= 0;i<size;i++){if(element.equals(data[i])){//判断的元素有可能是对象。return i;}}return -1;}表的其他操作
@Override//查找元素是否在表里public boolean contains(E element) {return indexOf(element) !=-1;}@Override//表是否为空public boolean isEmpty() {return size == 0;}@Override//清空public void clear() {data = (E[])new Object[DEFAULT_CAPACITY];size = 0;}对表的元素进行排序
@Override//排序,COMPARATOR是比较器，比较元素大小public void sort(Comparator<E> C) {if(C ==null){throw new IllegalArgumentException("Comparator can not be null");}int j=0;E e =null;for(int i=1;i< size;i++){e = data[i];//使用e暂存i上的数字进行比较for(j =i;j>0&&Cpare(data[j-i],e)>0;j++){//j>0并且j 的左边有数字，用compare进行比较。data[j]=data[j-1];}data[j] = e;}}获取某一段长度
@Override//获取从from到同的一段线性表public List<E> subList(int formindex, int toindex) {//保证0<fromindex<=toindex<sizeif(formindex<0){throw new IndexOutOfBoundsException("fromindex must >0");}if(formindex>toindex){throw new IndexOutOfBoundsException("fromindex must <= toindex");}if(toindex >size){throw new IndexOutOfBoundsException("toindex must <size");}ArrayList<E> sublist = new ArrayList<E>(10);//创建一个新线性表，可规定容量for(int i = formindex;i<=toindex;i++){sublist.add(data[i]);//调用add，直接传输数据}return sublist;}比较两个线性表是否相等
//比较两个线性表是否想的呢，长度内容public boolean equles(Object obj){//比较的是自己if(this == obj){return true;}//判断obj是否为空if(obj == null){return false;}//.判断obj和arraylist是否为同一个类型if(getClass() != obj.getClass() ){return false;}//比较内容ArrayList other =(ArrayList) obj;//比较长度if(size !=other.size){return false;}//比较数组内容return Arrays.equals(data,other.data);}
打印字符串
public String toString(){//打印对象时打印字符串样式//ArrayList:10/30[xxxxxxxxx]——10：有效元素个数；30——总长度StringBuilder sb =new StringBuilder(String.format("ArrayList:%d/%d[",size,data.length));if(isEmpty()){//判断是否为空sb.append("]");//如果是空直接输出[].有效元素为0；0/10}else {for(int i=0;i<size;i++){sb.append(data[i]);//添加数字//最有一位数字后+"]",其余数字后+","if(i != size -1){sb.append(",");}else {sb.append("]");}}}return sb.toString();}获取ArrayList的迭代器：用foreach遍历线性表
//获取ArrayList的迭代器：用foreach遍历线性表@Overridepublic Iterator<E> iterator() {return new ArrayListInterator();}class ArrayListInterator implements Iterator<E>{public int cur=0;@Override//判断之后是否有元素public boolean hasNext() {return cur < size;}@Override//先把元素返回在后移public E next() {return data[cur++];}}
3、栈的实现
栈限定仅在表尾进行插入和删除操作的线性表
把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）【在表尾操作，时间复杂度为o（1）.
不含任何数据元素的栈称为空栈。
栈又称为先进后出(last in First Out)的线性表
栈本身是一个线性表，其数据元素具有线性关系，只不过是一种特殊的线性表。栈接口的定义
public interface Stack<E> extends Iterable<E> {public int size();public boolean isEmpty();public void push(E element);public E pop();public E peek();public void clear();
}栈的一般操作——与线性表相似
import 数据结构接口.Stack;import java.util.Iterator;public class ArrayStack<E> implements Stack<E> {//底层用ArrayList实现栈private ArrayList<E> list;//创建一个默认容量栈public ArrayStack(){list = new ArrayList<E>();}//创建一个制定容量栈public ArrayStack(int capacity){list = new ArrayList<>(capacity);}@Overridepublic int size() {//有效元素个数return list.size();}@Overridepublic boolean isEmpty() {//是否为空return list.isEmpty();}@Overridepublic void push(E element) {//进栈list.add(element);}@Overridepublic E pop() {//出栈return list.remove(list.size()-1);}@Overridepublic E peek() {//查看栈顶元素return list.get(list.size()-1);}@Overridepublic void clear() {//清空list.clear();}@Overridepublic Iterator<E> iterator() {return list.iterator();}@Overridepublic String toString() {//ArrayList:10/30[xxxxxxxxx]——10：有效元素个数；30——总长度StringBuilder sb =new StringBuilder(String.format("ArrayList:%d/%d[",size(),list.getCapacity()));if(isEmpty()){//判断是否为空sb.append("]");//如果是空直接输出[].有效元素为0；0/10}else {for(int i=0;i<size();i++){sb.append(list.get(i));//添加数字//最有一位数字后+"]",其余数字后+","if(i != size() -1){sb.append(",");}else {sb.append("]");}}}return sb.toString();}
}2）栈实现中缀表达式
通用的算术逻辑公式表示方法、操作符是以中缀形式处于操作数的中间
如果遇见数字——直接进数字栈
遇见操作符——（1）空——直接进
（2）栈顶为“（”——直接进
（3）有其他操作符
当前操作符优先级大——直接进
当前操作符优先级等于或小于——将占中优先级大的先进行处理，知道栈空或者完全小于进栈的优先级。
public class infixCacular {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("请输入一串字符");String expression =scanner.nextLine();//格式化表达式expression = insertBlanks(expression);//以#为分隔符进行切割String[] tokens = expression.split("#");//测试，遍历输出加#后的字符【注意空字符串】for(int i =0;i<tokens.length;i++){System.out.print(tokens[i]+",");}//建立一个数字栈ArrayStack<Integer> numberStack= new ArrayStack<>();//建立一个字符栈ArrayStack<Character> operatorStack = new ArrayStack<>();//遍历for(String token:tokens){//过滤空字符串if(token.length() == 0){continue;}else if(token.charAt(0) == '+' || token.charAt(0) == '-'){//如果遇到了+或—，则需要一直运算while (!operatorStack.isEmpty() &&(operatorStack.peek()=='+'||operatorStack.peek()=='-'||operatorStack.peek()=='*'||operatorStack.peek()=='/')){processAnoperator (numberStack,operatorStack);}operatorStack.push(token.charAt(0));}else if(token.charAt(0) == '*' ||token.charAt(0) == '/' ){//*和/的时候，优先级高 的只有*/while (!operatorStack.isEmpty()&&(operatorStack.peek()=='*'||operatorStack.peek()=='/')){processAnoperator (numberStack,operatorStack);}operatorStack.push(token.charAt(0));}else if(token.charAt(0)=='('){operatorStack.push('(');} else if(token.charAt(0)==')'){//）是，必须左括号之前的全部运算while (operatorStack.peek() !='('){processAnoperator (numberStack,operatorStack);}operatorStack.pop();}else{//只剩num，直接进数字栈numberStack.push(new Integer(token));//把字符串解析成数字}}//将最后剩余的数字进行运算。最后的结果就是数字栈里的数while(! operatorStack.isEmpty()){processAnoperator(numberStack,operatorStack);}System.out.println(numberStack.pop());}//在数字栈里弹出两个数字，在运算符栈里弹出一个数字，并进行运算private static void processAnoperator(ArrayStack<Integer> numberStack, ArrayStack<Character> operatorStack) {char op = operatorStack.pop();int num1 = numberStack.pop();int num2 = numberStack.pop();if(op == '+'){numberStack.push(num2 + num1);}if(op == '-'){numberStack.push(num2 - num1);}if(op == '*'){numberStack.push(num2 * num1);}if(op == '/'){numberStack.push(num2 / num1);}}private static String insertBlanks(String expression) {//insertBlank——添加空格StringBuilder sb =new StringBuilder();//遍历char c;for(int i =0;i<expression.length();i++){c = expression.charAt(i);//在运算符前后加#if(c == '(' || c =='+'||c == '-'||c == '*'||c =='/'||c == ')'){sb.append('#');sb.append(c);sb.append('#');}else {//数字前面不加sb.append(c);}}return sb.toString();}
中缀转后缀
public class InfixtoSuffix {public static void main(String[] args) {String infixExpression = "(3+2-4/2)-5";String suffixExpression = infixToSuffix(infixExpression);//中缀转后缀的方法System.out.println(suffixExpression);}private static String infixToSuffix(String infixExpression) {//建栈ArrayStack<String> opStack = new ArrayStack();ArrayList<String> suffixList = new ArrayList<>();//表达式格式化infixExpression = inserBlanks(infixExpression);String[] tokens = infixExpression.split(" ");System.out.println(Arrays.toString(tokens));for (String token : tokens) {if (token.length() == 0) {continue;}if (isOperator(token)) {while (true) {//栈空或者是栈顶为（直接进if (opStack.isEmpty() || "(".equals(opStack.peek())) {opStack.push(token);break;}//如果遍历的优先级大于栈// 里的优先级，直接进if (priority(token) > priority(opStack.peek())) {opStack.push(token);break;}//都不是就出栈suffixList.add(opStack.pop());}} else if (isNumber(token)) {//如果是数字suffixList.add(token);} else if ("(".equals(token)) {//如果是（opStack.push(token);} else if (")".equals(token)) {//如果是）while (true) {if ("(".equals(opStack.peek())) {opStack.pop();break;} else {suffixList.add(opStack.pop());}}}else {throw new IllegalArgumentException("worng identfer"+token);}}while (!opStack.isEmpty()){suffixList.add(opStack.pop());}StringBuilder sb = new StringBuilder();for(int i =0;i<suffixList.size();i++){sb.append(suffixList.get(i)+" ");}return sb.toString();}private static int priority(String token) {if("*".equals(token)||"/".equals(token)){return 1;}if("+".equals(token)||"-".equals(token)){return 0;}return -1;}private static boolean isNumber(String token) {return token.matches("\\d+");//\\d+表示多个数字}private static boolean isOperator(String token) {return "+".equals(token)||"-".equals(token)||"*".equals(token)||"/".equals(token);}private static String inserBlanks(String expression) {StringBuilder sb =new StringBuilder();//遍历char c;for(int i =0;i< expression.length();i++){c = expression.charAt(i);//在运算符前后加#if(c == '(' || c =='+'||c == '-'||c == '*'||c =='/'||c == ')'){sb.append(' ');sb.append(c);sb.append(' ');}else {//数字前面不加sb.append(c);}}return sb.toString();}}
3)双端栈
将一个线性表的两端进行入栈出栈
左端栈为空: ltop=-1;
左端元素个数:=ltop +1;
右端栈为空 : rtop = length;
右端元素个数= length -rtop;
栈满 ：ltop +1 =rtop';
双端栈是线性表的一种特殊表现，更是栈的一个特殊分类。
可用动态数组和栈的思想实现双端栈。
接口
private E[] data;//存元素的容器private int ltop;//左端栈顶，ltop=-1为空，ltop+1为个数private int rtop;//右端栈顶，rtop=data.length为空，length-rtop 为元素个数private static int DEFAULT_SIZE = 10;//设置默认容量为10基本操作
public ArrayDoubleEndStack() {data = (E[]) new Object[DEFAULT_SIZE];ltop = -1;rtop = data.length;}//入栈public void push(E element,int stackId){//atackid表示栈，0，为左端栈，1为右端栈if(ltop +1 == rtop){//栈满，得扩容resize(data.length*2);switch (stackId){case 0://左端栈data[++ltop]=element;break;case 1://右端栈data[--rtop]=element;break;}}}private void resize(int newlength) {E[] newData =(E[]) new Object[newlength];//先处理左端栈//左端栈可以见元素一过去,且ltop所指位置不变for(int i=0;i<ltop;i++){newData[i] = data[i];}//右端栈int index = rtop;for(int i=newlength-size(1);i<newlength;i++){newData[i] = data[index++];}rtop = newlength - size(1);data = newData ;}//入栈public E pop(int stackId){if(isEmpty(stackId)){throw new NullPointerException("stack is null");}E ret = null;switch (stackId){case 0:ret = data[ltop--];break;case 1:ret = data[rtop++];break;}return ret;}public int size(int stackId){switch (stackId){case 0:return ltop+1;case 1:return data.length-rtop;}return -1;}//p判断某一端的栈是否为空private boolean isEmpty(int stackId) {switch (stackId){case 0:return ltop == -1;case 1:return rtop == data.length;}return false;}//获取栈顶元素public E peek(int stackId){if(isEmpty(stackId)){throw new NullPointerException("stack is null");}switch (stackId){case 0:return data[ltop];case 1:return data[rtop];}return null;}//清空public void clear(int stackId){switch (stackId){case 0:ltop = -1;case 1:rtop = data.length;}}public String toString(){StringBuilder sb =new StringBuilder(String.format("ArratDableEndStack:%d/%d",size(0)+size(1),data.length));if(isEmpty(0)){//左端栈为空sb.append("leftStack:[]");}else {sb.append("leftStack:[]");for(int i =0;i<=ltop;i++){sb.append(data[i]);if(i == ltop){sb.append(']');sb.append('\n');}else{sb.append(',');}}}if (isEmpty(1)){//右端栈sb.append("righeStack:[");}else {sb.append("rightStack:[");for(int i= data.length-1;i>=rtop;i--){sb.append(data[i]);if(i == rtop){sb.append(']');sb.append('\n');}else{sb.append(',');}}}return sb.toString();}
4、队列
只允许在一端进行插入操作，另一端进行删除操作的线性表
可以插入的一端叫队尾，可以删除的一端叫队首
不含任何数据元素的队列称空队列
队列是一种先进先出的线性表
接口的实现
public interface Queue<E> extends Iterable<E> {public int size();//有效元素个数public boolean isEmpty();//检测是否为空public void offer(E element);//入队public E poll();//出队public E element();//队首元素public void clear();//清空}队列的基本操作
public class ArrayQueue<E> implements Queue<E> {private ArrayList<E> list;//底层代码用List实现public ArrayQueue(){this(10);}private ArrayQueue(int capacity){list =new ArrayList<>(capacity);//设置容量}@Overridepublic int size() {return list.size();}@Override public boolean isEmpty() {return list.isEmpty();}@Overridepublic void offer(E element) {list.add(element);}@Overridepublic E poll() {return list.remove(0);}@Overridepublic E element() {return list.get(0);}@Overridepublic void clear() {list.clear();}@Overridepublic Iterator iterator() {return list.iterator();}@Overridepublic String toString() {StringBuilder sb = new StringBuilder(String.format("ArrayQueue:%d/%d[",size(),list.getCapacity()));if(isEmpty()){sb.append("[");}else{for(int i = 0;i < size();i++){sb.append(list.get(i));if(i != size()-1 ){sb.append(",");}else {sb.append("]");}}}return list.toString();}
}优化队列【循环队列】
队头和队尾指针随着元素的变化而移动
当队尾指针或队头指针到达尾部时，如需后移可重新指向表头
将一个空间预留出来，不存任何元素，rear指向null
队列已满：（rear + 1) % data.length == front;
队列为空：rear == front；
三、动态链表
链式存储结构的具体实现的核心思想
头结点：链表中的第一个结点，有真实头结点和虚拟头结点之分。
真实头结点可以存储数据，虚拟头结点不能存储数据
头指针：引用变量，存储头结点的地址——head
尾指针：链表中最后一个结点——tail
1、单向链表的实现
线性结构链式存储方式的具体实现
单向链表的基本操作
package part02.动态链表;import part01.动态数组.ArrayList;
import 数据结构接口.List;import javax.jws.soap.SOAPMessageHandlers;
import java.util.Comparator;
import java.util.Iterator;public class LinkedSinglyList<E> implements List<E> {private class Node{//定义一个结点，内部类E data;//数据域——存储数据Node next;//指针域——存储下一个结点对象的地址public Node(){this(null,null);}public Node(E data){this(data,null);}public Node(E data,Node next){this.data=data;this.next=next;}@Overridepublic String toString() {return data.toString();}}private Node head;//链表中的头指针，指向第一个结点private Node tail;//链表中的尾指针，指向最后一个元素private int size;//有效元素个数public LinkedSinglyList(){head = null;tail = null;size = 0;}public LinkedSinglyList(E[] arr){for(E e:arr){add(e);}}@Override//默认在尾部添加对象public void add(E element) {add(size,element);}@Override//在指定角标处添加元素public void add(int index, E element) {if(index < 0 || index >size){throw new ArrayIndexOutOfBoundsException("INDEX IS OUT");}//创建一个新的结点对象Node node = new Node(element);//链表为空if(isEmpty()){head = node;tail = node;}else if(index == 0) {//在表头添加node.next = head;head = node;}else if(index == size) {//在表尾添加tail.next = node;tail = node;}else {//在表中添加Node p = head;for(int i = 0; i < index-1;i++){p = p.next;}node.next =p.next;p.next = node;}size ++;}@Overridepublic void remove(E element) {int index = indexOf(element);//indexOf ：从头至尾找到这个元素的第一个角标if(index != -1){remove(index);}}@Override//删除指定角标的数值public E remove(int index) {if(index < 0 || index >size){throw new IndexOutOfBoundsException("remove index out of bounds ");}E ret = null;if(size == 1){//只有一个值的时候ret = head.data;head = null;tail = null;}else if(index == 0) {//删除表头Node del = head;ret = del.data;head = del.next;del.next = null;}else if(index == size - 1) {//删除表尾Node p = head;while (p.next != tail){p = p.next;}ret = tail.data;p.next = null;tail = p;}else {//删除表中Node p = head;for(int i= 0;i < index -1;i++){p =p.next;}Node del = p.next;ret = del.data;p.next = del.next;del.next = null;}size --;return ret;}@Overridepublic E get(int index) {if(index < 0 || index > size){throw new ArrayIndexOutOfBoundsException("Index is out of Bounds");}if(index == 0) {//表头return head.data;}else if(index == size-1){//表尾return tail.data;}else {//中间元素Node p = head;for(int i = 0;i < index ; i++){p = p.next;}return p.data;}}@Overridepublic E set(int index, E element) {if(index < 0 || index > size){throw new ArrayIndexOutOfBoundsException("Index is out of Bounds");}E ret = null;if(index == 0){//修改头ret = head.data;head.data = element;}else if(index == size - 1){//修改尾ret = tail.data;tail.data = element;}else{//修改中间Node p =head;for(int i = 0;i < index ; i++){p = p.next;}ret = p.data;p.data = element;}return ret;}@Overridepublic int size() {return size;}@Overridepublic int indexOf(E element) {Node p = head;int index = 0;while (! p.data.equals(element)){p = p.next;index ++;if(p == null){return -1;}}return index;}@Override//判断表中是否存在elementpublic boolean contains(E element) {return indexOf(element) != -1;}@Overridepublic boolean isEmpty() {return size == 0 && head == null && tail == null;}@Overridepublic void clear() {head = null;tail = null;size = 0;}@Overridepublic void sort(Comparator<E> C) {if(C ==null){throw new IllegalArgumentException("Comparator can not be null");}/* int j=0;E e =null;for(int i=1;i< size;i++){e = get(i);//使用e暂存i上的数字进行比较for(j =i;j>0&&Cpare(get(j-1),e)>0;j++){//j>0并且j 的左边有数字，用compare进行比较。set(j,get(j-1));}set(j,e);}*/if(size == 0 || size == 1){return;}Node nodeA = head;Node nodeB = nodeA.next;while (true){ //对Awhile (true){//对Bif(Cpare(nodeA.data,nodeB.data)>0){swap(nodeA,nodeB);}if(nodeB == tail){break;}nodeB = nodeB.next;if(nodeA.next == tail){break;}nodeA = nodeA.next;nodeB = nodeA.next;}}}private void swap(Node nodeA, Node nodeB) {E temp = nodeA.data;nodeA.data = nodeB.data;nodeB.data = nodeA.data;}@Overridepublic List<E> subList(int formindex, int toindex) {//保证0<fromindex<=toindex<sizeif(formindex<0){throw new IndexOutOfBoundsException("fromindex must >0");}if(formindex>toindex){throw new IndexOutOfBoundsException("fromindex must <= toindex");}if(toindex >size){throw new IndexOutOfBoundsException("toindex must <size");}LinkedSinglyList<E> sublist = new LinkedSinglyList<>();//创建一个新线性表，可规定容量/*for(int i = formindex;i<=toindex;i++){sublist.add(get(i));//调用add，直接传输数据}*/Node nodeA = head;for(int i = 0;i <formindex;i++){nodeA = nodeA.next;}Node nodeB = head;for(int i = 0;i<toindex;i++){nodeB = nodeB.next;}Node p = nodeA;while (true){sublist.add(p.data);if(p == nodeB){break;}p = p.next;}return sublist;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder(String.format("LinkedSinglyList:%d[",size));if(isEmpty()){sb.append(']');}else {Node p =head;while (true) {sb.append(p.data);if(p == tail){sb.append(']');break;}else {sb.append(',');p = p.next;}}}return sb.toString();}@Overridepublic Iterator<E> iterator() {return null;}class LinkedListIteartor implements Iterator<E>{private Node cur = head;@Overridepublic boolean hasNext() {return cur != null;}@Overridepublic E next() {E ret = cur.data;cur = cur.next;return ret;}}}
2、单向循环链表
将单链表的最后一个指针指向链表的头部，而不是指向null，那么就可以构成一个单向循环链表。
package part02.动态链表;import com.sun.apache.xpath.internal.operations.Bool;
import 数据结构接口.List;import java.util.Comparator;
import java.util.Iterator;public class LinkedSinglyCircularList<E> implements List<E> {private class Node{//定义一个结点，内部类E data;//数据域——存储数据Node next;//指针域——存储下一个结点对象的地址public Node(){this(null,null);}public Node(E data){this(data,null);}public Node(E data, Node next){this.data=data;this.next=next;}@Overridepublic String toString() {return data.toString();}}private Node head;//链表中的头指针，指向第一个结点private Node tail;//链表中的尾指针，指向最后一个元素private int size;//有效元素个数public LinkedSinglyCircularList(){head = null;tail = null;size = 0;}public LinkedSinglyCircularList(E[] arr){for(E e:arr){add(e);}}@Override//默认在尾部添加对象public void add(E element) {add(size,element);}@Override//在指定角标处添加元素public void add(int index, E element) {if(index < 0 || index >size){throw new ArrayIndexOutOfBoundsException("INDEX IS OUT");}//创建一个新的结点对象Node node = new Node(element);//链表为空if(isEmpty()){head = node;tail = node;tail.next = head;}else if(index == 0) {//在表头添加node.next = head;head = node;tail.next = head;}else if(index == size) {//在表尾添加node.next = tail.next;tail.next = node;tail = node;}else {//在表中添加Node p = head;for(int i = 0; i < index-1;i++){p = p.next;}node.next =p.next;p.next = node;}size ++;}@Overridepublic void remove(E element) {int index = indexOf(element);//indexOf ：从头至尾找到这个元素的第一个角标if(index != -1){remove(index);}}@Override//删除指定角标的数值public E remove(int index) {if(index < 0 || index >size){throw new IndexOutOfBoundsException("remove index out of bounds ");}E ret = null;if(size == 1){//只有一个值的时候ret = head.data;head = null;tail = null;}else if(index == 0) {//删除表头Node del = head;ret = del.data;head = del.next;del.next = null;tail.next = head;}else if(index == size - 1) {//删除表尾Node p = head;while (p.next != tail){p = p.next;}ret = tail.data;p.next = head;tail = p;}else {//删除表中Node p = head;for(int i= 0;i < index -1;i++){p =p.next;}Node del = p.next;ret = del.data;p.next = del.next;del.next = null;}size --;return ret;}@Overridepublic E get(int index) {if(index < 0 || index > size){throw new ArrayIndexOutOfBoundsException("Index is out of Bounds");}if(index == 0) {//表头return head.data;}else if(index == size-1){//表尾return tail.data;}else {//中间元素Node p = head;for(int i = 0;i < index ; i++){p = p.next;}return p.data;}}@Overridepublic E set(int index, E element) {if(index < 0 || index > size){throw new ArrayIndexOutOfBoundsException("Index is out of Bounds");}E ret = null;if(index == 0){//修改头ret = head.data;head.data = element;}else if(index == size - 1){//修改尾ret = tail.data;tail.data = element;}else{//修改中间Node p =head;for(int i = 0;i < index ; i++){p = p.next;}ret = p.data;p.data = element;}return ret;}@Overridepublic int size() {return size;}@Overridepublic int indexOf(E element) {Node p = head;int index = 0;while (! p.data.equals(element)){p = p.next;index ++;if(p == head){return -1;}}return index;}@Override//判断表中是否存在elementpublic boolean contains(E element) {return indexOf(element) != -1;}@Overridepublic boolean isEmpty() {return size == 0 && head == null && tail == null;}@Overridepublic void clear() {head = null;tail = null;size = 0;}@Overridepublic void sort(Comparator<E> C) {if(C ==null){throw new IllegalArgumentException("Comparator can not be null");}/* int j=0;E e =null;for(int i=1;i< size;i++){e = get(i);//使用e暂存i上的数字进行比较for(j =i;j>0&&Cpare(get(j-1),e)>0;j++){//j>0并且j 的左边有数字，用compare进行比较。set(j,get(j-1));}set(j,e);}*/if(size == 0 || size == 1){return;}Node nodeA = head;Node nodeB = nodeA.next;while (true){ //对Awhile (true){//对Bif(Cpare(nodeA.data,nodeB.data)>0){swap(nodeA,nodeB);}if(nodeB == tail){break;}nodeB = nodeB.next;if(nodeA.next == tail){break;}nodeA = nodeA.next;nodeB = nodeA.next;}}}private void swap(Node nodeA, Node nodeB) {E temp = nodeA.data;nodeA.data = nodeB.data;nodeB.data = nodeA.data;}@Overridepublic List<E> subList(int formindex, int toindex) {//保证0<fromindex<=toindex<sizeif(formindex<0){throw new IndexOutOfBoundsException("fromindex must >0");}if(formindex>toindex){throw new IndexOutOfBoundsException("fromindex must <= toindex");}if(toindex >size){throw new IndexOutOfBoundsException("toindex must <size");}part02.动态链表.LinkedSinglyList<E> sublist = new part02.动态链表.LinkedSinglyList<>();//创建一个新线性表，可规定容量/*for(int i = formindex;i<=toindex;i++){sublist.add(get(i));//调用add，直接传输数据}*/Node nodeA = head;for(int i = 0;i <formindex;i++){nodeA = nodeA.next;}Node nodeB = head;for(int i = 0;i<toindex;i++){nodeB = nodeB.next;}Node p = nodeA;while (true){sublist.add(p.data);if(p == nodeB){break;}p = p.next;}return sublist;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder(String.format("LinkedSinglyList:%d[",size));if(isEmpty()){sb.append(']');}else {Node p =head;while (true) {sb.append(p.data);if(p == tail){sb.append(']');break;}else {sb.append(',');p = p.next;}}}return sb.toString();}@Overridepublic Iterator<E> iterator() {return new LinkedSinglyCircularListIteartor();}class LinkedSinglyCircularListIteartor implements Iterator<E>{private Node cur = head;private Boolean flag = true;//表示可以继续（没有第二次指向haed@Overridepublic boolean hasNext() {if(isEmpty()){return false;}return flag;}@Overridepublic E next() {E ret = cur.data;cur = cur.next;if(cur == head){flag = false;//第二次指向head}return ret;}}public void JosePhusLoop(){if(size <= 2){return;}Node p = head;while (size != 2) {p = p.next;Node del = p.next;if(del == head){head = head.next;}else if(del == tail){tail = p;}p.next = del.next;del.next = null;size --;p = p.next;}}}
3、双向链表
也叫双链表每个节点都有两个指针，分别指向直接前驱和直接后继
原理与单链表基本一致
package part02.动态链表;import 数据结构接口.Deque;
import 数据结构接口.List;
import 数据结构接口.Stack;import java.util.Comparator;
import java.util.Iterator;public class LinkedList<E> implements List<E>, Deque<E>, Stack<E> {//定义结点private class Node{E data;Node pre;//指向前驱的指针Node next;//指向后继的指针public Node(){this(null,null,null);}public Node (E data){this(data,null,null);}public Node(E data,Node pre,Node next){this.data = data;this.pre = pre;this.next = next;}@Overridepublic String toString() {return data.toString();}}private Node head;private Node tail;private int size;public LinkedList(){head = null;tail = null;size = 0;}public LinkedList(E[] arr){for(E e:arr){add(e);}}@Override//默认添加在后面public void add(E element) {add(size,element);}@Override//在指定角标添加元素public void add(int index, E element) {if(index < 0 || index > size){throw new ArrayIndexOutOfBoundsException("index is out of bounds");}Node node = new Node(element);/*数组为空1.head 指向新结点2. tail指向新结点3,head.pre 指向tail4.tail.next 指向head*/if(isEmpty()){head = node;tail = node;head.pre = tail;tail.next = head;}else if(index == 0) {/*在表头添加1.把head.pre给node.pre2.node.next 指向头；3.head的上一跳指向node4.head赋给node4.tail的next指向noda*/node.pre = head.pre;node.next = head;head.pre = node;head = node;tail.next = head;}else if(index == size - 1) {//在表尾添加node.next = tail.next;tail.next = node;node.pre = tail;tail = node;head.pre = node;}else {//在中段添加Node p,q;if(index <= size / 2){p = head;for(int i = 0;i < index-1; i ++){p = p.next;}q = p.next;p.next = node;node.pre = p;q.pre = node;node.next = q;}else {p = tail;for (int i = size - 1; size > index; i++) {p = p.pre;}q = p.pre;q.next = node;node.pre = q;p.pre = node;node.next = p;}}size ++;}@Overridepublic void remove(E element) {int index = indexOf(element);//indexOf ：从头至尾找到这个元素的第一个角标if(index != -1){remove(index);}}@Override//删除指定位置的元素public E remove(int index) {if(index < 0 || index >size){throw new IndexOutOfBoundsException("index is out of bounds");}E ret = null;Node node;if(size == 1) {//只有一个元素时ret = head.data;head = null;tail = null;} else if (index == 0) {/*删除头结点1.node指向head.next最终node的头结点2.head的吓一跳置空3.head的上一跳给node的上一跳，head的上一跳置空4.head重新指向node5.tail的吓一跳指向node*/ret = head.data;node= head.next;head.next = null;node.pre =head.pre;head.pre = null;head = node;tail.next = head;}else if(index == size-1) {//删除尾结点ret = tail.data;node = tail.pre;tail.pre = null;node.next = tail.next;tail = node;tail.pre = null;}else {//删除中间结点Node p,q,r;if (index <= size/2) {p = head;for(int i = 0;i < index-1 ;i ++){p= p.next;}q = p.next;ret = q.data;r = q.next;p.next = r;r.pre = p;q.next = null;q.pre = null;}else {p = tail;for(int i =size -1 ;i >index+1;i--){p = p.pre;}q = p.pre;ret = q.data;r = q.pre;p.pre = r;r.next = p;q.pre = null;q.next = null;}}size --;return ret;}@Overridepublic E get(int index) {if(index < 0 || index > size){throw new ArrayIndexOutOfBoundsException("Index is out of Bounds");}if(index == 0) {//表头return head.data;}else if(index == size-1){//表尾return tail.data;}else {//中间元素Node p = head;for(int i = 0;i < index ; i++){p = p.next;}return p.data;}}@Overridepublic E set(int index, E element) {if(index < 0 || index > size){throw new ArrayIndexOutOfBoundsException("Index is out of Bounds");}E ret = null;if(index == 0){//修改头ret = head.data;head.data = element;}else if(index == size - 1){//修改尾ret = tail.data;tail.data = element;}else{//修改中间Node p =head;for(int i = 0;i < index ; i++){p = p.next;}ret = p.data;p.data = element;}return ret;}@Overridepublic void addFirst(E element) {add(0,element);}@Overridepublic void addLast(E element) {add(size,element);}@Overridepublic E removeFirst() {return remove(0);}@Overridepublic E removeLast() {return remove(size-1);}@Overridepublic E getFirst() {return get(0);}@Overridepublic E getLast() {return get(size-1);}@Overridepublic int size() {return size;}@Overridepublic int indexOf(E element) {Node p = head;int index = 0;while (! p.data.equals(element)){p = p.next;index ++;if(p == head){return -1;}}return index;}@Overridepublic boolean contains(E element) {return indexOf(element) != -1;}@Overridepublic boolean isEmpty() {return size == 0 && head == null && tail == null;}@Overridepublic void push(E element) {addLast(element);}@Overridepublic E pop() {return removeLast();}@Overridepublic E peek() {return getLast();}@Overridepublic void offer(E element) {addLast(element);}@Overridepublic E poll() {return removeFirst();}@Overridepublic E element() {return getFirst();}@Overridepublic void clear() {head = null;tail = null;size = 0;}@Overridepublic void sort(Comparator<E> C) {if(C ==null){throw new IllegalArgumentException("Comparator can not be null");}if(size == 0 || size == 1){return;}Node nodeA = head;Node nodeB = nodeA.next;while (true){ //对Awhile (true){//对Bif(Cpare(nodeA.data,nodeB.data)>0){swap(nodeA,nodeB);}if(nodeB == tail){break;}nodeB = nodeB.next;if(nodeA.next == tail){break;}nodeA = nodeA.next;nodeB = nodeA.next;}}}private void swap(Node nodeA, Node nodeB) {E temp = nodeA.data;nodeA.data = nodeB.data;nodeB.data = nodeA.data;}@Overridepublic List<E> subList(int formindex, int toindex) {if(formindex<0){throw new IndexOutOfBoundsException("fromindex must >0");}if(formindex>toindex){throw new IndexOutOfBoundsException("fromindex must <= toindex");}if(toindex >size){throw new IndexOutOfBoundsException("toindex must <size");}LinkedList<E> sublist = new LinkedList<>();//创建一个新线性表，Node nodeA = head;for(int i = 0;i <formindex;i++){nodeA = nodeA.next;}Node nodeB = head;for(int i = 0;i<toindex;i++){nodeB = nodeB.next;}Node p = nodeA;while (true){sublist.add(p.data);if(p == nodeB){break;}p = p.next;}return sublist;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder(String.format("LinkedSinglyList:%d[",size));if(isEmpty()){sb.append(']');}else {Node p =head;while (true) {sb.append(p.data);if(p == tail){sb.append(']');break;}else {sb.append(',');p = p.next;}}}return sb.toString();}@Overridepublic Iterator<E> iterator() {return new LinkedList.LinkedListIteartor();}class LinkedListIteartor implements Iterator<E>{private Node cur = head;private Boolean flag = true;//表示可以继续（没有第二次指向haed@Overridepublic boolean hasNext() {if(isEmpty()){return false;}return flag;}@Overridepublic E next() {E ret = cur.data;cur = cur.next;if(cur == head){flag = false;//第二次指向head}return ret;}}public void JosePhusLoop(){if(size <= 2){return;}Node p = head;while (size != 2) {p = p.next;Node del = p.next;if(del == head){head = head.next;}else if(del == tail){tail = p;}p.next = del.next;del.next = null;size --;p = p.next;}}
}
四、分治回溯
1.算法
算法—— 一个解决问题的流程和步骤
各种算法是针对不同问题的解决策略和思想。
2、递归
递归——程序调用自身的编辑技巧
将一个大型问题转化成一个相似的小规模计算，递归至于要少量程序描述多次重复计算。递归要有边界条件，递归前进段和递归返回段。
当递归条件不满足时，递归前进。当递归条件满足是递归返回。
3、分治算法
将原问题划分为n个规模较小，并且结构与原问题相似的子问题
三个操作
1）分解——将原问题分解成一系列子问题
2）解决——递归的求解各个子问题，若问题足够小，则直接求解
3）合并——将子问题的结果合并成原问题
四个条件
1）原问题与小问题有相同的模式
2）原问题分解成的子问题可独立求解，子问题之间无相关性
3）有分解终止条件
4）合并操作复杂度不能太高。
4、回溯算法
类似于枚举的搜索尝试过程
五、查找算法
根据给定的某个值，在表中确定一个关键字，给定数值元素
1、顺序查找算法
也称线性查找，从数据结构线性表的一端开始，顺序扫描，依次将扫描到的关键字与给定值比较，相等则返回角标，比较到最后一个都不想等，则查找失败。
【应用于顺序存储式链接存储】
2、二分查找
一种有序查找算法【效率较高】
素必须有序，若元素无序需要先进行排序操作
3、插值查找
对于表长较大且关键字分布均匀，插值查找比较方便
六、排序算法
1、比较类排序比较
通过比较来确定元素的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序
【选择、冒泡、插入、希尔、归并、堆、快速排序】
2、非比较类排序
不通过比较来确定元素之间的相对次序，可以突破基于时间比较的下界，以线性时行，因此也称为线性时间比较类排序
【计数、桶、基数】
3、相关概念
1）稳定：如果a原本在b前面，且a==b，排序后a仍在b前面。
2）不稳定：如果a原本在b前面，且a==b，排序后a在b后面。
3）时间复杂度：对排序数据的总操作次数，反映n变化时操作次数的规律
4）空间复杂度：算法在计算机内执行时所需要的存储空间的度量，也是数据规模n的函数
4、一些具体排序
冒泡排序
package Part05.排序算法;
//冒泡排序——稳定
import java.lang.reflect.Array;
import java.util.Arrays;public class BubleSort {public static void main(String[] args) {int[] arr = {1,3,2,4,6,5,7,9,8};bubleSort(arr);System.out.println(Arrays.toString(arr));}private static void bubleSort(int[] arr) {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]){swap(arr,j,j+1);}}}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr [j];arr[j] = temp;}
}
插入排序
package Part05.排序算法;import java.util.Arrays;//插入排序
public class InsertionSort {public static void main(String[] args) {int[] arr = {1,3,2,4,6,5,7,9,8};insertionSort(arr);System.out.println(Arrays.toString(arr));insertionSortUpper(arr);System.out.println(Arrays.toString(arr));}private static void insertionSortUpper(int[] arr) {int e = 0;int j = 0;for(int i = 1;i < arr.length ; i ++){e = arr[i];for (j = i;j > 0 && arr[j-1] > e; j --){arr[j] = arr[j-1];}}arr[j] = e;}private static void insertionSort(int[] arr) {for(int i = 1;i < arr.length ; i ++){for (int j = i ; j > 0 && arr[j -1] >arr[j]; j --){swap(arr,j,j-1);}}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr [j];arr[j] = temp;}
}
希尔排序
插入排序的改进版，优先比较距离远的元素，又叫缩小增量排序
package Part05.排序算法;import java.util.Arrays;public class ShellSort {public static void main(String[] args) {int[] arr = {1,3,2,4,6,5,7,9,8};shellSort(arr);System.out.println(Arrays.toString(arr));}public static void shellSort(int[] arr) {for(int gap = arr.length / 2; gap > 0 ;gap = gap /2){for (int i = gap ; i < arr.length;i ++){int j = i;int e = arr[j];while (arr[j-gap] > e && j- gap >= 0){arr[j] = arr[j - gap];j = j-gap;}arr[j] = e;}}}}
归并排序
将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列时间段有序，若将两个有序表合并成一个有序表，则称为归并排序
堆排序
利用堆这种数据结构设计的一种排序法，
二叉堆是一棵完全二叉树，堆中某个节点总不大于父节点的值
package Part05.排序算法;import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] arr = {1,3,2,4,6,5,7,9,8};heapSort(arr);System.out.println(Arrays.toString(arr));}private static int len;private static void heapSort(int[] arr) {len = arr.length;//1.将传入的数据堆化 heapfiyheapifiy(arr);//2.将最大值与最后一个元素交换for(int i = arr.length - 1; i >= 0; i --){swap(arr,0,i);len --;heapifiy(arr);}}private static void heapifiy(int[] arr) {for(int i = len - 1; i >= 0; i --){siftDown(arr,i);}System.out.println("heapify" + Arrays.toString(arr));}private static void siftDown(int[] arr,int k) {while (leftChild(k) < len){int j = leftChild(k);if(j +1 < len && arr[j + 1] > arr[j]){j = rightChild(k);}if(arr[k] < arr[j]){swap(arr,k,j);k = j;}else {break;}}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr [j];arr[j] = temp;}private static int leftChild(int i){return i * 2 + 1;}private static int rightChild(int i){return i * 2 + 2;}private static int parent(int i){return (i - 1) / 2;}
}
快速排序
通过一趟排序将待排记录分割成独立两部分，一部分记录的关键字比另一部分小，但是比另一部分大。分别在对这两部分进行排序
快速排序01——单路快速排序
package Part05.排序算法;import java.util.Arrays;public class QuickSort01{public static void main(String[] args) {int[] arr = {1, 3, 2, 4, 6, 5, 7, 9, 8};quickSort01(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}private static void quickSort01(int[] arr,int l , int r) {if(r - l <= 10){ShellSort.shellSort(arr);return;}int p = partition(arr,l,r);quickSort01(arr,9,p-1);quickSort01(arr,p+1,r);}private static int partition(int[] arr, int l, int r) {//优化swap(arr,l, (int) (Math.random()*(r - l + 1)+ l));int v = arr[l];int j = l;for (int i = j +1;i <= r;i ++){if(arr[i] < v){swap(arr,j +1,i);j++;}}swap(arr,l,j);return j;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr [j];arr[j] = temp;}
}
快速排序02——双路排序
package Part05.排序算法;import java.util.Arrays;public class QuickSort02 {public static void main(String[] args) {int[] arr = {1, 3, 2, 4, 6, 5, 7, 9, 8};quickSort02(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}private static void quickSort02(int[] arr, int l, int r) {if(l >= r){return;}int p = partition(arr,l,r);quickSort02(arr,l,p-1);quickSort02(arr,p+1,r);}private static int partition(int[] arr, int l, int r) {swap(arr,l, (int) (Math.random()*(r - l + 1)+ l));int v = arr[l];int i = l + 1;int j = r;while (true){while (i <= r && arr[i] < v){i ++;}while (j >= l + 1 && arr[j] > v ){j --;}if( i > j){break;}swap(arr,i,j);i ++;j --;}swap(arr,l,j);return j;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr [j];arr[j] = temp;}
}
快速排序03——三路排序
package Part05.排序算法;import java.util.Arrays;
//三路排序，用于重复较多的数组
public class QuickSort03 {public static void main(String[] args) {int[] arr = {1, 3, 2, 4, 6, 5, 7, 9, 8};quickSort03(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}private static void quickSort03(int[] arr, int l, int r) {if (l >= r) {return;}swap(arr, l, (int) (Math.random() * (r - l + 1) + l));int v = arr[l];int lt = l;int gt = r + 1;int i = l + 1;while (i < gt){if(arr[i] < v) {swap(arr, lt + 1, i);lt++;i++;}else if(arr[i]>v){swap(arr,i,gt-1);gt--;}else {i ++;}swap(arr,l,lt );quickSort03(arr,l,lt);quickSort03(arr,gt,r);}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr [j];arr[j] = temp;}}
计数排序
将数字与角标对应，数字则为原数组元素出现的次数
package Part05.排序算法;import java.util.Arrays;
//计数排序
public class CountingSort {public static void main(String[] args) {int[] arr = {1, 3, 2, 4, 6, 5, 7, 9, 8};countingSort(arr);System.out.println(Arrays.toString(arr));}private static void countingSort(int[] arr) {//1、获取最大值和最小值int max = arr[0];int min = arr[0];for (int i = 1;i < arr.length;i ++){if(arr[i] > max){max = arr[i];}if(arr[i] < min ){min = arr[i];}}//2、创建辅助数组int[] temp = new int[arr.length];int setoff = min - 0;//3、遍历原数组，将数字的个数存放在新的数组里for (int i = 0; i < arr.length; i++){temp[arr[i] - setoff] ++;}//4、遍历新数组temp，将统计结果处理int index = 0;for (int i = 0;i < temp.length; i ++){if(temp[i] != 0){for (int j = 0;j < temp[i]; j++){arr[index ++] = i + setoff;}}}}
}
桶排序
通过函数映射关系，将数字大致进行区间划分，再将区间进行排序
package Part05.排序算法;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;public class BucketSort {public static void main(String[] args) {int[] arr = new int[20];Random random = new Random();for (int i = 0;i < arr.length; i ++){arr[i] = random.nextInt(50);}bucketSort(arr);System.out.println(Arrays.toString(arr));}private static void bucketSort(int[] arr) {//1、获取最大值和最小值int max = arr[0];int min = arr[0];for (int i = 1;i < arr.length;i ++){if(arr[i] > max){max = arr[i];}if(arr[i] < min ){min = arr[i];}}//2、计算桶的数量int bucketNum = (max - min)/ arr.length + 1;//3、创建所有的桶ArrayList<Integer>[] buckets = new ArrayList[bucketNum];for (int i = 0;i <buckets.length;i++){buckets[i] = new ArrayList<>();}//4、遍历所有元素，放入桶中for (int i = 0;i <arr.length; i ++){buckets[(arr[i] - min)/arr.length].add(arr[i]);}//5、对每一个桶进行排序for(int i = 0;i < buckets.length;i ++){buckets[i].sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1pareTo(o2);}});System.out.println(i + ":" + buckets[i]);}//6、将桶的个数放到原数组中int index = 0;for (int i = 0;i <buckets.length; i ++){for (int j = 0;j < buckets[i].size();j++){arr[index++] = buckets[i].get(j);}}}
}
更多推荐
数据结构简要
发布评论