常见算法
选择排序
选择排序的思想
-
每轮选择当前位置，开始找出后面的较小值与该位置的值进行交换，知道与最后一个数比较完成，本轮结束；
然后从后一个位置开始，依次比较第二个元素后面的值，直到最后一个比较完成，本轮结束
一直重复比较，每次轮数结束后起始点递进1，反复执行直到起始点变成最后一个元素为止
image.png
选择排序的关键
- 确定总共需要选择几轮：数组的长度 - 1
- 控制每轮从以前位置为基准，与后面元素选择几次
代码
package com.java.sort_binarysearch;
import java.util.Arrays;
public class Test01 {
public static void main(String[] args) {
// 1.定义数组
int[] arr = {5, 1, 3, 2};
// 0 1 2 3
// 2.定义一个循环控制选择几轮：arr.length - 1
// 其中 i是起始值 j是被比较值
for (int i = 0; i < arr.length; i++) {
/*
i = 0 j = 1 2 3
i = 1 j = 2 3
i = 2 j = 3
*/
// 3. 定义内部循环，控制循环几次
for (int j = i + 1; j < arr.length; j++) {
// 当前位：arr[i]
// 如果有比当前位更小的，则交换
if (arr[i] > arr[j]) { // 使用异或运算特性交换两个元素
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
}
}
System.out.println(Arrays.toString(arr));
}
}
二分查找
二分查找的思想
- 基本查找在数据量比较大的时候，从前往后查找的性能极差
- 二分查找性能好，前提是数据必须被排好序
- 二分查找就是每次查找砍掉一半的查找范围
- 二分查找正常的检索条件应该是：开始位置min<=结束位置max
代码
package com.java.sort_binarysearch;
public class Test02 {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(binarySearch(arr, 3));
System.out.println(binarySearch(arr, -43));
}
/**
* 二分查找元素索引
*
* @return 索引 不存在返回-1
*/
public static int binarySearch(int[] arr, int data) {
// 1. 定义左边的位置和右边的位置
int left = 0;
int right = arr.length - 1;
// 2. 开始循环，折半查询
// 折叠条件：左边位置小于等于右边位置，最后一次折叠即两者相遇
while (left <= right) {
// 取中间索引
int middleIndex = (left + right) / 2; //不用关心中间值是否准确，大致即可，即11对折可以为5也可以为6，无所谓
// 3. 判断当前中间位置的元素和要找的大小情况
if (data > arr[middleIndex]) {
// 3.1 往右找，左边值更新 = 中间索引 + 1
left = middleIndex + 1;
} else if (data < arr[middleIndex]) {
// 3.2 往左找，右边位置更新 = 中间索引 - 1
right = middleIndex - 1;
} else {
// 3.3 中间值正好是待查找值
return middleIndex;
}
}
// 4. 元素不在其中的情况
return -1; // 查无此元素
}
}
网友评论