前言
本文主要讲了常见的查找算法和排序算法，内容通俗易懂，相信各位小伙伴定会有一定的收获。
一、查找算法
1.1基本查找
基本查找也叫顺序查找，核心思想是从0下标开始挨个往后查找。
public class Test { public static void main(String[] args) { //算法：基本查找 //需求：定义一个方法利用基本查找判断一个元素是否存在 int[] arr = {12,89,24,26,100,215,48,94}; System.out.println(basicSearch(arr, 12)); } /** * 基本查找 * @param array 数组 * @param number 要查找的元素 * @return 元素是否存在 */ public static boolean basicSearch(int[] array,int number) { for (int i = 0; i < array.length; i++) { if(array[i] == number) { return true; } } return false; } }
练习1
定义一个方法，利用基本查找，查询某个元素在数组中的索引
要求：不需要考虑数组中元素是否重复
public static int basicSearchIndex(int[] array,int number) { for (int i = 0; i < array.length; i++) { if(array[i] == number) { return i; } } return -1; }
练习2
定义一个方法，利用基本查找，查询某个元素在数组中的索引
要求：需要考虑数组中元素是否重复
public static ArrayList<Integer> basicSearchIndex2(int[] array,int number) { ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < array.length; i++) { if(array[i] == number) { list.add(i); } } return list; }
1.2二分查找/折半查找
前提：数组arr中的数据必须是有序的
核心：每次排除一半的查找范围
定义三个变量：min,max,mid
min：表示每次查找的0下标
max：表示每次查找的最大下标
mid：表示每次查找的数组的范围的中间值下标，即mid = (min + max)/2
要查找的数：num
在进行查找时，每次查找将要查找的数与mid下标的元素进行比较
1.若arr[mid] > num,则max = mid - 1,mid = (min + max)/2,继续查找
2.若arr[mid] < num,则min = mid + 1,mid = (min + max)/2,继续查找
直到arr[mid] == num 时查找结束。
查找不到的情况：
若要查找的数在数组中不存在，这时代码的逻辑是min>max（或max
public static int binarySearch(int[] array,int number) { //1.定义变量记录范围 int min = 0; int max = array.length - 1; //2.利用循环查找数据 while (true) { if(min>max) { return -1; } //3.找到min和max的中间位置mid int mid = (min + max) >>> 1; //4.比较 //4.1 number在mid左边 if(array[mid] > number) { max = mid - 1; mid = (min + max) >>> 1; } //4.2 number在mid右边 else if(array[mid] < number){ min = mid + 1; mid = (min + max) >>> 1; }else{ //4.3 number与mid下标的值一样 return mid; } } }
1.3插值查找
二分查找是将每次查找的中间值与要查的元素比较确定是否找到和下一次的查找范围，插值查找是二分查找的一种改进方式，插值查找是尽可能将中间值接近要查找的元素。
通过套用公式
mid = min + (num - arr[min]) / (arr[max] - arr[min] ) * (max - min)可以使每次得到的中间值更接近要查找的元素。1.
num - arr[min]指的是数组中要查找的值与当前范围最小索引值的距离2.
arr[max] - arr[min]指的是数组中当前范围最大索引值与最小索引值的距离3.
(num - arr[min]) / (arr[max] - arr[min] )指的是要查找的元素在数组中位置的占比，乘以数组的长度(max - min)再加上最小偏移量min得到查找的元素在数组中的位置。优点：计算中间值mid时效率更高。
缺陷：要保证数组中的数据分布要比较均匀，否则效率会降低。
/** * 插值查找 * @param array * @param number * @return */ public static int binarySearch2(int[] array,int number) { //1.定义变量记录范围 int min = 0; int max = array.length - 1; //2.利用循环查找数据 while (true) { if(min>max) { return -1; } //3.找到min和max的中间位置mid int mid = (min + max) >>> 1; //4.比较 //4.1 number在mid左边 if(array[mid] > number) { max = mid - 1; mid = min + (number - array[min]) / (array[max] - array[min]) * (max - min); } //4.2 number在mid右边 else if(array[mid] < number){ min = mid + 1; mid = min + (number - array[min]) / (array[max] - array[min]) * (max - min); }else{ //4.3 number与mid下标的值一样 return mid; } } }
1.4分块查找
将一组数据分成好几个小块，每个块内的数据都是无序的，但块与块间是有一定顺序的。
分块的原则：
前一个块中的最大数都小于紧相挨着它的下一个块中的所有数（块内无序，块间有序）
块数数量一般等于数字的个数开根号。
在查找时，先确定要找的元素位于哪一块，然后在块内挨个查找。
代码分析：
在书写代码时，要先创建一个类，表示块，需要多少个块则分别创建多少个块的对象，然后将这些块对象放到一个数组中统一管理，这个数组也叫索引表
若要查找某个数，通过索引表中的每个最大值与该数进行比较得出该数在哪一块内。
package com.practice; /** * @Author YJ * @Date 2023/7/15 12:06 * Description: 分块查找 */ public class BlockSearch { 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}; //创建3个Block对象 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 num = 50; //调用方法 打印 System.out.println(getIndex(blocks, arr, num)); } public static int getIndex(Block[] blocks, int[] array, int number) { //1.确定number在哪一块中 int indexBlock = findIndexBlock(blocks, number); if(indexBlock == -1) { return -1; } //数据在数组中 //2.获取这一块的起始索引和结束索引 int startIndex = blocks[indexBlock].getStartIndex(); int endIndex = blocks[indexBlock].getEndIndex(); //3.遍历 for (int i = startIndex; i <= endIndex; i++) { if(array[i] == number) { return i; } } return -1; } //定义一个方法，确定number在哪一块中 public static int findIndexBlock(Block[] blocks, int number) { //Block b1 = new Block(21, 0, 5); -------- 0 //Block b2 = new Block(45, 6, 11); -------- 1 //Block b3 = new Block(73, 12, 17); -------- 2 //通过基本查找确定number在哪一块中 //从0索引遍历blocks数组，如果number小于max,说明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 + "}"; } }
二、排序算法
2.1冒泡排序
规则：相邻的数据两两比较，小的放前面，大的放后面
在进行排序的时候，按照相邻数据比较，小的放左边，大的放右边，当第一轮的数据比较结束后，最大值找到，且最大值在数组的最右边，除了最大值外，前面的其他数据还是无序的，所以还需要接着进行新一轮的排序，在剩余的数据中再次找到最大值，第二轮结束后，找到了次大值，继续再剩余的数据中进行新一轮的比较，再次找到最大值。
进行循环比较时，一轮比较完毕后，后一轮就可以少循环一次，执行的轮数为数组中的数据个数n - 1
package com.practice; /** * @Author YJ * @Date 2023/7/15 17:12 * Description:冒泡排序 */ public class BubbleSortDemo { public static void main(String[] args) { //1.定义数组 int[] arr = {2, 4, 5, 3, 1}; //2.冒泡排序 //第一轮：结束后最大值在数组的最右边 //多轮比较： for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { //i表示数组当中的索引 0 1 2 3 4 if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } //3.遍历数组 printArr(arr); } /** * 遍历数组 * @param arr */ public static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } }
2.2选择排序
选择排序：从0索引开始，拿着每一个索引上的元素跟后面的元素一次比较，小的放前面，大的放后面。
跟冒泡排序类似，选择排序从0索引开始，跟后面的元素一一比较，小的放前面，大的放后面，每一轮循环结束后，最小值就可以确定，接着以此从剩下的元素进行循环比较。
package com.practice; /** * @Author YJ * @Date 2023/7/15 18:15 * Description: */ public class SelectionDemo { public static void main(String[] args) { //1.定义数组 int[] arr = {2, 4, 5, 3, 1}; //开始比较 //i:表示这一轮中，哪个索引上的数据跟后面的数据进行比较并交换 for (int i = 0; i < arr.length - 1; i++) { for (int j = i + 1; j < arr.length; j++) { if(arr[i] > arr[j]) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } } printArr(arr); } /** * 遍历数组 * @param arr */ public static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } }
2.3插入排序
将0索引的元素到N索引的元素看作是有序的，把N+1索引的元素到最后一个当成是无序的。遍历无序的数据，将遍历到的元素插入到有序序列中适当的位置，如遇到相同数据，插在后面。
N的范围：0~最大索引
代码分析：在进行插入排序时，首先遍历无序的一组数据，拿到无序数据中的第一个，将这个元素与有序数据中倒着依次比较，并进行插入。
/** * @Author YJ * @Date 2023/7/16 6:54 * Description: */ public class InsertSortDemo { public static void main(String[] args) { //数组 int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}; //1.找到无序的那一组数据是从哪个索引开始的 int startIndex = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] > arr[i + 1]) { startIndex = i + 1;//表示有序的数据到i下标就结束了 break; } } //2.遍历从startIndex开始到最后一个元素，依次得到无序的那一组数据中的每一个数据 for (int i = startIndex; i < arr.length; i++) { //记录当前要插入数据的索引 int cur = i; while (cur > 0 && arr[cur] < arr[cur - 1]) { //交换位置 int tmp = arr[cur]; arr[cur] = arr[cur - 1]; arr[cur - 1] = tmp; cur--; } } printArr(arr); } private static void printArr(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
2.4快速排序
在进行快速排序前，我们还要用到递归算法。
递归指的是方法中调用方法本身的现象。
注意：递归一定要有出口，否则就会出现内存溢出。
作用：把一个复杂的问题层层转换为一个与原问题相似的规模较小的问题来求解。
递归只需少量的程序就可描述出解题过程中所需要的多次重复计算。
核心
1.找出口：什么时候不再调用方法。
2.找规则：如何把大问题变成规模较小的问题。
2.4.1递归求和
求1-100之间的和
/** * @Author YJ * @Date 2023/7/16 7:22 * Description: */ public class RecursionDemo { public static void main(String[] args) { //把大问题拆成小问题 //1-100之间的和 = 100 + （1-99之间的和） //1-99之间的和 = 99 + （1-98之间的和） //... //1-2之间的和 + 2 + （1-1之间的和） //1-1之间的和 = 1（递归的出口） System.out.println(getSum(100)); } public static int getSum(int number) { if(number == 1) { return 1; } return number + getSum(number - 1); } }
2.4.2快速排序
第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置。
结束后比基准数小的全部在左边，比基准数大的全部在右边。
要想实现上面的效果，要将6作为基准数，定义start和end作为数组的起始和结束位置，从start开始与基准数6依次比较，找出比6大的数，从end开始往后与基准数6比较，找出比6小的数，分别找到后将这两个数交换位置，然后继续找，当start和end指向同一数时，此时的位置就是基准数应存入的位置，这个也叫基准数归位。
/** * @Author YJ * @Date 2023/7/16 7:42 * Description:快速排序 */ public class QuickSort { 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] + " "); } System.out.println(); } /** * 快速排序 * * @param arr 要排序的数组 * @param i 起始索引 * @param j 结束索引 */ public static void quickSort(int[] arr, int i, int j) { //1.定义变量记录要查找的范围 int start = i; int end = j; if(start > end) { return; } //2.定义变量记录基准数 int baseNumber = arr[i]; //3.利用循环找到要交换的数据 while (start != end) { //利用end，从后往前找比基准数小的数 while (true) { if(end <= start || arr[end] < baseNumber) { break; } end--; } //利用start，从前往后找比基准数大的数 while (true) { if(start >= end || arr[start] > baseNumber) { break; } start++; } //交换 int tmp = arr[start]; arr[start] = arr[end]; arr[end] = tmp; } //当start和end指向了同一个元素时，循环结束 //表示已经找到了基准数在数组中应存入的位置 //基准数归位 int tmp = arr[i]; arr[i] = arr[start]; arr[start] = tmp; //确定6左边的数，重复排序 quickSort(arr,i,start - 1); //确定6右边的数，重复排序 quickSort(arr,start + 1,j); } }
总结
经过这一番讲解，我们学到了最基本的查找和排序算法，欢迎各位的持续关注！！！
