常見算法和Lambda

常見算法

查找算法

基本查找（順序查找）

核心:從0索引開始挨個往后查找

• 需求定義：一個方法利用基本查找，查找某個元素是否存在
• 數據如下：{131,127,147,81,103,23,7,79}

package com.example.demo;public class Text{public static void main(String[] args) {int [] arr = {131,127,147,81,103,23,7,79};int number = 81;System.out.println(basicSearch(arr,number));}private static boolean basicSearch(int[] arr, int number) {for (int i = 0; i < arr.length; i++) {if(arr[i] == number){return true;}}return false;}
}

• 需求：定義一個方法利用基本查找，查詢某個元素在數組中的索引
• 要求：不需要考慮數組中元素是否重復

package com.example.demo;public class Text{public static void main(String[] args) {int [] arr = {131,127,147,81,103,23,7,79};int number = 81;System.out.println(basicSearch(arr,number));}private static int basicSearch(int[] arr, int number) {for (int i = 0; i < arr.length; i++) {if(arr[i] == number){return i;}}return -1;}
}

• 需求：定義一個方法利用基本查找，查詢某個元素在數組中的索引
• 要求：需要考慮數組中元素有重復的可能性

package com.example.demo;import java.util.ArrayList;public class Text{public static void main(String[] args) {int [] arr = {131,127,147,81,103,23,7,79,81};int number = 81;System.out.println(basicSearch(arr,number));}private static ArrayList<Integer> basicSearch(int[] arr, int number) {ArrayList<Integer> list = new ArrayList<>();for (int i = 0; i < arr.length; i++) {if(arr[i] == number){list.add(i);}}return list;}
}

二分查找/折半查找

前提條件：數組中的數據必須是有序的

核心思想：每次排除一半的查找范圍

• min和max表示當前要查找的范圍
• mid是在min和max中間的
• 如果要查找的元素在mid的左邊，縮小范圍時，min不變，max等于mid減一
• 如果要查找的元素在mid的右邊，縮小范圍，max不變，min等于mid加一

