Java 常见排序与二分查找模板

在算法面试或机试（如 ACM 模式）中，往往需要手写或灵活运用常见的排序算法与二分查找算法。以下是使用 Java 实现的常见经典算法模板。

1. 快速排序（Quick Sort）

快速排序利用分治思想，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。

时间复杂度: 平均 $O(N \log N)$，最坏 $O(N^2)$。
空间复杂度: $O(\log N)$。

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        
        // 取中间元素作为基准
        int pivot = arr[(left + right) >> 1];
        int i = left - 1;
        int j = right + 1;
        
        while (i < j) {
            // 从左向右找第一个大于等于基准的数
            while (arr[++i] < pivot);
            // 从右向左找第一个小于等于基准的数
            while (arr[--j] > pivot);
            // 交换这两个数
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // 递归处理左右两区间
        quickSort(arr, left, j);
        quickSort(arr, j + 1, right);
    }
}

2. 归并排序（Merge Sort）

归并排序也是基于分治法。它将数组从中间分成两个子数组，分别递归排序，然后再将两个有序子数组合并成一个最终排序的数组。

时间复杂度: $O(N \log N)$。
空间复杂度: $O(N)$（需使用一个临时数组用于合并）。

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        // 分治：递归排序左右两边
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两个有序区间
        int[] temp = new int[right - left + 1];
        int k = 0;
        int i = left, j = mid + 1;
        while(i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 如果左边数组还有剩余，则放入临时数组
        while(i <= mid) {
            temp[k++] = arr[i++];
        }
        // 如果右边数组还有剩余，则放入临时数组
        while(j <= right) {
            temp[k++] = arr[j++];
        }

        k = 0;
        // 将排序好的临时数组复制回原数组
        for(int i = left; i <= right; i ++) {
            arr[i] = temp[k++];
        }
    }
}

3. 堆排序（Heap Sort）

堆排序可以分为两步：第一步建堆（对于升序排序一般建大根堆），第二步是将堆顶元素（最大值）和末尾元素交换，并缩小堆的大小，重新调整堆。

时间复杂度: $O(N \log N)$。
空间复杂度: $O(1)$。

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // 1. 从最后一个非叶子节点开始，构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 2. 逐步将堆顶元素与末尾元素交换，并持续调整堆
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶元素和当前未排序部分的最后一个元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            // 将剩下的 i 个元素重新调整为大顶堆
            heapify(arr, i, 0);
        }
    }

    // 维护大顶堆的性质
    private static 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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 递归调整受影响的子树
            heapify(arr, n, largest);
        }
    }
}

4. 二分查找（Binary Search）

二分查找是针对有序数组的高效查找算法，每次将搜索范围缩小一半。

时间复杂度: $O(\log N)$。
空间复杂度: $O(1)$。

标准二分查找（找精确值）

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            // 防止 (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 int leftBound(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else if (arr[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 检查越界情况
    if (left >= arr.length || arr[left] != target) {
        return -1;
    }
    return left;
}