13.5 排序与查找
面试重要程度：⭐⭐⭐⭐⭐
常见提问方式： "手写快速排序" "实现二分查找" "分析排序算法复杂度"
预计阅读时间：45分钟
🔄 经典排序算法
基础排序算法
/**
* 基础排序算法实现
*/
public class BasicSortingAlgorithms {
/**
* 冒泡排序
* 时间复杂度：O(n²)，空间复杂度：O(1)
* 稳定排序
*/
public void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swapped = true;
}
}
// 如果没有发生交换，说明已经有序
if (!swapped) break;
}
}
/**
* 选择排序
* 时间复杂度：O(n²)，空间复杂度：O(1)
* 不稳定排序
*/
public void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// 找到最小元素的索引
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换最小元素到当前位置
if (minIndex != i) {
swap(arr, i, minIndex);
}
}
}
/**
* 插入排序
* 时间复杂度：O(n²)，空间复杂度：O(1)
* 稳定排序
*/
public void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将大于key的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
高效排序算法
/**
* 高效排序算法实现
*/
public class AdvancedSortingAlgorithms {
/**
* 快速排序
* 平均时间复杂度：O(n log n)，最坏：O(n²)
* 空间复杂度：O(log n)，不稳定排序
*/
public void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private 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++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
/**
* 归并排序
* 时间复杂度：O(n log n)，空间复杂度：O(n)
* 稳定排序
*/
public void mergeSort(int[] arr) {
if (arr.length <= 1) return;
int[] temp = new int[arr.length];
mergeSort(arr, temp, 0, arr.length - 1);
}
private void mergeSort(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, temp, left, mid);
mergeSort(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
private void merge(int[] arr, int[] temp, int left, int mid, int right) {
// 复制到临时数组
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left, j = mid + 1, k = left;
// 合并两个有序子数组
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
// 复制剩余元素
while (i <= mid) {
arr[k++] = temp[i++];
}
while (j <= right) {
arr[k++] = temp[j++];
}
}
/**
* 堆排序
* 时间复杂度：O(n log n)，空间复杂度：O(1)
* 不稳定排序
*/
public void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 逐个提取元素
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i); // 将最大元素移到末尾
heapify(arr, i, 0); // 重新调整堆
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
🔍 查找算法
基础查找算法
/**
* 查找算法实现
*/
public class SearchAlgorithms {
/**
* 二分查找（迭代版本）
* 时间复杂度：O(log n)，空间复杂度：O(1)
* 要求数组有序
*/
public int binarySearch(int[] arr, int target) {
int left = 0, 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;
}
/**
* 查找第一个等于目标值的位置
* LeetCode 34: Find First and Last Position of Element in Sorted Array
*/
public int findFirst(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid;
right = mid - 1; // 继续向左查找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
/**
* 查找最后一个等于目标值的位置
*/
public int findLast(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid;
left = mid + 1; // 继续向右查找
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
/**
* 在旋转排序数组中搜索
* LeetCode 33: Search in Rotated Sorted Array
*/
public int searchInRotatedArray(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
// 判断哪一半是有序的
if (nums[left] <= nums[mid]) {
// 左半部分有序
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// 右半部分有序
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
/**
* 寻找峰值
* LeetCode 162: Find Peak Element
*/
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
// 峰值在左半部分（包括mid）
right = mid;
} else {
// 峰值在右半部分
left = mid + 1;
}
}
return left;
}
}
📊 LeetCode高频题目
经典题目实现
/**
* LeetCode高频排序查找题目
*/
public class LeetCodeSortingSearching {
/**
* 数组中的第K个最大元素
* LeetCode 215: Kth Largest Element in an Array
*/
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
private int quickSelect(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k) {
return nums[pivotIndex];
} else if (pivotIndex < k) {
return quickSelect(nums, pivotIndex + 1, right, k);
} else {
return quickSelect(nums, left, pivotIndex - 1, k);
}
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (nums[j] <= pivot) {
i++;
swap(nums, i, j);
}
}
swap(nums, i + 1, right);
return i + 1;
}
/**
* 合并区间
* LeetCode 56: Merge Intervals
*/
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
// 按起始位置排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
int[] current = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (current[1] >= intervals[i][0]) {
// 有重叠，合并区间
current[1] = Math.max(current[1], intervals[i][1]);
} else {
// 无重叠，添加当前区间，更新current
merged.add(current);
current = intervals[i];
}
}
merged.add(current);
return merged.toArray(new int[merged.size()][]);
}
/**
* 颜色分类
* LeetCode 75: Sort Colors
*/
public void sortColors(int[] nums) {
int left = 0, right = nums.length - 1;
int current = 0;
while (current <= right) {
if (nums[current] == 0) {
swap(nums, left++, current++);
} else if (nums[current] == 2) {
swap(nums, current, right--);
} else {
current++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
💡 面试常见问题解答
Q1: 各种排序算法的适用场景？
标准回答：
排序算法选择指南： 1. 快速排序 - 适用：一般情况下的最佳选择 - 优点：平均性能最好 - 缺点：最坏情况O(n²) 2. 归并排序 - 适用：需要稳定排序，外部排序 - 优点：稳定，时间复杂度稳定 - 缺点：空间复杂度O(n) 3. 堆排序 - 适用：内存受限，需要O(1)空间 - 优点：时间复杂度稳定，空间O(1) - 缺点：不稳定，常数因子大 4. 计数排序/基数排序 - 适用：整数排序，范围较小 - 优点：线性时间复杂度 - 缺点：空间消耗大，适用范围有限 根据数据特点和需求选择合适算法。
Q2: 二分查找的变种问题？
标准回答：
二分查找变种： 1. 查找确切值 - 标准二分查找 - 注意边界条件 2. 查找边界 - 第一个/最后一个目标值位置 - 插入位置查找 3. 旋转数组查找 - 判断哪一半有序 - 根据目标值范围选择搜索方向 4. 峰值查找 - 利用单调性进行二分 - 比较相邻元素大小关系 关键是理解二分的本质：在有序空间中快速定位。
Q3: 快速排序的优化策略？
标准回答：
快速排序优化： 1. 基准选择优化 - 随机选择基准 - 三数取中法 - 避免最坏情况 2. 小数组优化 - 小数组使用插入排序 - 减少递归开销 3. 三路快排 - 处理大量重复元素 - 将数组分为小于、等于、大于三部分 4. 尾递归优化 - 减少栈空间使用 - 先处理较小的子数组 这些优化能显著提升实际性能。
核心要点总结：
- ✅ 掌握经典排序算法的实现和复杂度分析
- ✅ 熟练运用二分查找解决各种变种问题
- ✅ 理解排序算法的选择策略和优化方法
- ✅ 能够解决LeetCode中的高频排序查找题目
Java面试圣经 文章被收录于专栏
Java面试圣经
查看7道真题和解析
投递中国电信等公司8个岗位