数组的算法
目录搜索方法
-
线性搜索（Linear Search）:
-
算法：遍历数组，直到找到目标值或遍历完数组。
-
时间复杂度：O(n)。
-
应用：在未排序的数组中查找元素。
public int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; // 返回目标元素的索引 } } return -1; // 如果未找到，返回-1 }
-
-
二分搜索（Binary Search）:
-
算法：在已排序的数组中，通过比较中间元素与目标值来确定搜索区间，并逐步缩小搜索范围。
-
时间复杂度：O(log n)。
-
应用：在已排序的数组中快速查找元素。
public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; // 找到目标 } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // 未找到目标 }
排序方法
-
-
冒泡排序（Bubble Sort）:
-
算法：通过重复遍历数组，相邻元素两两比较并交换位置，直到整个数组排序。
-
时间复杂度：O(n^2)。
-
应用：教学和简单场景下的排序。
public void bubbleSort(int[] arr) { boolean swapped; for (int i = 0; i < arr.length - 1; i++) { swapped = false; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 交换 arr[j] 和 arr[j + 1] int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } if (!swapped) break; // 如果没有交换，数组已经排序完成 } }
-
-
选择排序（Selection Sort）:
-
算法：找到未排序部分的最小（或最大）元素，将其与未排序部分的第一个元素交换位置。
-
时间复杂度：O(n^2)。
-
应用：教学和简单场景下的排序。
public void selectionSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 交换最小元素与第一个元素 int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } }
-
-
插入排序（Insertion Sort）:
-
算法：构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
-
时间复杂度：O(n^2)。
-
应用：对小规模数据或部分有序数据的排序。
public void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }
-
-
快速排序（Quick Sort）:
-
算法：选择一个基准元素，将数组分为小于和大于基准的两部分，递归地在这两部分上进行快速排序。
-
时间复杂度：平均O(n log n)，最坏O(n^2)。
-
应用：高效的通用排序算法。
public void quickSort(int[] arr, int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } private int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; }
-
-
归并排序（Merge Sort）:
-
算法：将数组分成两半，递归地对每一半进行归并排序，然后将排序好的两半合并。
-
时间复杂度：O(n log n)。
-
应用：对大规模数据的稳定排序。
public void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } private void merge(int[] arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int[] leftArr = new int[n1]; int[] rightArr = new int[n2]; for (int i = 0; i < n1; ++i) { leftArr[i] = arr[left + i]; } for (int j = 0; j < n2; ++j) { rightArr[j] = arr[mid + 1 + j]; } int i = 0, j = 0; int k = left; while (i < n1 && j < n2) { if (leftArr[i] <= rightArr[j]) { arr[k] = leftArr[i]; i++; } else { arr[k] = rightArr[j]; j++; } k++; } while (i < n1) { arr[k] = leftArr[i]; i++; k++; } while (j < n2) { arr[k] = rightArr[j]; j++; k++; } }
-
-
计数排序（Counting Sort）:
- 算法：使用额外的数组来统计每个元素出现的次数，然后根据这些计数来确定元素的排序位置。
- 时间复杂度：O(n + k)，k是元素范围。
- 应用：当元素范围不大且需要稳定排序时。
排序算法库
排序算法库提供了一组预先实现的排序函数，这些函数可以高效地对数据进行排序。
Java 提供了 Arrays.sort() 方法，可以对数组进行排序。对于对象数组，可以使用 Arrays.sort() 的变体，传入自定义的比较器。
import java.util.Arrays;
int[] myArray = {5, 3, 8, 6, 2};
Arrays.sort(myArray); // 对整型数组进行排序
// 对对象数组使用自定义比较器
class MyObject implements Comparable<MyObject> {
int value;
// 实现 compareTo 方法
public int compareTo(MyObject other) {
return this.value - other.value;
}
}
MyObject[] objects = ...;
Arrays.sort(objects); // 自然排序