【Java开发实训】day05——数组常见算法
目录
🌈嗨！我是Filotimo__🌈。很高兴与大家相识，希望我的博客能对你有所帮助。
💡本文由Filotimo__✍️原创，首发于CSDN📚。
📣如需转载，请事先与我联系以获得授权⚠️。
🎁欢迎大家给我点赞👍、收藏⭐️，并在留言区📝与我互动，这些都是我前进的动力！
🌟我的格言：森林草木都有自己认为对的角度🌟。
一、数组翻转
数组翻转是指将数组中的元素按照对称索引位置互相交换。例如，如果有一个数组 {1, 2, 3, 4, 5}，翻转后变成 {5, 4, 3, 2, 1}。
1.1示例代码
数组翻转的示例代码：
public class ArrayReverseExample {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
System.out.println("原始数组:");
printArray(array);
reverseArray(array);
System.out.println("\n翻转后的数组:");
printArray(array);
}
public static void reverseArray(int[] array) {
int start = 0;
int end = array.length - 1;
while (start < end) {
int temp = array[start];
array[start] = array[end];
array[end] = temp;
start++;
end--;
}
}
public static void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}运行截图：
在上面代码中，reverseArray 方法实现了数组翻转的逻辑：使用两个指针 start 和 end，分别指向数组的起始和末尾元素。在循环中，将 start 和 end 指向的元素互换，然后将 start 向右移动一位，end 向左移动一位，直到 start 不小于 end。
1.2适用场景
数组翻转的适用场景：
① 倒序输出：当需要将数组中的元素按照相反的顺序输出时，可以先对数组进行翻转，然后再遍历输出元素。
② 字符串反转：在字符串处理中，有时需要将字符串进行反转操作，此时可以将字符串转换为字符数组，对字符数组进行翻转操作，然后再将字符数组转换回字符串。
③ 实现栈和队列：在实现栈（后进先出）或队列（先进先出）这样的数据结构时，可以使用数组进行存储，并通过翻转数组来实现不同的操作顺序。
二、冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数组，比较每对相邻的元素，并依次交换顺序错误的元素，直到没有需要交换的元素为止。这个过程类似于水泡在水中上浮的过程，故名冒泡排序。
2.1示例代码
冒泡排序的示例代码：
public class BubbleSortExample {
public static void main(String[] args) {
int[] array = {5, 1, 12, -5, 16};
System.out.println("原始数组:");
printArray(array);
bubbleSort(array);
System.out.println("\n排序后的数组:");
printArray(array);
}
public static void bubbleSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (array[j] > array[j + 1]) {
// 交换 array[j] 和 array[j + 1]
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
public static void printArray(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}运行截图：
在上面代码中，bubbleSort 方法实现了冒泡排序算法：外层循环 for (int i = 0; i < n - 1; i++) 控制排序的轮数，其中 n 是数组的长度。内层循环 for (int j = 0; j < n - 1 - i; j++) 在每一轮中遍历数组，并比较相邻元素。如果前一个元素比后一个元素大，则交换它们的位置，确保较大的元素向右移动。
2.2适用场景
冒泡排序的适用场景：
① 小规模数据排序：冒泡排序算法简单易懂，适合处理小规模的数据（一般小于100个元素），在小数据量下性能良好。
② 几乎已排序的数组：如果数组的元素大部分已经处于正确位置，冒泡排序的性能会相对较好，因为它的优化版本可以提前结束排序过程。
③ 实时数据流排序：在某些实时系统中，如果数据流入非常缓慢且对排序的实时性要求不高，可以用冒泡排序进行简单的处理。
三、二分查找
二分查找是一种高效的查找算法，适用于已排序的数组或列表。它通过反复将查找范围减半来定位目标值，直到找到目标或确定目标不存在为止。（前提：数组中的数据必须是有序的）
3.1示例代码
二分查找的示例代码：
public class BinarySearchExample {
public static void main(String[] args) {
int[] array = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 11;
int index = binarySearch(array, target);
if (index != -1) {
System.out.println("找到目标 " + target + " ，索引位置为：" + index);
} else {
System.out.println("目标 " + target + " 未找到。");
}
}
public static int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 如果目标值在中间位置
if (array[mid] == target) {
return mid;
}
// 如果目标值比中间值小，向左侧继续查找
if (array[mid] > target) {
right = mid - 1;
}
// 如果目标值比中间值大，向右侧继续查找
if (array[mid] < target) {
left = mid + 1;
}
}
// 如果没有找到目标值，返回 -1
return -1;
}
}运行截图：
在上面代码中，binarySearch 方法实现了二分查找的算法：使用 left 和 right 分别表示当前查找范围的左右边界。在每一轮循环中，计算中间位置 mid。如果目标值等于 array[mid]，则找到目标值，返回 mid。如果目标值小于 array[mid]，则更新 right，缩小查找范围到左半部分。如果目标值大于 array[mid]，则更新 left，缩小查找范围到右半部分。若最终 left > right，表示未找到目标值，返回 -1。
3.2适用场景
二分查找的适用场景：
① 有序数据：二分查找要求数据是有序的，因此适用于已经排序好的数组或列表中查找特定元素。
② 大数据量的查找：相比于线性搜索，二分查找在大数据量的情况下性能更好，因为它每次可以排除一半的数据。
③ 频繁查找：如果需要多次查找同一个有序集合中的元素，一次排序、多次查找的场景适合使用二分查找。
④ 需求较高的性能：对查找性能有较高要求的场景，二分查找是一个高效的算法，时间复杂度为 O(log n)。
⑤ 对内存要求低：相比于哈希表等数据结构，二分查找不需要额外的存储空间，对内存要求较低。
原文地址：https://blog.csdn.net/m0_71369515/article/details/140495706
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！