当前位置：首页 > java >正文

JAVA中常用算法详解：排序（冒泡、快速排序）与查找（二分查找）

java 2025/7/24 0:44:17

一、排序算法

1. 冒泡排序（Bubble Sort）

核心思想：
重复遍历数组，比较相邻元素，若顺序错误则交换它们。每一轮遍历会将最大的元素“冒泡”到末尾。

步骤：

从第一个元素开始，比较相邻元素。
若前一个元素大于后一个元素，交换它们。
每一轮结束后，最大的元素会被放到正确的位置。
重复上述过程，直到没有需要交换的元素。

时间复杂度：

最好情况：O(n)（已有序）
平均和最坏情况：O(n²)

Java实现：

java

复制

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 交换元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 若未发生交换，说明已有序，提前结束if (!swapped) break;}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("冒泡排序结果：");System.out.println(Arrays.toString(arr)); // [11, 12, 22, 25, 34, 64, 90]}
}

示例分析：
初始数组：[64, 34, 25, 12, 22, 11, 90]
第1轮：将90冒泡到末尾 → [34, 25, 12, 22, 11, 64, 90]
第2轮：将64冒泡到倒数第二 → [25, 12, 22, 11, 34, 64, 90]
……
最终所有元素有序。

2. 快速排序（Quick Sort）

核心思想：
分治策略：

选择一个基准元素（pivot）。
将数组分为两部分：小于基准的元素和大于基准的元素。
递归地对左右两部分重复上述过程。

时间复杂度：

最好和平均情况：O(n log n)
最坏情况（已排序且基准固定）：O(n²)（可通过随机选择基准避免）

Java实现：

java

复制

public class QuickSort {public static 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 static 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;}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("快速排序结果：");System.out.println(Arrays.toString(arr)); // [1, 5, 7, 8, 9, 10]}
}

示例分析：
初始数组：[10, 7, 8, 9, 1, 5]
基准选择：5（最后一个元素）
分区后：[1,5,8,9,10,7]（基准5在索引1）
递归处理左半部分 [1] 和右半部分 [8,9,10,7]，最终整体有序。

二、查找算法

1. 二分查找（Binary Search）

核心思想：
在有序数组中，通过不断缩小搜索范围来定位目标值。

比较中间元素与目标值。
若中间元素等于目标值，返回索引。
若中间元素小于目标值，搜索右半部分；否则搜索左半部分。
重复直到找到目标值或确定不存在。

时间复杂度：O(log n)

Java实现：

java

复制

public class BinarySearch {public static 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; // 未找到}public static void main(String[] args) {int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};int target = 23;int result = binarySearch(arr, target);if (result != -1) {System.out.println("元素 " + target + " 的索引是：" + result); // 5} else {System.out.println("元素未找到");}}
}

示例分析：
目标值：23
初始范围：[2,5,8,12,16,23,38,56,72,91]
第1次中间值：16（索引4），23 > 16 → 搜索右半部分
第2次中间值：38（索引6），23 < 38 → 搜索左半部分
第3次中间值：23（索引5），找到目标。

三、算法对比与应用场景

算法	时间复杂度	特点	适用场景
冒泡排序	O(n²)	简单但效率低，适合小规模数据	教学、小数组排序
快速排序	O(n log n)	高效，但需合理选择基准	大规模数据排序
二分查找	O(log n)	要求数组有序，查找极快	静态数据集的频繁查找

四、综合应用示例

java

复制

public class AlgorithmDemo {public static void main(String[] args) {// 冒泡排序示例int[] arr1 = {5, 3, 8, 6, 4};BubbleSort.bubbleSort(arr1);System.out.println("冒泡排序结果：" + Arrays.toString(arr1)); // [3, 4, 5, 6, 8]// 快速排序示例int[] arr2 = {9, -3, 5, 2, 6, 8, -6};QuickSort.quickSort(arr2, 0, arr2.length - 1);System.out.println("快速排序结果：" + Arrays.toString(arr2)); // [-6, -3, 2, 5, 6, 8, 9]// 二分查找示例int[] sortedArr = {1, 3, 5, 7, 9, 11};int target = 7;int index = BinarySearch.binarySearch(sortedArr, target);System.out.println("元素 " + target + " 的索引是：" + index); // 3}
}

关键点总结