分块查找（Block Search）实现

概念介绍

分块查找是一种 改进的顺序查找方法，适用于 静态数据，即数据不频繁增删的情况。它的基本思想是 将有序数据分成若干块，然后进行两步查找：

索引查找（块定位）：使用索引表快速定位元素所在的块。
块内顺序查找：在确定的块内进行 顺序查找。

适用场景

适用于 静态有序数组（数据较大但查询频繁，变动较少）。
适用于 查询速度较高的情况，因为它可以减少顺序查找的范围，提高查询效率。

1. 实现思路

分块排序适用于超大数据集的排序问题，核心思路如下：

数据分块：将超大数据拆分成若干小块，每个块大小由内存决定。
块内排序：每个小块独立排序（可使用插入排序、冒泡排序等）。
归并多个块：合并排序后的块，得到最终有序结果。

2. 代码实现

#include <iostream>

using namespace std;

// **交换函数**
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// **插入排序（用于小块排序）**
void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; 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;
    }
}

// **合并两个有序块**
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    int i = 0, j = 0, k = 0;

    // 归并两个有序数组
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    // 复制剩余元素
    while (i < leftSize) arr[k++] = left[i++];
    while (j < rightSize) arr[k++] = right[j++];
}

// **分块排序（模拟大数据排序）**
void blockSort(int arr[], int size, int blockSize) {
    int numBlocks = (size + blockSize - 1) / blockSize;  // 计算需要多少块

    // **第一步：对每个块进行排序**
    for (int i = 0; i < numBlocks; i++) {
        int start = i * blockSize;
        int end = (start + blockSize < size) ? (start + blockSize) : size;
        insertionSort(arr + start, end - start);  // 对块进行插入排序
    }

    // **第二步：归并已排序的块**
    int *temp = new int[size];
    for (int i = 1; i < numBlocks; i++) {
        int leftSize = i * blockSize;
        int rightSize = (i + 1) * blockSize > size ? size - leftSize : blockSize;

        // 归并当前块与已合并部分
        merge(temp, arr, leftSize, arr + leftSize, rightSize);

        // 复制回原数组
        for (int j = 0; j < leftSize + rightSize; j++) {
            arr[j] = temp[j];
        }
    }

    delete[] temp;
}

// **测试代码**
int main() {
    int arr[] = {20, 5, 12, 8, 15, 7, 3, 9, 1, 6, 17, 11};
    int size = sizeof(arr) / sizeof(arr[0]);
    int blockSize = 4;  // 设定块大小（内存限制）

    cout << "排序前：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    blockSort(arr, size, blockSize);  // 执行分块排序

    cout << "排序后：";
    for (int i = 0; i < size; i++) cout << arr[i] << " ";
    cout << endl;

    return 0;
}

3. 代码解析

insertionSort：
- 采用插入排序进行小块排序（适用于小规模数据）。
merge：
- 采用两路归并合并两个有序块。
blockSort：
- 第一步：按 blockSize 大小分块并逐个排序。
- 第二步：采用两两归并合并所有已排序的块。