數(shù)據(jù)結(jié)構(gòu)算法

數(shù)據(jù)結(jié)構(gòu)算法整理

文章目錄

時間&空間復(fù)雜度

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函

數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時，

T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。

記作T(n)=O(f(n)),稱0(f(n))為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)

雜度。

常見的時間復(fù)雜度有：常數(shù)階0(1),對數(shù)［logarithmic］階0(log2n),

線性階0(n),線性對數(shù)階0(nlog2n),平方階0(n2),立方階0(n3),k

次方階0(nk),指數(shù)階0(2n)。隨著問題規(guī)模n的不斷增大，上述時間復(fù)

雜度不斷增大，算法的執(zhí)行效率越低。

算法時間復(fù)雜度由小到大依次為：0(1)<O(log2n)［二分］V

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

0(n!)0

求解算法的時間復(fù)雜度的具體步驟是：

找出算法中的基本語句；

算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的

循環(huán)體。

計算基本語句的執(zhí)行次數(shù)的數(shù)量級；

只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句

執(zhí)行次數(shù)的函數(shù)中的最高次幕正確即可，可以忽略所有低次幕和最高次塞

的系數(shù)。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點上：

增長率。

用大0記號表示算法的時間性能。

將基本語句執(zhí)行次數(shù)的數(shù)量級放入大0記號中。

空間復(fù)雜度比較常用的有：0(1)、o(n)、0(n2)

如果算法執(zhí)行所需要的臨時空間不隨著某個變量n的大小而變化，即

此算法空間復(fù)雜度為一個常量，可表示為0(1)

如果新建一個數(shù)組，這個數(shù)據(jù)占用的大小為n,雖然有循環(huán)，但沒有

再分配新的空間，因此，空間復(fù)雜度主要看數(shù)組大小即可，即S(n)=0(n)o

數(shù)據(jù)結(jié)構(gòu)

線性與非線性

線性：數(shù)組(Array)、鏈表(LinkedList)、棧(Stack)、隊列(Queue)

非線形：多維數(shù)組、樹結(jié)構(gòu)、圖結(jié)構(gòu)

常見數(shù)據(jù)結(jié)構(gòu)

稀疏數(shù)組

場景：解壓縮

當(dāng)一個數(shù)組中大部分元素為0,或者為同一個值的數(shù)組時，可以使用

稀疏數(shù)組來保存。

處理方法是:

第一行記錄數(shù)組一共有幾行幾列和不同值的個數(shù)；而后記錄每行不同

值的位置與實際值

環(huán)形隊列

通過取模的方式實現(xiàn)。尾索引的下一個為頭索引時表示隊列滿

雙向鏈表

prev,next

單向環(huán)形鏈表

(約瑟夫環(huán))

先創(chuàng)建一個節(jié)點，讓first指向自己，形成環(huán)形；后面每創(chuàng)建一個新

節(jié)點，就將其加入到鏈表中(first.next=new;new.next=first)o

棧

先進(jìn)后出結(jié)構(gòu)，入棧push(top++),出棧pop(top-)[poll取空不

報錯]

常見排序算法

插入排序

直接插入排序

希爾排序

選擇排序

簡單選擇排序

堆排序

交換排序

冒泡排序

快速排序

歸并排序

基數(shù)排序

內(nèi)排序：所有排序操作都在內(nèi)存完成

外排序：由于數(shù)據(jù)太大，需要把數(shù)據(jù)放在磁盤，通過磁盤和內(nèi)存的數(shù)

據(jù)傳輸才能進(jìn)行

交換排序-冒泡排序

重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果它們的順序錯

誤就把它們交換過來。

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++){〃趟

數(shù)是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

交換排序?快速排序

通過一趟排序?qū)⒋庞涗浄指舫瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)

鍵字均比另一部分的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，

以達(dá)到整個序列有序。

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;〃左下標(biāo)

intr=right;〃右下標(biāo)

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

選擇排序

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

位置；再從剩余未排序元素中繼續(xù)尋找最小(大)元素，然后放到已排序

序列的末尾。

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

堆排序

也是一種選擇排序，也是一種完全二叉樹：每個節(jié)點的值都大于或等

