数据结构算法

数据结构算法整理

文章目录

时间&空间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函

数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，

T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=O(f(n)),称0(f(n))为算法的渐进时间复杂度，简称时间复

杂度。

常见的时间复杂度有：常数阶0(1),对数［logarithmic］阶0(log2n),

线性阶0(n),线性对数阶0(nlog2n),平方阶0(n2),立方阶0(n3),k

次方阶0(nk),指数阶0(2n)。随着问题规模n的不断增大，上述时间复

杂度不断增大，算法的执行效率越低。

算法时间复杂度由小到大依次为：0(1)<O(log2n)［二分］V

0(n)<0(nlog2n)<0(n2)<0(n3)<•••<0(2n)<

0(n!)0

求解算法的时间复杂度的具体步骤是：

找出算法中的基本语句；

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的

循环体。

计算基本语句的执行次数的数量级；

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句

执行次数的函数中的最高次幕正确即可，可以忽略所有低次幕和最高次塞

的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：

增长率。

用大0记号表示算法的时间性能。

将基本语句执行次数的数量级放入大0记号中。

空间复杂度比较常用的有：0(1)、o(n)、0(n2)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即

此算法空间复杂度为一个常量，可表示为0(1)

如果新建一个数组，这个数据占用的大小为n,虽然有循环，但没有

再分配新的空间，因此，空间复杂度主要看数组大小即可，即S(n)=0(n)o

数据结构

线性与非线性

线性：数组(Array)、链表(LinkedList)、栈(Stack)、队列(Queue)

非线形：多维数组、树结构、图结构

常见数据结构

稀疏数组

场景：解压缩

当一个数组中大部分元素为0,或者为同一个值的数组时，可以使用

稀疏数组来保存。

处理方法是:

第一行记录数组一共有几行几列和不同值的个数；而后记录每行不同

值的位置与实际值

环形队列

通过取模的方式实现。尾索引的下一个为头索引时表示队列满

双向链表

prev,next

单向环形链表

(约瑟夫环)

先创建一个节点，让first指向自己，形成环形；后面每创建一个新

节点，就将其加入到链表中(first.next=new;new.next=first)o

栈

先进后出结构，入栈push(top++),出栈pop(top-)[poll取空不

报错]

常见排序算法

插入排序

直接插入排序

希尔排序

选择排序

简单选择排序

堆排序

交换排序

冒泡排序

快速排序

归并排序

基数排序

内排序：所有排序操作都在内存完成

外排序：由于数据太大，需要把数据放在磁盘，通过磁盘和内存的数

据传输才能进行

交换排序-冒泡排序

重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错

误就把它们交换过来。

