查找算法
基本查找
从0索引开始查找
是否找到
package com.itheima.search;
import java.security.KeyStore;
public class BasicSearchDemo1 {
public static void main(String[] args) {
int[] arr = {23, 34, 54, 24, 43, 46};
int number = 43;
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.itheima.search;
import java.util.ArrayList;
public class BasicSearchDemo2 {
public static void main(String[] args) {
int[] arr = {23, 34, 54, 24, 43, 46, 34};
int number = 34;
int num = findNum(arr, number);
System.out.println(num);
ArrayList<Integer> num2 = findNumList(arr, number);
for (int i = 0; i < num2.size(); i++) {
if (i == num2.size() - 1) {
System.out.println(num2.get(i));
} else {
System.out.print(num2.get(i) + ", ");
}
}
}
private static int findNum(int[] arr, int number) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == number) {
return i;
}
}
return -1;
}
private static ArrayList<Integer> findNumList(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;
}
}
二分查找 / 折半查找
- 前提条件：数组中的数据有序
- 核心逻辑：每次排除一般的查找范围
package com.itheima.search;
import javax.sound.midi.MidiChannel;
public class BinarySearchDemo1 {
public static void main(String[] args) {
int[] arr = {23, 34, 54, 64, 75, 98};
int number = 34;
int search = binarySearch(arr, number);
System.out.println(search);
}
private static int binarySearch(int[] arr, int number) {
int min = 0;
int max = arr.length - 1;
while (true) {
if (min > max) {
return -1;
}
int mid = (min + max) / 2;
if (arr[mid] == number) {
return mid;
} else if (arr[mid] < number) {
min = mid + 1;
} else {
max = mid - 1;
}
}
}
}
插值查找
package com.itheima.search;
public class ChaZhiSearchDemo {
public static void main(String[] args) {
int[] arr = {12, 23, 45, 56, 76, 89, 98};
int number = 45;
int index = getIndex(arr, number);
System.out.println(index);
}
private static int getIndex(int[] arr, int number) {
int min = 0;
int max = arr.length - 1;
while (true) {
if (min > max) {
return -1;
}
int mid = min + ((number - arr[min]) / (arr[max] - arr[min]) * (max - min));
if (number < arr[mid]) {
max = mid - 1;
} else if (number > arr[mid]) {
min = mid + 1;
} else {
return mid;
}
}
}
}
斐波那契查找
二分查找、插值查找、斐波那契查找的异同
分块查找
package com.itheima.search;
public class BlockSearchDemo {
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};
int number = 37;
Block b1 = new Block(21, 0, 5);
Block b2 = new Block(45, 6, 11);
Block b3 = new Block(73, 12, 17);
Block[] blocks = {b1, b2, b3};
int index = getIndex(arr, blocks, number);
System.out.println(index);
}
private static int getIndex(int[] arr, Block[] blocks, int number) {
int index = getBlockIndex(blocks, number);
if (index == -1) {
return -1;
}
for (int i = blocks[index].getStartIndex(); i <= blocks[index].getEndIndex(); i++) {
if (number == arr[i]) {
return i;
}
}
return -1;
}
private static int getBlockIndex(Block[] blocks, int number) {
for (int i = 0; i < blocks.length; i++) {
if (number <= blocks[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;
}
/**
* 获取
* @return max
*/
public int getMax() {
return max;
}
/**
* 设置
* @param max
*/
public void setMax(int max) {
this.max = max;
}
/**
* 获取
* @return startIndex
*/
public int getStartIndex() {
return startIndex;
}
/**
* 设置
* @param startIndex
*/
public void setStartIndex(int startIndex) {
this.startIndex = startIndex;
}
/**
* 获取
* @return endIndex
*/
public int getEndIndex() {
return endIndex;
}
/**
* 设置
* @param endIndex
*/
public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}
public String toString() {
return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
}
}
扩展的分块查找（无规律的数据）
package com.itheima.search;
public class BlockSearchDemo1 {
public static void main(String[] args) {
int[] arr = {27,22,30,40,36,
13,19,16,20,
7,10,
43,50,48};
int number = 48;
Block1 b1 = new Block1(22,40,0,4);
Block1 b2 = new Block1(13,20,5,8);
Block1 b3 = new Block1(7,10,9,10);
Block1 b4 = new Block1(43,50,11,13);
Block1[] block1s = {b1, b2, b3, b4};
int index = getIndex(arr, block1s, number);
System.out.println(index);
}
private static int getIndex(int[] arr, Block1[] block1s, int number) {
int index = getBlockIndex(block1s, number);
if (index == -1) {
return -1;
}
for (int i = block1s[index].getStartIndex(); i <= block1s[index].getEndIndex(); i++) {
if (number == arr[i]) {
return i;
}
}
return -1;
}
private static int getBlockIndex(Block1[] block1s, int number) {
for (int i = 0; i < block1s.length; i++) {
if (number >= block1s[i].getMin() && number <= block1s[i].getMax()) {
return i;
}
}
return -1;
}
}
class Block1 {
private int min;
private int max;
private int startIndex;
private int endIndex;
public Block1() {
}
public Block1(int min, int max, int startIndex, int endIndex) {
this.min = min;
this.max = max;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
/**
* 获取
* @return min
*/
public int getMin() {
return min;
}
/**
* 设置
* @param min
*/
public void setMin(int min) {
this.min = min;
}
/**
* 获取
* @return max
*/
public int getMax() {
return max;
}
/**
* 设置
* @param max
*/
public void setMax(int max) {
this.max = max;
}
/**
* 获取
* @return startIndex
*/
public int getStartIndex() {
return startIndex;
}
/**
* 设置
* @param startIndex
*/
public void setStartIndex(int startIndex) {
this.startIndex = startIndex;
}
/**
* 获取
* @return endIndex
*/
public int getEndIndex() {
return endIndex;
}
/**
* 设置
* @param endIndex
*/
public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}
public String toString() {
return "Block{min = " + min + ", max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
}
}
哈希查找
排序算法
冒泡排序
package com.itheima.sort;
public class BubbleDemo1 {
public static void main(String[] args) {
int[] arr = {2, 4, 5, 3, 1};
for (int i = 0; i < arr.length -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.print(arr[i] + " ");
}
}
}
选择排序
package com.itheima.sort;
public class XuanZeSearchDemo {
public static void main(String[] args) {
int[] arr = {2, 4, 5, 3, 1};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
插入排序
package com.itheima.sort;
public class ChaRuSearchDemo {
public static void main(String[] args) {
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 首先找到无序的第一个索引即是38的索引
// 1. 先定义一个变量记录索引
int startIndex = -1;
// 2. 遍历数组得到无序索引
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] < arr[i + 1]) {
startIndex = i + 1;
break;
}
}
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.itheima.sort;
public class DiGuiDemo1 {
public static void main(String[] args) {
System.out.println(getSum(100));
}
public static int getSum(int number) {
if (number == 1) {
return 1;
}
return number + getSum(number - 1);
}
}
package com.itheima.sort;
public class DiGuiDemo2 {
public static void main(String[] args) {
System.out.println(getJi(5));
}
public static int getJi(int number) {
if (number == 1) {
return 1;
}
return number * getJi(number - 1);
}
}
快速排序
package com.itheima.sort;
public class QuickSortDemo {
public static void main(String[] args) {
int[] arr = {4,10,2,5,36,78,6,3};
int i = 0;
int j = arr.length - 1;
quickSort(arr,i ,j);
for (int k = 0; k < arr.length; k++) {
System.out.print(arr[k] + " ");
}
}
public static void quickSort(int[] arr, int i, int j) {
int start = i;
int end = j;
if (start > end) {
return;
}
while (end != start) {
while (end > start && arr[end] > arr[i]) {
end--;
}
while (end > start && arr[start] < arr[i]) {
start++;
}
int temp = arr[end];
arr[end] = arr[start];
arr[start] = temp;
}
int temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
quickSort(arr, i, start - 1);
quickSort(arr, start + 1, j);
}
}
标签：arr,JAVA,int,常见,number,算法,static,return,public From： https://blog.csdn.net/Ling_suu/article/details/142766170