常见算法(二分,分块查找,插入,快速排序)

常见算法

1. 顺序查找

java">package com.mohuanan.exercise;import java.util.ArrayList;public class BasicFind01 {public static void main(String[] args) {int[] arr = {1, 2, 3, 1, 2, 3, 4, 5, 6};int number = 2;ArrayList<Integer> indexList = findIndex(arr, number);if (indexList.size() == 0) {System.out.println("没有该元素");} else {//遍历集合 输出for (int i = 0; i < indexList.size(); i++) {int numberIndex = indexList.get(i);System.out.println(numberIndex);}}}//基本查找public static ArrayList<Integer> findIndex(int[] arr, int number) {//定义一个集合ArrayList<Integer> list = new ArrayList<>();//遍历数组for (int i = 0; i < arr.length; i++) {if (arr[i] == number) {//Java会自动装箱和拆箱list.add(i);}}return list;}
}

2. 二分查找

数组必须是有序的
mid只是数组元素的下标,要比较两个数字,是用arr[mid]和number比较,而不是mid和number比较

java">package com.mohuanan.exercise;public class HalfFind01 {public static void main(String[] args) {//前提是数组是有序的int[] arr = {11, 55, 66, 77, 88, 99};int number = 11;int index = findIndex(arr, number);System.out.println(index);}private static int findIndex(int[] arr, int number) {//两个指针 表示下标int min = 0;int max = arr.length - 1;//二分查找while (min <= max) {int mid = (min + max) / 2;//注意 mid只是 下标//要比较两个值 是arr[mid] 而不是midif(arr[mid]==number){return mid;}else if(arr[mid] > number){max = mid-1;}else if(arr[mid] < number){min = mid + 1;}}//没有找到return -1;}
}

3. 分块查找

块内无序,块间有序

java">package com.mohuanan.exercise;public class FenkuaiFind01 {public static void main(String[] args) {//分块int[] arr = {11, 5, 8, 9,30, 20,50, 80, 45, 60, 50,84, 90};int number = 20;//创建四个块Block b1 = new Block(11, 0, 3);Block b2 = new Block(30, 4, 5);Block b3 = new Block(80, 6, 10);Block b4 = new Block(90, 11, 12);//创建数组存储每一块Block[] blockArr = {b1, b2, b3, b4};int index = findIndex(blockArr,arr,number);System.out.println(index);}//查找元素public static int findIndex(Block[] blockArr, int[] arr, int number) {//查找该元素在那一块里面int result = findBlock(blockArr, number);if (result == -1) {return -1;} else {//获取该块的开始索引 和最后索引int startIndex = blockArr[result].getStartIndex();int endIndex = blockArr[result].getEndIndex();//从开始索引 到最后索引 遍历arr数字 查找元素for (int i = startIndex; i <= endIndex; i++) {if(arr[i] == number){return i;}}}//没有找到return -1;}private static int findBlock(Block[] blockArr, int number) {//遍历Block数组for (int i = 0; i < blockArr.length; i++) {//如果number小于等于max 那么number就在该块里面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;}/*** 获取** @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 + "}";}
}

4. 冒泡排序

java">package com.mohuanan.sort;public class MaopaoSort {public static void main(String[] args) {int[] arr = {7, 8, 9, 5, 4, 6, 3, 2, 1};int[] sortArr = sortArr(arr);//遍历for (int i : sortArr) {System.out.print(i + " ");}System.out.println();}public static int[] sortArr(int[] arr) {//从da到小//轮数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 t = arr[j];arr[j] = arr[j + 1];arr[j + 1] = t;}}}return arr;}}

5. 选择排序

java">package com.mohuanan.sort;public class ChooseSort {public static void main(String[] args) {int[] arr = {7, 8, 9, 5, 4, 6, 3, 2, 1};int[] sortArr = sortArr(arr);//遍历for (int i : sortArr) {System.out.print(i + " ");}System.out.println();}private static int[] sortArr(int[] arr) {//da dao xiaofor (int i = 0; i < arr.length - 1; i++) {//注意j必须初始值 是i  i+1也可以表示不用自己和自己比较for (int j = i + 1; j < arr.length; j++) {//原理从0开始 找值 放在开头if (arr[i] < arr[j]) {int t = arr[j];arr[j] = arr[i];arr[i] = t;}}}return arr;}}

6. 插入排序

要重点复习这个算法

java">package com.mohuanan.sort;public class InsertSort {public static void main(String[] args) {int[] arr = {7, 8, 9, 5, 4, 6, 3, 2, 1};int[] sortArr = sortArr(arr);//遍历for (int i : sortArr) {System.out.print(i + " ");}System.out.println();}private static int[] sortArr(int[] arr) {//找到无序的开始的索引//从大到小int startIndex = -1;for (int i = 0; i < arr.length - 1; i++) {if (arr[i] < arr[i + 1]) {startIndex = i + 1;//找到第一个就退出break;}}System.out.println(startIndex);//从startIndex开始遍历for (int i = startIndex; i < arr.length; i++) {//二分//用于存储i前面数字的索引//j = i; 而不是j= startIndex;int j = i;//arr[j]表示 要插入的元素//arr[j - 1]表示要插入的元素的前面的元素//j> 0 为了下标 到了最后一个数字时 不用在插lwhile (j > 0 && arr[j] > arr[j - 1]) {//交换int t = arr[j];arr[j] = arr[j - 1];arr[j - 1] = t;//往前移一位j--;}}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]+ " ");}System.out.println();return arr;}
}

7. 快速排序

重点复习这个算法

java">package com.mohuanan.sort;public class QuickSort {public static void main(String[] args) {int[] arr = {4, 1, 2, 5, 6, 3, 9, 7, 8, 10};quickSort(arr, 0, arr.length - 1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}private static void quickSort(int[] arr, int i, int j) {//开始索引int start = i;//结束索引int end = j;//终止递归的条件if (start > end) {return;}//记录基准数int basicNumber = arr[i];//找到基准数//这里要用!=  表示while (start != end) {//先要移动end 从后往前找到 比基准数小的数字while (true) {//这里两个条件//end不能超过stratif (end <= start || arr[end] < basicNumber) {break;}end--;}//再移动start 从前往后找到 比基准数大的数字while (true) {if (start >= end || arr[start] > basicNumber) {break;}start++;}//找到两个数字 交换int t = arr[start];arr[start] = arr[end];arr[end] = t;}//当上面执行完之后//将基准数 和start或者end指向的数字进行交换//拿着这个范围里面的第一个数字进行交换int t = arr[start];arr[start] = arr[i];arr[i] = t;//重复执行quickSort(arr, i, start - 1);quickSort(arr, start + 1, j);}
}