Java常見八股-（6.算法+實施篇）

Java常見八股-（1.Java基礎篇）

Java常見八股-（2.Java高級篇）

Java常見八股-（3.MySQL篇）

Java常見八股-（4.前端篇）

Java常見八股-（5.框架篇）

一、算法與數據結構

1.?算法

1.1你知道哪些算法，說下你了解的排序算法

1.2談一下遞歸

1.3棧和隊列的區別

1.4二叉排序樹了解嗎

1.5在堆中查找一個數字用什么方法可以快速查到

1.6遞歸和迭代的區別

2.?數據結構

2.1什么是堆和棧，說一下堆棧的區別？

2.2用過什么樹結構

2.3?B樹，B+樹哪個用的比較多

二、實施

1.?Linux

1.1談一下對Linux的了解

1.2?Linux如何查看文件內容

1.3 Linux如何刪除文件內容

1.4?Linux切換目錄命令

1.5?Linux創建文件命令

1.6?linux中搜索文件命令

1.7?Linux的部署

1.8?linux 中 vim

1.9?Linux文件分頁查看指令

一、算法與數據結構

1.?算法

1.1你知道哪些算法，說下你了解的排序算法

1、冒泡排序（Bubble Sort）

冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

2、選擇排序（Selection Sort）

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

3、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。

4、希爾排序（Shell Sort）

1959年Shell發明，第一個突破O(n2)的排序算法，是簡單插入排序的改進版。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。

5、歸并排序（Merge Sort）

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。

6、快速排序（Quick Sort）

快速排序的基本思想：通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

7、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

8、計數排序（Counting Sort）

計數排序不是基于比較的排序算法，其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

9、桶排序（Bucket Sort）

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的確定。桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續使用桶排序進行排）。

10、基數排序（Radix Sort）

基數排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。

1.2談一下遞歸

(1) 遞歸就是在過程或函數里調用自身。

(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

(3) 遞歸算法解題通常顯得很簡潔，但運行效率較低。所以一般不提倡用遞歸算法設計程序。

(4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。

1.3棧和隊列的區別

棧（Stack）和隊列（Queue）是兩種常見的線性數據結構.

主要區別：

操作原則：棧遵循后進先出（LIFO），而隊列遵循先進先出（FIFO）。

操作位置：棧的操作只在棧頂進行，而隊列的插入操作在隊尾進行，刪除操作在隊頭進行。

應用場景：棧常用于處理需要反向處理的數據運算，如遞歸調用和表達式求值；隊列則更多用于消息傳遞和任務調度等場景。

1.4二叉排序樹了解嗎

?二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree）或二叉搜索樹，是一種數據結構，主要用于存儲數據并支持高效的查找、插入和刪除操作??。

二叉排序樹是一種特殊的二叉樹，滿足以下性質：

?空樹?：若左子樹不空，則左子樹上所有結點的值均小于根結點的值。
?右子樹?：若右子樹不空，則右子樹上所有結點的值均大于根結點的值。
?遞歸性質?：左、右子樹也分別為二叉排序樹?

1.5在堆中查找一個數字用什么方法可以快速查到

堆排序

1.6遞歸和迭代的區別

定義和結構

?遞歸?：遞歸是一種通過函數自己調用自己的編程技巧。它通常將一個大問題分解為更小的子問題，通過不斷調用自身來解決。遞歸算法包括遞歸定義和基本情況，遞歸函數會反復調用自身，每次處理一個子問題，直到達到基本情況為止。?
?迭代?：迭代是通過循環結構重復執行某段代碼，每次迭代使用上一次的結果作為下一次的初始值。迭代不需要函數調用棧空間，因此通常比遞歸更高效。?

時間復雜度

?遞歸?：遞歸的時間復雜度通常較高，因為每次函數調用都會增加棧空間的開銷。對于一些遞歸算法，隨著問題規模的增加，遞歸調用的次數可能會呈指數增長，導致時間復雜度急劇上升。?
?迭代?：迭代的時間復雜度通常較低，因為它不需要額外的函數調用開銷。迭代通過循環結構逐步逼近目標，適合處理大規模數據問題。?

適用場景

?遞歸?：遞歸適合解決那些可以分解成相似子問題的問題，如樹形結構的遍歷、計算斐波那契數列等。遞歸的優點在于代碼簡潔，但缺點是可能導致棧溢出，特別是在深度遞歸的情況下。?
?迭代?：迭代適合處理需要逐步逼近目標的問題，如計算數組中所有數字的和。迭代的優點是效率高、穩定，缺點是代碼可能較冗長，不易理解。?

優缺點總結

?遞歸?：
- ?優點?：代碼簡潔、易于理解。
- ?缺點?：效率較低，可能導致棧溢出，特別是在深度遞歸的情況下。?3
?迭代?：
- ?優點?：效率高、穩定，適合處理大規模數據問題。
- ?缺點?：代碼較長，不易理解

2.?數據結構

2.1什么是堆和棧，說一下堆棧的區別？

功能方面：堆是用來存放對象的，棧是用來執行程序的。

共享性：堆是線程共享的，棧是線程私有的。

空間大小：堆大小遠遠大于棧

2.2用過什么樹結構

在編程和計算機科學中，常用的樹結構包括二叉樹、二叉搜索樹、AVL樹、紅黑樹、B-tree等?。這些樹結構各有其特點和適用場景。

二叉樹

二叉樹是最基礎的樹結構之一，每個節點最多有兩個子節點，通常稱為左子節點和右子節點。二叉樹有多種類型，包括完全二叉樹、滿二叉樹和平衡二叉樹等。二叉樹在各種算法中都有廣泛應用，例如在堆排序和優先隊列中?12。

二叉搜索樹

二叉搜索樹是一種特殊的二叉樹，其每個節點的左子樹上的所有節點值都小于該節點的值，而右子樹上的所有節點值都大于該節點的值。這種結構使得在二叉搜索樹中查找、插入和刪除節點變得非常高效。AVL樹和紅黑樹都是自平衡的二叉搜索樹，它們通過保持樹的平衡來優化查找、插入和刪除操作的效率?13。

AVL樹

AVL樹是一種自平衡的二叉搜索樹，其每個節點的左子樹和右子樹的高度最多相差1。為了保持平衡，當插入或刪除節點時，可能需要通過旋轉節點來重新平衡樹。AVL樹的查找、插入和刪除操作的平均時間復雜度為O(log n)?13。

紅黑樹

紅黑樹也是一種自平衡的二叉搜索樹，每個節點都有顏色屬性，可以是紅色或黑色。紅黑樹的平衡特性保證了其高效的查找、插入和刪除操作。紅黑樹的性質包括根節點是黑色、每個葉節點（NIL或空節點）是黑色、紅色節點的子節點必須是黑色等?13。

B-tree

B-tree是一種多路平衡搜索樹，適用于磁盤或其他直接訪問輔助設備。B-tree能夠保持數據有序，并且廣泛應用于數據庫和文件系統中。

2.3?B樹，B+樹哪個用的比較多

B+樹

?B+樹是B樹的變體，是一種自平衡的樹數據結構，在數據庫系統中使用得更為廣泛，B+樹中所有實際數據都存儲在葉子節點中，而非葉子節點僅用于索引。這種設計使得B+樹在處理大量數據時能夠顯著提高查詢效率，尤其是在范圍查詢方面表現優異。B+樹的葉子節點之間通過鏈表連接，便于區間查找和遍歷。因此，B+樹廣泛應用于關系型數據庫的索引