publicvoidmaopao({

int[]arr={0,-1,4,-2,9,5};

inttemp;

for(inti=0;i<arr.length-1;i++){

for(intj=0;j<arr.length-1-i;j++){〃趟

数是lenT-i

if(arr[j+1]<arr[j]){

temp=arr[j+1];

arr[j+1]=arr

arr[j]=temp;

}

)

)

System,out.printin(Arrays.toString(arr));

)o

交换排序•快速排序

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关

键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，

以达到整个序列有序。

publicvoidquicksort({

int[]arr={0,-1,4,-2,9,5,-3,4,8,7};

sort(arr,0,arr.length-1);

System,out.printin(Arrays.toString(arr));

)

privatevoidsort(int[]arr,intleft,intright){

int1=left;〃左下标

intr=right;〃右下标

intpivot=arr[(left+right)/2];//中轴值

inttemp=0;

while(1<r){

while(arr[1]<pivot){〃在pivot左边找

1+=1;

)

while(arr[r]>pivot){〃在pivot右边找

r-=1;

)

if(1>=r){

break;

}

//交换

temp=arr[1];

arr[1]=arr[r];

arr[r]=temp;

if(arr[1]==pivot){〃前移

r-=1;

if(arr[r]==pivot){〃后移

1+=1;

)

if(1==r){

1+=1;

r-=1;

}

if(left<r){〃向左递归

sort(arr,left,r);

)

if(right>1){〃向右递归

sort(arr,1,right);

)

)o

选择排序

首先在未排序的序列中找到最小(大)元素，存放到排序序列的起始

位置；再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序

序列的末尾。

publicvoidchooseSort({

int[]arr={0,-1,4,-2,9,5};

intmini,temp;

for(inti=0;i<arr.length-1;i++){

mini=i;

for(intj=i+1;j<arr.length;j++){

if(arr[j]<arr[mini]){〃找到最小(或最大)

mini=j;

}

}

temp=arr[i];

arr[i]=arr[mini];

arr[mini]=temp;

)

System,out.printin(Arrays.toString(arr));

)o

堆排序

也是一种选择排序，也是一种完全二叉树：每个节点的值都大于或等

于其左右孩子节点的值，称为大顶堆；小于等于称为小顶堆。

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描,

找到相应位置并插入。

publicvoidinsertSort({

int[]arr={0,-1,4,一2,9,5};

intlasti,curr;

for(inti=1;i<arr.length;i++){

lasti=i-1;〃上一个索引

curr=arr[i];

while(lasti>=0&&arr[lasti]>curr){

arr[lasti+1]=arr[lasti];

lasti一;

)

arr[lasti+1]=curr;

}

System,out.printin(Arrays.toString(arr));

}o

其他：希尔排序，缩小增量排序

归并排序

将多个有序的子序列合并，得到完全有序的序列，即先使每个子序列

有序，再使子序列段间有序。

publicvoidmergeSortTest({

int[]arr={8,4,5,7,1,3,6,2};

int[]temp=newint[arr.length];〃额外空间排序

mergeSort(arr,0,arr.length-1,temp);

System,out.printin(Arrays.toString(arr));

)

privatevoidmergeSort(int[]arr,intleft,intright,int[]

temp){

if(left<right){

intmiddle=(left+right)/2;

mergeSort(arr,left,middle,temp);〃向左递归分解

mergeSort(arr,middle+1,right,temp);〃向右递归

分解

merge(arr,left,middle,right,temp);〃再合并

)

)

publicvoidmerge(int[]arr,intleft,intmiddle,intright,

int[]temp){

inti=left;〃左边初始序列索引

intj=middle+1;〃右边初始序列索引

intt=0;〃指向temp数组的当前索引

while(i<=middle&&j<=right){

if(arr[i]<=arr[j]){

temp[t]=arr[i];

t+=1;

i+=1;

}else{

temp[t]=arr[j];

t+=1;

j+=1；

)

}

〃剩余元素填充

while(i<=middle){

temp[t]=arr[i];

t+=1;

i+=1;

while(j<=right){

temp[t]=arr[j];

t+=1;

j+=1；

)

//将temp数组拷贝到arr

t=0;

inttempLeft=left;

while(tempLeft<=right){

arr[tempLeft]=temp[t];

t+=1;

tempLeft+=1;

}

}o

基数排序

桶排序一种，将整数按照位数切割，然后按每个位数分别比较(消耗

存储,容易OOM)

案例一-文件修改时间排序

案例二«文件名称排序

常见查找算法

二分查找

publicstaticvoidmain(String[]args){

int[]arr=newint[]{1,4,5,7,8,12,45,67,99,

105};

System,out.printin(biSearch(arr,99));

)

publicstaticintbiSearch(int[]arr,intnum){

intstart=0;

intend=arr.length-1;

intmid;

while(start<=end){

System,out.printing'*");

mid=(start+end)/2;

if(arr[mid]==num){

returnmid+1;

}elseif(arr[mid]>num){//向左查找

end=mid-1;

}else{//向右查找

start=mid+1;

)

)

return-1;

}

publicstaticintbiSearch2(int[]arr,intstart,intend,

intnum){

if(start>end){

return-1;

)

intmid=(start+end)/2;

intmidVai=arr[mid];

if(midVai==num){

returnmid;

}elseif(midVai>num){//向左查找

returnbiSearch2(arr,start,end-1,num);

}else{//向右查找

returnbiSearch2(arr,start+1,end,num);

//查找多个值的情况。

插值查找

类似于二分，不同的是每次从自适应mid处开始查找，适用于连续且

量大的数据

公式：intmid=left+(right-left)*(findVal-arr[left])

/(arr[right]-arr[left])

注意需要判断findVal过大或过小越界的情况。

树结构

数组、链表和二叉树的优缺点略

二叉树

每个节点最有只有两个子节点(左节点、右节点)

满二叉树、完全二叉树

前序遍历：先输出父节点，再遍历左子树和右子树

中序遍历：先遍历左子树，再输出父节点，再遍历右子树

后序遍历：先遍历左子树，再遍历右子树，再输出父节点

二叉排序树

左边比根节点小，右边比根节点大

二叉排序树既可以保证数据的检索速度，同时也可以保证增删改的速

度

问题：极端情况，插入有序会退化成链表

publicvoidinsert(Treetree,intvalue){

if(tree.getValue(==0){

tree.setValue(value);

}elseif(tree.getValue(<value){

if(tree.getRight(==null){

tree.setRight(newTree();

)

insert(tree.getRight(,value);

}elseif(tree.getValue(>value){

if(tree.getLeft(==null){

tree.setLeft(newTree();

}

insert(tree.getLeft(,value);

)

}o

红黑树

平衡二叉树AVL的一种，降低树的高度，树高最大最小之差不超过1,

实现方式：旋转（左、右、双旋转（左+右））。Java中的TreeSet底层用

的就是红黑树。

左旋转：

NodenewNode=newNode（value）;

newNode.left=left;

newNode.right=right,left;

value=right.value;

right=right.right;

left=newNode;0

B树

B+树

在B树的基础上改造，它的数据都在叶子节点，同时叶子节点之间还

加了指针形成链表

由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需

要找到首尾，通过链表就能把所有数据取出来了

一般用于数据库索引（如果只取一条数据，Hash快）。

赫夫曼树

赫（哈Huffman）夫曼树带权路径长度最小的二叉树，也称最优二叉

树

创建一个赫夫曼树

应用：通讯领域信息传输、文件压缩解压，赫夫曼编码(按照各个字

符出现的次数进行编码)

递归与分治

递归

当程序执行到一个方法时，就会独立开辟一个空间(栈)，每个空间

中的局部变量也是独立的。

注意递归调用处前后代码的执行顺序

publicstaticvoidshow(intn){

System,out.printin(z/nl:"+n);//10->2

if(n>2){

show(n-1);

}

System,out.println(，，n2:"+n);〃2->10

)o

分治

待解决复杂的问题能够简化为几个若干个小规模相同的问题，然后逐

步划分，达到易于解决的程度。应用：阶乘、斐波纳契数列、汉诺塔问题、

棋盘覆盖、找出伪币、求最值

案例一•汉诺塔

publicstaticvoidmain({

move(5,"A柱〃，〃B柱”，〃C柱〃);

)

publicstaticvoidmove(intnum,Stringa,Stringb,String

c){

if(num==1){

disPaly(num,a,c);

}else{

move(num-1,a,c,b);

disPaly(num,a,c);

move(num-1,b,a,c);

)

)

publicstaticvoiddisPaly(intnum,Stringsi,Strings2){

System,out.printin("第"+num+”个塔从"+si+"到"+

s2);

}。

案例二•走迷宫

publicstaticvoidmain(String[]args){

int[][]map={

{1,1,1,1,1,1,1,1,1},

(1,0,0,0,0,0,0,0,1},

{1,1,1,1,0,1,1,1,1),

{1,1,0,0,0,0,0,1,1},

{1,0,0,1,0,1,1,1,1},

{1,o,1,1,0,1,1,1,1},

{1,o,0,1,1,1,1,1,1},

{1,o,0,0,1,1,1,1,1},

{1,1,1,o,1,1,1,1,1},

{1,1,1,0,0,0,0,0,1},

(1,1,1,1,1,1,1,1,1}

);

System,out.printin("原来的地图11*9");

for(inti=0;i<11;i++){

for(intj=0;j<9;j++){

System,out.print(map[i][j]+“");

System,out.printin(;

//1,1是起点9,7是终点

setWay(map,1,1);

System,out.printin("走过的地图”);

for(inti=0;i<11;i++){

for(intj=0;j<9;j++){

if(map[i][j]==2){

System,out.format(，z\33[32;lm，/+map[i][j]+

“\33[0m〃);

}else{

System,out.print(map[i][j]+"");

}

)

System,out.printin(;

}

}

//0-还没走1-不可以走2-可以走3-走过不行

publicstaticbooleansetWay(int[][]map,intx,inty){

if(map[9][7]==2){

returntrue;

else{

if(map[x][y]==0){

map[x][y]=2;

if(setWay(map,x+1,y)){〃下

returntrue;

}elseif(setWay(map,x,y+1)){//右

returntrue;

}elseif(setWay(map,x-1,y)){〃上

returntrue;

}elseif(setWay(map,x,y-1)){〃左

returntrue;

}else{

map[x][y]=3;

returnfalse;

}else{

returnfalse;

)o

动态规划

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,

可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优

值的解，使用填表的方式。

与分治法不同的是，分解得到的子问题是非独立的，即下一个子阶段

的求解是建立在上一个子阶段的解的基础上。

案例一•有n级台阶，一个人每次上一级或者两级，问有多少种走完

n级台阶的方法。

publicstaticint[]steps=newint[11];

publicstaticvoidmain({

steps[10]=calStep(10);

for(inti=0;i<steps,length;i++){

System,out.print(steps[i]+"");

}

System,out.printin(;

System,out.printIn(steps[10]);

)

privatestaticintcalStep(intn){

if(n==1||n==2){

returnn;

)

if(steps[n-1]==0){

steps[n-1]calStep(n-1);

if(steps[n-2]==0){

steps[n-2]=calStep(n-2);

returnsteps[n-1]+steps[n-2];

)o

案例二-给定一个矩阵，从左上角开始每次只能向右走或者向下走，

最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有

路径的最小路径和

publicvoidstep({

int[][]arr={

{4,1,5,3),

{3,2,7,7),

{6,5,2,8},

[8,9,4,5)

)；

intresult=minSteps(arr);

System,out.printin(，，result=/，+result);

)

privatestaticintminSteps(int[][]arr){

introw=arr.length;

intcol=arr[0].length;

int[][]steps=newint[row][col];

steps[0][0]=arr[0][0];

for(inti=1;i<row;i++){//列+,从上到下

steps[i][0]=steps[i-1][0]+arr[i][0];

)

for(intj=1;j<col;j++){//行+,从左到右

steps[0][j]=steps[0][j-1]+arr[0][j];

}

for(inti=1;i<row;i++){

for(intj=1;j<col;j++){

steps[i][j]=Math,min(steps[i-1][j],

steps[i][j-1])+arr[i][j];

)

}

/*for(inti=0;i<steps.length;i++){

for(inti1=0;il<steps,length;i1++){

System,out.print(steps[i][il]+"");

)

System,out.print("\n");

}*/

returnsteps[row-1][col-1];

}

〃优化解法

publicstaticintminSteps2(int[][]arr){

intcol=arr[0].length;

int[]steps=newint[col];

steps[0]=arr[0][0];

for(inti=1;i<col;i++){

steps[i]=steps[i-1]+arr[0][i];〃第一行

for(inti=1;i<arr.length;i++){

steps[0]=arr[i][0]+steps[0];〃每一行的最左边

for(intj=1;j<col;j++){

steps[j]=Math,min(steps[j-1]+arr[i][j],

steps[j]+arr[i][j]);

}

)

System,out.printin(Arrays.toString(steps));

returnsteps[col-1];

}o

贪心算法

在每一