一、常見算法-01-基本、二分、插值和斐波那契查找

1、基本查找/順序查找

需求1：定義一個方法利用基本查找，查詢某個元素是否存在

數據如下：{131，127，147，81，103，23，7，79}

需求2：定義一個方法利用基本查找，查詢某個元素在數組中的索引

要求：不需要考慮數組中元素是否重復

需求3：定義一個方法利用基本查找，查詢某個元素在數組中的索引

要求：需要考慮數組中元素是否重復

數據如下：{131，127，147，81，103，23，7，79，81}

2、二分查找/折半查找

• 前提條件：數組中的數據必須是有序的
• 核心邏輯：每次排除一般的查找范圍

練習?

需求：定義一個方法利用二分查找，查詢某個元素在數組中的索引

數據如下：?{7,23,79,81,103,127,131,147}

?

總結：

3、插值查找（二分查找改進）

?

4、斐波那契查找（二分查找改進）

5、總結：

?

二、常見算法-02-分塊,分塊查找，哈希查找

1、分塊查找?

??練習?

分塊查找核心思想：塊內無序，塊間有序實現步驟：1.創建數組blockArr存放每一個塊對象的信息2.先查找blockArr確定要查找的數據屬于哪一塊3.再單獨遍歷這一塊數據即可

2、擴展的分塊查找（無規律的數據）?

3、擴展的分塊查找（查找的過程中還需要添加數據）?

三、常見算法-03-冒泡排序和選擇排序

1、冒泡排序

冒泡排序：相鄰兩個數據兩兩比較，小的放前面，大的放后面。

?

2、選擇排序

選擇排序：從0索引開始，拿著每一個索引商的元素跟后面的元素一次比較，小的放前面，大的放后面，一次類推。?

?

?

四、常見算法-04-插入排序和遞歸算法

1、插入排序

將0索引的元素到N索引的元素看做是有序的，把N+1索引的元素到最后一個當成是無序的。
遍歷無序的數據，將遍歷到的元素插入有序序列中適當的位置，如遇到相同數據，插在后面。
N的范圍：0~最大索引

?

2、遞歸算法?

遞歸值得是方法中調用方法本身的現象。

遞歸算法的作用

• 把一個復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解。

• 遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算

書寫遞歸的兩個核心：

• 找出口:什么時候不再調用方法。

• 找規則：如何把大問題變成規模較小的問題

遞歸的注意點：遞歸一定要有出口，否則就會出現內存溢出

練習——遞歸求和

需求：求1~100之間的和?

練習——遞歸求階乘

?需求：用遞歸求5的階乘，并把結果在控制臺輸出

5！= 5*4*3*2*1? ? ? ? ? ? ? ? 100！= 100*99*98*97*96....*2*1;

五、常見算法-05-快速排序

練習——快速排序

第一輪：以e索引的數字為基準數，確定基準數在數組中正確的位置。
比基準數小的全部在左邊，比基準數大的全部在右邊。
后面以此類推。

//結果：1，2，3，4，5，6，7，8，9，10

?總結

六、Arrays?

?

1、Lambda表達式的標準格式

Lambda表達式是JDK8開始后的一中新語法形式。

? ? ? ? ?( ) ->{? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }

()對應著方法的形參 ->? 固定格式 {}? 對應著方法的方法體

函數式編程

函數式編程（Functional programming）是一種思想特點。
函數式編程思想，忽略面向對象的復雜語法，強調做什么，而不是誰去做。
而我們要學習的Lambda表達式就是函數式思想的體現。

2、總結：

1、Lambda表達式的基本作用？
? ? ? ? ? ? ? ? ? ? ?簡化函數式接口的匿名內部類的寫法。
2、Lambda表達式有什么使用前提？
? ? ? ? ? ? ? ? ? ? ?必須是接口的匿名內部類，接口中只能有一個抽象方法
3、Lambda的好處？
? ? ? ? ? ? ? ? ? ? ? Lambda是一個匿名函數
? ? ? ? ? ? ? ? ? ? ? 我們可以把Lambda表達式理解為是一段
? ? ? ? ? ? ? ? ? ? ? 可以傳遞的代碼，它可以寫出更簡潔、更靈活的代碼，作為一種更緊
? ? ? ? ? ? ? ? ? ? ? 湊的代碼風格，使Java語言表達能力得到了提升。?

3、Lambda表達式的省略寫法

省略核心：可推導，可省略

• 參數類型可以省略不寫。
• 如果只有一個參數，參數類型可以省略，同時（)也可以省略。
• 如果Lambda表達式的方法體只有一行，大括號，分號，return可以省略不寫，需要同時省略。?

?七、五道算法題

練習1——Lambda表達式簡化Comparator接口的匿名形式

定義數組并存儲一些字符串，利用Arrays中的sort方法進行排序
要求:? ? ?按照字符串的長度進行排序，短的在前面，長的在后面。
? ? ? ? ? ? ? ? ? ? （暫時不比較字符串里面的內容）

?練習2——按照要求進行排序

定義數組并存儲一些女朋友對象，利用Arrays中的sort方法進行排序
要求1：屬性有姓名、年齡、身高。
要求2：按照年齡的大小進行排序，年齡一樣，按照身高排序，身高一樣按照姓名的字母進行排序。
（姓名中不要有中文或特殊字符，會涉及到后面的知識)

創建Text類

或者用

??練習3——不死神兔

有一個很有名的數學邏輯題叫做不死神兔問題，有一對兔子，從出生后第三個月起每個月都生一對兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問第十二個月的兔子對數為多少？?

規律：從第三個數據開始，是前兩個數據和? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（斐波那契數列）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?練習4——猴子吃桃子

有一堆桃子，猴子第一天吃了其中的一半，并多吃了一個！以后每天猴子都吃當前剩下來的一半，然后再多吃一個，第10天的時候（還沒吃），發現只剩下一個桃子了，請問，最初總共多少個桃子?

練習5——爬樓梯

可愛的小明特別喜歡爬樓梯，他有的時候一次爬一個臺階，有的時候一次爬兩個臺階。
如果這個樓梯有20個臺階，小明一共有多少種爬法呢?