數(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)=Ｏ(f(n)),稱Ｏ(f(n))為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。常見的時間復(fù)雜度有：常數(shù)階O(1),對數(shù)[logarithmic]階O(log2n),線性階O(n),線性對數(shù)階O(nlog2n),平方階O(n2),立方階O(n3),k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。算法時間復(fù)雜度由小到大依次為：Ο(1)＜Ο(log2n)[二分]＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)。求解算法的時間復(fù)雜度的具體步驟是：找出算法中的基本語句；算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。計算基本語句的執(zhí)行次數(shù)的數(shù)量級；只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，這就意味著只要保證基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長率。用大O記號表示算法的時間性能。將基本語句執(zhí)行次數(shù)的數(shù)量級放入大Ο記號中?？臻g復(fù)雜度比較常用的有：O(1)、O(n)、O(n2)如果算法執(zhí)行所需要的臨時空間不隨著某個變量n的大小而變化，即此算法空間復(fù)雜度為一個常量，可表示為O(1)如果新建一個數(shù)組，這個數(shù)據(jù)占用的大小為n，雖然有循環(huán)，但沒有再分配新的空間，因此，空間復(fù)雜度主要看數(shù)組大小即可，即S(n)=O(n)。數(shù)據(jù)結(jié)構(gòu)線性與非線性線性：數(shù)組(Array)、鏈表(LinkedList)、棧(Stack)、隊(duì)列(Queue)非線形：多維數(shù)組、樹結(jié)構(gòu)、圖結(jié)構(gòu)常見數(shù)據(jù)結(jié)構(gòu)稀疏數(shù)組場景：解壓縮當(dāng)一個數(shù)組中大部分元素為0，或者為同一個值的數(shù)組時，可以使用稀疏數(shù)組來保存。處理方法是：第一行記錄數(shù)組一共有幾行幾列和不同值的個數(shù)；而后記錄每行不同值的位置與實(shí)際值環(huán)形隊(duì)列通過取模的方式實(shí)現(xiàn)。尾索引的下一個為頭索引時表示隊(duì)列滿雙向鏈表prev,next單向環(huán)形鏈表(約瑟夫環(huán))先創(chuàng)建一個節(jié)點(diǎn)，讓first指向自己，形成環(huán)形；后面每創(chuàng)建一個新節(jié)點(diǎn)，就將其加入到鏈表中(first.next=new;new.next=first)。棧先進(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ù)是len-1-iif(arr[j+1]<arr[j]){temp=arr[j+1];arr[j+1]=arr[j];arr[j]=temp;}}}System.out.println(Arrays.toString(arr));}。交換排序·快速排序通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(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.println(Arrays.toString(arr));}privatevoidsort(int[]arr,intleft,intright){intl=left;//左下標(biāo)intr=right;//右下標(biāo)intpivot=arr[(left+right)/2];//中軸值inttemp=0;while(l<r){while(arr[l]<pivot){//在pivot左邊找l+=1;}while(arr[r]>pivot){//在pivot右邊找r-=1;}if(l>=r){break;}//交換temp=arr[l];arr[l]=arr[r];arr[r]=temp;if(arr[l]==pivot){//前移r-=1;}if(arr[r]==pivot){//后移l+=1;}}if(l==r){l+=1;r-=1;}if(left<r){//向左遞歸sort(arr,left,r);}if(right>l){//向右遞歸sort(arr,l,right);}}。選擇排序首先在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置；再從剩余未排序元素中繼續(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]){//找到最?。ɑ蜃畲螅﹎ini=j;}}temp=arr[i];arr[i]=arr[mini];arr[mini]=temp;}System.out.println(Arrays.toString(arr));}。堆排序也是一種選擇排序，也是一種完全二叉樹：每個節(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)的值，稱為大頂堆；小于等于稱為小頂堆。插入排序通過構(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.println(Arrays.toString(arr));}。其他：希爾排序，縮小增量排序歸并排序?qū)⒍鄠€有序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序。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.println(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ù)組拷貝到arrt=0;inttempLeft=left;while(tempLeft<=right){arr[tempLeft]=temp[t];t+=1;tempLeft+=1;}}?；鶖?shù)排序桶排序一種，將整數(shù)按照位數(shù)切割，然后按每個位數(shù)分別比較（消耗存儲，容易OOM）案例一·文件修改時間排序案例二·文件名稱排序常見查找算法二分查找publicstaticvoidmain(String[]args){int[]arr=newint[]{1,4,5,7,8,12,45,67,99,105};System.out.println(biSearch(arr,99));}publicstaticintbiSearch(int[]arr,intnum){intstart=0;intend=arr.length-1;intmid;while(start<=end){System.out.println("*");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;intmidVal=arr[mid];if(midVal==num){returnmid;}elseif(midVal>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)缺點(diǎn)略二叉樹每個節(jié)點(diǎn)最有只有兩個子節(jié)點(diǎn)（左節(jié)點(diǎn)、右節(jié)點(diǎn)）滿二叉樹、完全二叉樹前序遍歷：先輸出父節(jié)點(diǎn)，再遍歷左子樹和右子樹中序遍歷：先遍歷左子樹，再輸出父節(jié)點(diǎn)，再遍歷右子樹后序遍歷：先遍歷左子樹，再遍歷右子樹，再輸出父節(jié)點(diǎn)二叉排序樹左邊比根節(jié)點(diǎn)小，右邊比根節(jié)點(diǎn)大二叉排序樹既可以保證數(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);}}。紅黑樹平衡二叉樹AVL的一種，降低樹的高度，樹高最大最小之差不超過1，實(shí)現(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;。B樹B+樹在B樹的基礎(chǔ)上改造，它的數(shù)據(jù)都在葉子節(jié)點(diǎn)，同時葉子節(jié)點(diǎn)之間還加了指針形成鏈表由于所有數(shù)據(jù)都在葉子結(jié)點(diǎn)，不用跨層，同時由于有鏈表結(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í)行到一個方法時，就會獨(dú)立開辟一個空間（棧），每個空間中的局部變量也是獨(dú)立的。注意遞歸調(diào)用處前后代碼的執(zhí)行順序publicstaticvoidshow(intn){System.out.println("n1:"+n);//10->2if(n>2){show(n-1);}System.out.println("n2:"+n);//2->10}。分治待解決復(fù)雜的問題能夠簡化為幾個若干個小規(guī)模相同的問題，然后逐步劃分，達(dá)到易于解決的程度。應(yīng)用：階乘、斐波納契數(shù)列、漢諾塔問題、棋盤覆蓋、找出偽幣、求最值案例一·漢諾塔publicstaticvoidmain({move(5,"A柱","B柱","C柱");}publicstaticvoidmove(intnum,Stringa,Stringb,Stringc){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,Strings1,Strings2){System.out.println("第"+num+"個塔從"+s1+"到"+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,0,1,1,0,1,1,1,1},{1,0,0,1,1,1,1,1,1},{1,0,0,0,1,1,1,1,1},{1,1,1,0,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.println("原來的地圖11*9");for(inti=0;i<11;i++){for(intj=0;j<9;j++){System.out.print(map[i][j]+"");}System.out.println(;}//1,1是起點(diǎn)9,7是終點(diǎn)setWay(map,1,1);System.out.println("走過的地圖");for(inti=0;i<11;i++){for(intj=0;j<9;j++){if(map[i][j]==2){System.out.format("\33[32;1m"+map[i][j]+"\33[0m");}else{System.out.print(map[i][j]+"");}}System.out.println(;}}//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;}}}。動態(tài)規(guī)劃動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解，使用填表的方式。與分治法不同的是，分解得到的子問題是非獨(dú)立的，即下一個子階段的求解是建立在上一個子階段的解的基礎(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.println(;System.out.println(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];}。案例二·給定一個矩陣，從左上角開始每次只能向右走或者向下走，最后達(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.println("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;i1<steps.length;i1++){System.out.print(steps[i][i1]+"");}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];//每一行的最左邊f(xié)or(intj=1;j<col;j++){steps[j]=Math.min(steps[j-1]+arr[i][j],steps[j]+arr[i][j]);}}System.out.prin