package com.example.demo;public class Text{public static void main(String[] args) {
//        需求：定義一個方法利用二分查找，查詢某個元素在數組中的索引
//        數據如下：{7,23,79,81,103,127,131,147}int [] arr = {7,23,79,81,103,127,131,147};System.out.println(binarySearch(arr,131));}private static int binarySearch(int[] arr, int number) {
//       1.定義兩個變量記錄要查找的范圍int min = 0;int max = arr.length-1;//        2.利用循環不斷地去找要查找的數據while (true){if(min > max){return -1;}//            3.找到min和max的中間位置int mid = (min + max)/2;
//            4.拿著mid指向的元素跟要查找的元素進行比較if (arr[mid] > number){//4.1 number在mid的左邊// min不變，max = min -1；max = mid - 1;}else if(arr[mid] < number){//4.2 number子啊mid的右邊//max不變，min = mid + 1min = mid + 1;}else{//4.3 number跟mid指向的元素一樣//找到了return mid;}}}
}

插值查找

數組中的值，分布比較均勻。

斐波那契查找

分塊查找

• 前一塊中的最大數據，小于后一塊中所有的數據（塊內無序，塊間有序）
• 塊數數量一般等于數字的個數開根號。比如：16個數字一般分為4塊左右

核心思路：先確定要查找的元素在哪一塊，然后在塊內挨個查找。

package com.example.demo;public class Text{public static void main(String[] args) {int[] arr = {16,5,9,12,21,18,32,23,37,26,45,34,50,48,61,52,73,66};//創建三個的塊對象Block b1 = new Block(21,0,5);Block b2 = new Block(45,6,11);Block b3 = new Block(73,12,17);//        定義數組用來管理三個塊的對象（索引表）Block[] blockArr = {b1,b2,b3};//        定義一個變量用來記錄要查找的元素int number = 30;//        調用方法，傳遞索引表，數組，要查找的元素int index = getIndex(blockArr,arr,number);//        打印System.out.println(index);}//    利用分塊查找的原理，查詢number的索引
//    1.確定number在索引表的位置private static int getIndex(Block[] blockArr, int[] arr, int number) {//1.確定number是在哪一塊中的int indexBlock = findIndexBlock(blockArr,number);if(indexBlock == -1){//表示number不在數組當中return -1;}//        2.獲取這一塊的起始索引和結束索引int startIndex = blockArr[indexBlock].getStartIndex();int endIndex = blockArr[indexBlock].getEndIndex();//        3.遍歷for (int i = startIndex; i <= endIndex; i++) {if(arr[i] == number){return i;}}return -1;}//    定義一個方法，用來確定number在哪一塊public static int findIndexBlock(Block[] blockArr,int number){//從0索引開始遍歷blockArr，如果number小于max，那么就表示number是在這一塊當中的。for (int i = 0; i < blockArr.length; i++) {if(number <= blockArr[i].getMax()){return i;}}return -1;}}class Block{private int max;private int startIndex;private int endIndex;public Block() {}public Block(int max, int startIndex, int endIndex) {this.max = max;this.startIndex = startIndex;this.endIndex = endIndex;}public int getMax() {return max;}public void setMax(int max) {this.max = max;}public int getStartIndex() {return startIndex;}public void setStartIndex(int startIndex) {this.startIndex = startIndex;}public int getEndIndex() {return endIndex;}public void setEndIndex(int endIndex) {this.endIndex = endIndex;}@Overridepublic String toString() {return "Block{" +"max=" + max +", startIndex=" + startIndex +", endIndex=" + endIndex +'}';}
}

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

package com.example.demo;public class Text{public static void main(String[] args) {int[] arr = {27,22,30,40,36,13,19,16,20,7,10,43,50,48};//創建三個的塊對象Block b1 = new Block(22,40,0,4);Block b2 = new Block(13,20,5,8);Block b3 = new Block(7,10,9,10);Block b4 = new Block(43,50,11,13);//        定義數組用來管理三個塊的對象（索引表）Block[] blockArr = {b1,b2,b3,b4};//        定義一個變量用來記錄要查找的元素int number = 48;//        調用方法，傳遞索引表，數組，要查找的元素int index = getIndex(blockArr,arr,number);//        打印System.out.println(index);}//    利用分塊查找的原理，查詢number的索引
//    1.確定number在索引表的位置private static int getIndex(Block[] blockArr, int[] arr, int number) {//1.確定number是在哪一塊中的int indexBlock = findIndexBlock(blockArr,number);if(indexBlock == -1){//表示number不在數組當中return -1;}//        2.獲取這一塊的起始索引和結束索引int startIndex = blockArr[indexBlock].getStartIndex();int endIndex = blockArr[indexBlock].getEndIndex();//        3.遍歷for (int i = startIndex; i <= endIndex; i++) {if(arr[i] == number){return i;}}return -1;}//    定義一個方法，用來確定number在哪一塊public static int findIndexBlock(Block[] blockArr,int number){//從0索引開始遍歷blockArr，如果number小于max，大于min，那么就表示number是在這一塊當中的。for (int i = 0;i < blockArr.length; i++) {if(number <= blockArr[i].getMax() && number >= blockArr[i].getMin()){return i;}}return -1;}}class Block{private int max;private int min;private int startIndex;private int endIndex;public Block() {}public Block(int min,int max, int startIndex, int endIndex) {this.min = min;this.max = max;this.startIndex = startIndex;this.endIndex = endIndex;}public int getMin() {return min;}public void setMin(int min) {this.min = min;}public int getMax() {return max;}public void setMax(int max) {this.max = max;}public int getStartIndex() {return startIndex;}public void setStartIndex(int startIndex) {this.startIndex = startIndex;}public int getEndIndex() {return endIndex;}public void setEndIndex(int endIndex) {this.endIndex = endIndex;}@Overridepublic String toString() {return "Block{" +"max=" + max +", min=" + min +", startIndex=" + startIndex +", endIndex=" + endIndex +'}';}
}

常見排序算法

冒泡排序

• 相鄰的數據兩兩比較，小的放前面，大的放后面。
• 第一輪循環結束，最大值已經找到，在數組的最右邊。第二輪可以少循環一次，后面以此類推。
• 如果數組中有n個數據，總共我們只要執行n-1輪的代碼就可以。

package com.example.demo;public class Text {public static void main(String[] args) {
//        1.定義數組int[] arr = {2,4,5,3,1};//        2.利用冒泡排序將數組的數據變成1,2,3,4,5
//        外循環：表示我要執行多少輪，如果有n個數據，那么執行n-1輪for (int i = 0; i < arr.length-1; i++) {
//            內循環：每一輪中我如何比較數據并找到當前的最大值//-1:為了防止索引越界//-i:提高效率，每一輪執行的次數應該比上一輪少一次。for (int j = 0; j < arr.length-1 - i; j++) {if(arr[j] > arr[j+1]){int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}for (int i = 0; i < arr.length; i++) {System.out.println(arr[i] + " ");}}
}

選擇排序

• 從0索引開始，拿著每一個索引上的元素跟后面的元素依次比較，小的放前面，大的放后面，以此類推。
• 第一輪結束后，最小的數據已經確定

package com.example.demo;public class Text {public static void main(String[] args) {
//        1.定義數組int[] arr = {2, 4, 5, 3, 1};//        2.利用選擇排序讓數組變成1 2 3 4 5for (int i = 0; i < arr.length - 1; i++) {for (int j = i + 1; j < arr.length; j++) {if(arr[i] > arr[j]){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

插入排序

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

package com.example.demo;public class Text {public static void main(String[] args) {
//        1.定義數組int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};//        2.找到無序的那一組數組是從哪個索引開始的int startIndex= -1;for (int i = 0; i < arr.length; i++) {if(arr[i] > arr[i+1] ){startIndex = i + 1;break;}}//        3.遍歷從startIndex開始到最后一個元素，依次得到無序的那一組數據中的每一個元素for (int i = startIndex; i < arr.length; i++) {
//            記錄當前要插入數據的索引int j = i;while (j > 0 && arr[j] < arr[j-1]){
//                交換位置int temp = arr[j];arr[j] = arr[j-1];arr[j-1] = temp;j--;}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

快速排序

遞歸

方法中調用方法本身的現象

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

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

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

package com.example.demo;public class Text {public static void main(String[] args) {//求1~100之間的和System.out.println(getSum(100));}public static int getSum(int number){if(number == 1){return 1;}//        如果number不是1？return number + getSum(number-1);}
}

package com.example.demo;public class Text {//求5的階乘public static void main(String[] args) {System.out.println(getFactorial(5));}public static int getFactorial(int number){if(number == 1){return 1;}
//        如果number不是1？return number * getFactorial(number-1);}
}

快速排序

第一輪：把0索引的數字作為基準數，確定基準數在數組中正確的位置。

比基準數小的全部在左邊，比基準數大的全部在右邊。

package com.example.demo;public class Text {public static void main(String[] args) {int[] arr = {6,1,2,7,9,3,4,5,10,8};quickSort(arr,0,arr.length-1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}public static void quickSort(int[] arr,int i,int j){
//        定義兩個變量記錄要查找的范圍int start= i;int end = j;if(start > end){return;}//        記錄基準數int baseNumber = arr[i];
//        利用循環找到要交換的數字while (start != end) {
//            利用end，從后往前開始找，找比基準數小的數字while (true){if(end <= start || arr[end] < baseNumber){break;}end--;}
//            利用start，從前往后找，找比基準數大的數字while (true){if(end <= start || arr[start] > baseNumber){break;}start++;}
//            把end和start指向的元素進行交換int temp = arr[start];arr[start] = arr[end];arr[end] = temp;}
//    當start和end直系那個了同一個元素的時候，那么上面的循環就會結束
//    表示已經找到了基準數在數組中應存入的位置
//    基準數歸位int temp = arr[i];arr[i] = arr[start];arr[start] = temp;//        確定6左邊的范圍，重復剛剛所做的事情quickSort(arr,i,start-1);
//        確定6右邊的范圍，重復剛剛所做的事情quickSort(arr,start+1,j);}}

Arrays

操作數組的工具類

Lambda表達式

函數式編程

是一種思想特點。函數式編程思想忽略面向對象的復雜語法，強調做什么，而不是誰去做。