第二大脑

主题

2026-08-24
730
2.9m

概念卡片：排序与查找算法 ​

一句话机制：排序 = 比较 + 交换/移动使序列有序；二分查找 = 每次折半缩小范围（前提有序）；一致性哈希 = 把哈希值空间组织成环，节点增减只重定位相邻小部分数据。

三大排序算法对比 ​

算法思路最佳最差平均稳定性
冒泡排序相邻比较交换，大的「浮」到末尾O(n)O(n²)O(n²)稳定
选择排序每趟选最小放到有序区末尾O(n²)O(n²)O(n²)不稳定
快速排序选基准 pivot，分区递归O(nlogn)O(n²)O(nlogn)不稳定

关键代码示例 ​

冒泡排序（外层控制轮数，内层比较交换）：

java
public static void bubbleSort(int[] array) {
    int length = array.length;
    for (int i = 0; i < length; i++) {           // 外层：轮数
        for (int j = 0; j < length - 1 - i; j++) { // 内层：每轮找出一个较大值
            if (array[j] > array[j + 1]) {        // 前大后小则交换
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

快速排序（分区 + 递归）：

java
private static int partition(int[] array, int left, int right) {
    int temp = array[left];              // 基准
    while (right > left) {
        while (temp <= array[right] && left < right) --right;  // 右找小
        if (left < right) { array[left] = array[right]; ++left; }
        while (temp >= array[left] && left < right) ++left;    // 左找大
        if (left < right) { array[right] = array[left]; --right; }
    }
    array[left] = temp;
    return left;
}

二分查找 ​

  • 前提：有序表，时间复杂度 O(log₂n)，插入删除困难。
  • mid 计算防溢出：mid = (low + high) / 2 在 low+high 溢出时出错，改用 mid = low + (high - low) / 2。
java
int low = 0, high = arr.length - 1;
while (low <= high) {
    int mid = (low + high) >>> 1;   // 无符号右移，等效防溢出
    if (key < arr[mid]) high = mid - 1;
    else if (key > arr[mid]) low = mid + 1;
    else return mid;
}
return -1;

一致性哈希 ​

  • 问题：普通 Hash 在集群节点数 N 变化时，全部映射失效（缓存全失效，灾难性）。
  • 解法：把哈希值空间组织成虚拟环，数据沿环顺时针找第一个节点。
  • 效果：节点增减只重定位该节点到环上前一节点之间的数据，容错性好、可扩展。
  • 四特性：平衡性、单调性、分散性、负载；用虚拟节点解决节点少时分布不均。

不变量（必须成立的约束） ​

  • 二分查找前提是有序。
  • 快排最坏 O(n²) 出现在基准选得极端（如已有序时选首元素）。
  • 一致性哈希节点增减只影响相邻区间，不影响全局。

常见误解 ​

  • 以为「选择排序比冒泡快」→ 都是 O(n²)，选择只是交换次数少。
  • 以为「快排永远 O(nlogn)」→ 最坏退化为 O(n²)。
  • 以为「(low+high)/2 没问题」→ 极端情况会整型溢出。

关联 ​

最近更新