于其左右孩子節(jié)點的值，稱為大頂堆；小于等于稱為小頂堆。

插入排序

通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描,

找到相應(yīng)位置并插入。

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數(shù)組的當(dāng)前索引

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數(shù)組拷貝到arr

t=0;

inttempLeft=left;

while(tempLeft<=right){

arr[tempLeft]=temp[t];

t+=1;

tempLeft+=1;

}

}o

基數(shù)排序

桶排序一種，將整數(shù)按照位數(shù)切割，然后按每個位數(shù)分別比較(消耗

存儲,容易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);

//查找多個值的情況。

插值查找

類似于二分，不同的是每次從自適應(yīng)mid處開始查找，適用于連續(xù)且

量大的數(shù)據(jù)

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

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

注意需要判斷findVal過大或過小越界的情況。

樹結(jié)構(gòu)

數(shù)組、鏈表和二叉樹的優(yōu)缺點略

二叉樹

每個節(jié)點最有只有兩個子節(jié)點(左節(jié)點、右節(jié)點)

滿二叉樹、完全二叉樹

前序遍歷：先輸出父節(jié)點，再遍歷左子樹和右子樹

中序遍歷：先遍歷左子樹，再輸出父節(jié)點，再遍歷右子樹

后序遍歷：先遍歷左子樹，再遍歷右子樹，再輸出父節(jié)點

二叉排序樹

左邊比根節(jié)點小，右邊比根節(jié)點大

二叉排序樹既可以保證數(shù)據(jù)的檢索速度，同時也可以保證增刪改的速

度

問題：極端情況，插入有序會退化成鏈表

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,

實現(xiàn)方式：旋轉(zhuǎn)（左、右、雙旋轉(zhuǎn)（左+右））。Java中的TreeSet底層用

的就是紅黑樹。

左旋轉(zhuǎn)：

NodenewNode=newNode（value）;

newNode.left=left;

newNode.right=right,left;

value=right.value;

right=right.right;

left=newNode;0

B樹

B+樹

在B樹的基礎(chǔ)上改造，它的數(shù)據(jù)都在葉子節(jié)點，同時葉子節(jié)點之間還

加了指針形成鏈表

由于所有數(shù)據(jù)都在葉子結(jié)點，不用跨層，同時由于有鏈表結(jié)構(gòu)，只需

要找到首尾，通過鏈表就能把所有數(shù)據(jù)取出來了

一般用于數(shù)據(jù)庫索引（如果只取一條數(shù)據(jù)，Hash快）。

赫夫曼樹

赫（哈Huffman）夫曼樹帶權(quán)路徑長度最小的二叉樹，也稱最優(yōu)二叉

樹

創(chuàng)建一個赫夫曼樹

應(yīng)用：通訊領(lǐng)域信息傳輸、文件壓縮解壓，赫夫曼編碼(按照各個字

符出現(xiàn)的次數(shù)進(jìn)行編碼)

遞歸與分治

遞歸

當(dāng)程序執(zhí)行到一個方法時，就會獨立開辟一個空間(棧)，每個空間

中的局部變量也是獨立的。

注意遞歸調(diào)用處前后代碼的執(zhí)行順序

publicstaticvoidshow(intn){

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

if(n>2){

show(n-1);

}

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

)o

分治

待解決復(fù)雜的問題能夠簡化為幾個若干個小規(guī)模相同的問題，然后逐

步劃分，達(dá)到易于解決的程度。應(yīng)用：階乘、斐波納契數(shù)列、漢諾塔問題、

棋盤覆蓋、找出偽幣、求最值

案例一?漢諾塔

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

動態(tài)規(guī)劃

動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中,

可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)

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

與分治法不同的是，分解得到的子問題是非獨立的，即下一個子階段

的求解是建立在上一個子階段的解的基礎(chǔ)上。

案例一?有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

案例二-給定一個矩陣，從左上角開始每次只能向右走或者向下走，

最后達(dá)到右下角的位置，路徑中所有數(shù)字累加起來就是路徑和，返回所有

路徑的最小路徑和

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

}

〃優(yōu)化解法

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

貪心算法

在每一