Java的查找算法和排序算法
- 一、查找算法
- 1. 基本查找
- a. 示例
- 2. 二分查找
- a. 示例
- 3. 插值查找
- 4. 斐波那契查找
- 5. 分块查找
- a. 示例
- 二、排序算法
- 1. 冒泡排序
- a. 示例
- 2. 选择排序
- a. 示例
- 3、插入排序
- a. 示例
- 4. 快速排序（效率最高）
- a. 示例
一、查找算法
1. 基本查找
- 基本查找也叫顺序查找。
- 核心：从0索引开始挨个往后查找。
a. 示例
- 需求：定义一个方法，查询元素在数组中的索引值。
import java.util.ArrayList;
public class Demo2 {
public static void main(String[] args) {
int[] arr = {131, 127, 147, 81, 103, 23, 7, 79, 81};
System.out.println(searchNumber(arr, 81));
}
public static ArrayList<Integer> searchNumber(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;
}
}
2. 二分查找
- 二分查找又称折半查找。
- 前提条件：数组中的数据必须是有序的。
- 如果数据是乱的，必须先排序。
- 只能确定当前key在数组中是否存在，不能确定其索引值。
- 核心：每次排除一半的查找范围。
- 过程：
- 定义min和max表示当前要查找的范围
- 定义中间索引mid（min和max中间的索引）
- 如果key在mid的左边，缩小范围时，min不变，max等于mid减1
- 如果key在mid的右边，缩小范围时，max不变，min等于mid加1
a. 示例
public class Demo3 {
public static void main(String[] args) {
int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
System.out.println(BinarySearch(arr, 127));
}
public static int BinarySearch(int[] arr, int number){
// 定义范围
int min = 0;
int max = arr.length;
while (true) {
if (min > max) {
return -1;
}
// 定义中间索引
int mid = (min + max) / 2;
// 核心代码
if (arr[mid] > number) {
max = mid - 1;
} else if (arr[mid] < number) {
min = mid + 1;
} else if (arr[mid] == number) {
return mid;
}
}
}
}
3. 插值查找
-
插值查找在二分查找的基础上改进。
-
前提条件：数据尽可能的分布均匀。
-
核心： m i d = m i n + k e y − a r r [ m i n ] a r r [ m a x ] − a r r [ m i n ] × ( m a x − m i n ) mid = min + \dfrac{key-arr[min]}{arr[max]-arr[min]}\times(max-min) mid=min+arr[max]−arr[min]key−arr[min]×(max−min)
- mid值是key在数组中的百分比位置。
- mid = 偏移量 + 左距离 ÷ 总距离 × (最大值-最小值)
4. 斐波那契查找
- 斐波那契查找在二分查找的基础上改进。
- 根据黄金分割点来计算mid索引。
- mid = min + 黄金分割点左半边长度 - 1。
5. 分块查找
- 原则
- 前一块中的最大数据，小于后一块中所有的数据（块内无序，块间有序）
- 块数数量一般等于元素个数开根号。比如：16个元素一般分为4块左右。
- 核心：先确定要查找的元素在哪一块，然后再块内挨个查找。
a. 示例
- 定义一个数组 {16, 5, 9, 12, 21, 18, 32, 23, 37, 26, 45, 34, 50, 48, 61, 52, 73, 66}，查询数字是否在数组中。
package day18.search;
public class Demo4 {
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 = 66;
// 现确定在哪一块
int index = getIndex(blockArr, arr, number);
// 在块中查找
System.out.println(index);
}
private static int getIndex(Block[] blockArr, int[] arr, int number) {
int indexBlock = findIndexBlock(blockArr, number);
if (indexBlock == -1) {
return -1;
}
int startIndex = blockArr[indexBlock].getStartIndex();
int endIndex = blockArr[indexBlock].getEndIndex();
for (int i = startIndex; i <= endIndex; i++) {
if (arr[i] == number) {
return i;
}
}
return -1;
}
public static int findIndexBlock(Block[] blockArr, int 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;
}
}
二、排序算法
1. 冒泡排序
- 步骤：
- 相邻的元素两两比较，大的放后面，小的放前面；
- 第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推；
- 如果数组中有n个数据，总共要执行n-1轮。
a. 示例
- 定义一个数组{2, 1, 4, 5, 3}，并排序。
import java.util.Arrays;
public class Demo1 {
public static void main(String[] args) {
int[] arr = {2, 1, 4, 5, 3};
// 循环多少轮
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;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
2. 选择排序
- 步骤：
- 从0索引开始，与每一个索引上的元素依次比较。
- 小的放前面，大的放后面。
a. 示例
- 定义一个数组{2, 1, 6, 8, 3}，并排序。
import java.util.Arrays;
public class Demo2 {
public static void main(String[] args) {
int[] arr = {2, 1, 6, 8, 3};
// 进行比较的索引值
for (int i = 0; i < arr.length; i++) {
// 拿每个索引值对应的元素与后面的每个元素进行比较
// 每完成一轮，索引值加1
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;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
3、插入排序
- 步骤：
- 将索引在[0, N]的元素看作有序的，把[N+1, arr.length-1]的元素当成无序的。
- 遍历无序的数据，将遍历到的元素插入到有序序列中适当的位置，如遇到相同数据，插在后面。
- N的范围：0～arr.length-1
a. 示例
- 定义数组：{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
import java.util.Arrays;
public class Demo3 {
public static void main(String[] args) {
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 找到无序的那一组数据从哪个索引开始
int startIndex = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > arr[i + 1]) {
startIndex = i + 1;
break;
}
}
// 遍历从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--;
}
}
System.out.println(Arrays.toString(arr));
}
}
4. 快速排序（效率最高）
- 步骤：
- 将排序范围内的第一个数字作为基准数，在定义两个索引变量start、end
- 索引start从前往后找比基准数大的，索引end从后往前找比基准数小的。
- start、end都找到一个数后，替换两个数。
- 循环上面三步，直到start和end指向同一个索引。让基准数与这个索引的元素替换（基准数归位）。
- 归位后的效果：基准数左边的，比基准数小；基准数右边的，比基准数大。
- 对基准数两边的数据重复上面四步，直到要求范围的开始索引大于结束索引。
a. 示例
- 定义一个长度为100万的数组，为数组随机填充数字，给数组进行排序。
import java.util.Random;
public class Demo6 {
public static void main(String[] args) {
Random random = new Random();
int[] arr = new int[1000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt();
}
long start = System.currentTimeMillis();
quickSort(arr, 0, arr.length - 1);
long end = System.currentTimeMillis();
System.out.println("共用时: " + (end-start));
}
public static void quickSort(int[] arr, int startIndex, int endIndex) {
if (startIndex > endIndex) return;
// 记录索引值，防止被修改
int start = startIndex;
int end = endIndex;
// 记录基准数
int baseNumber = arr[startIndex];
// 利用循环找到要交换的数
while (start != end) {
// 从end往前找
while (end > start && arr[end] >= baseNumber) end--;
// 从start往后找
while (end > start && arr[start] <= baseNumber) start++;
// 交换start和end
int temp = arr[end];
arr[end] = arr[start];
arr[start] = temp;
}
// 基准数归位
int temp = arr[startIndex];
arr[startIndex] = arr[end];
arr[end] = temp;
// 确定6左边的范围
quickSort(arr, startIndex, start - 1);
// 确定6右边的范围
quickSort(arr, end + 1, endIndex);
}
}
