BFPRT算法詳解

一、BFPRT算法原理

BFPRT算法（也稱為中位數的中位數算法）是基於快速排序算法基礎上的變種算法，用於尋找一個無序數組中第K小的數（或第K大的數）。

快速排序算法的核心思想是把一個無序數組的第一個數作為劃分元素，將數組分為兩個部分，左邊部分的數都小於劃分元素，右邊部分的數都大於劃分元素，然後分別對左邊和右邊的部分進行遞歸調用。但是快速排序算法的時間複雜度並不穩定，最壞情況下時間複雜度為O(n^2)，這時候就需要使用BFPRT算法來解決這個問題。

BFPRT算法的核心思想是通過對數組進行特殊的劃分，確定第K小的數所在的區間。它首先將數組分成若干個5個元素一組的區間，對每個小區間進行排序，然後取出每個小區間的中位數，把這些中位數作為一個新的數組。

然後遞歸尋找這個數組的中位數（即第N/2小的數），假設這個數是x，那麼以x為中心，將數組分成兩部分，如果新數組中數的個數比x小，說明第K小的數在新數組後半部分，否則在新數組前半部分。對於所選擇的部分，再次遞歸調用進行查找，直到找到第K小的數。

int partition_median(int arr[], int left, int right) {
    // 將數組以每5個元素為一組分組，最後剩下的不足5個的單獨一組
    for (int i = left; i  right) {
            sub_right = right;
        }
        // 將小組進行插入排序，可以提高查找中位數的效率
        for (int j = i + 1; j = i && arr[k] > key) {
                arr[k + 1] = arr[k];
                k--;
            }
            arr[k + 1] = key;
        }
        // 將每個小組的中位數插入到數組的前面，方便後面進行遞歸查找
        int mid = (i + sub_right) / 2;
        int temp = arr[mid];
        arr[mid] = arr[left + (i - left) / 5];
        arr[left + (i - left) / 5] = temp;
    }
    // 遞歸查找所有中位數的中位數
    int median = (left + (right - left) / 10);
    if (left < right) {
        int pivotIndex = partition_median(arr, left, right);
        int i = partition(arr, left, right, pivotIndex);
        if (median  i) {
            // 第K小的數在數組右半部分
            return partition_median(arr, i + 1, right);
        }
        else {
            // 找到第K小的數，返回其值
            return arr[i];
        }
    }
    else {
        // 數組中只有一個元素，直接返回該元素的值
        return arr[left];
    }
}

二、BFPRT算法應用

1、尋找無序數組的中位數或第K小/大的數：使用定位排序算法，將數組劃分成若干個小組，對每個小組進行排序，然後將每個小組的中位數插入到一個新數組中，對新數組遞歸查找其中位數，以此確定第K小/大的數的位置。

int bfprt(int arr[], int left, int right, int k) {
    return partition_median(arr, left, right, k);
}

int main() {
    int arr[] = {3, 2, 1, 5, 6, 4};
    int k = 2; // 尋找第二小的數
    int n = sizeof(arr) / sizeof(arr[0]);
    int ans = bfprt(arr, 0, n - 1, k - 1);
    cout << "第" << k << "小的數是：" << ans << endl;
}

2、求無序數組的中位數與排序時間的實現：使用標準庫函數qsort排序，然後計算數組的中位數。這裡定義了一個類，其中構造函數中調用了qsort函數，並獲取數組的中位數，計算排序所需的時間。

class Median {
public:
    double median_;
    double sort_time_;

    Median(int arr[], int n) {
        clock_t start_time = clock();
        qsort(arr, n, sizeof(int), cmp);
        sort_time_ = (double)(clock() - start_time) / CLOCKS_PER_SEC;

        if (n % 2 == 0) {
            median_ = (double)(arr[n / 2 - 1] + arr[n / 2]) / 2.0;
        } else {
            median_ = (double)arr[n / 2];
        }
    }

    static int cmp(const void* a, const void* b) {
        return *(int*)a - *(int*)b;
    }
};

int main() {
    int arr[] = {3, 2, 1, 5, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = (n + 1) / 2;
    Median m(arr, n);
    cout << "排序所需時間: " << m.sort_time_ << "s" << endl;
    cout << "無序數組的中位數: " << m.median_ << endl;
}

三、BFPRT算法的優缺點

優點：

1、時間複雜度穩定，最壞情況下也只需要O(n)的時間複雜度。

2、與快速排序算法相比，BFPRT算法在大量數據的排序上表現更加優秀。

3、在尋找數組中第K小/大的數時，其所需時間不超過O(n)。

缺點：

1、在查找較小的K值時，效率可能會變慢。尤其是當K比較小，但N非常大的時候，會造成很大的時間開銷。

2、算法比較複雜，實現起來比較困難。

四、BFPRT算法的應用案例

1、使用BFPRT算法實現一道LeetCode的問題，尋找亂序數組中的第K大的元素。

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        int n = nums.size();
        int arr[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nums[i];
        }
        int ans = bfprt(arr, 0, n - 1, n - k);
        return ans;
    }
};

int main() {
    Solution s;
    vector nums = {3,2,1,5,6,4};
    int k = 2;
    int ans = s.findKthLargest(nums, k);
    cout << "第" << k << "大的數是：" << ans << endl;
}

2、使用BFPRT算法對海量數據進行快速排序。

// 將數組劃分成若干個小區間，對每個小區間排序，然後獲取各個小區間的中位數即可
template 
void bfprt_sort(vector& nums, int left, int right, int k) {
    if (left >= right) {
        return;
    }
    if (right - left + 1 <= 5) {
        sort(nums.begin()+left, nums.begin()+right+1);
        return;
    }
    int pivotIndex = partition_median(nums, left, right);
    int index = partition(nums, left, right, pivotIndex);
    if (k  index) {
        bfprt_sort(nums, index+1, right, k);
    } else {
        return;
    }
}

template 
void big_data_sort(vector& nums) {
    int len = nums.size();
    int left = 0;
    int right = len - 1;
    int group_num = len / 5;
    int mod_num = len % 5;
    vector helper;
    for (int i = 0; i  0) {
        sort(nums.begin() + group_num*5, nums.begin() + group_num*5 + mod_num);
        helper.push_back(nums[group_num*5 + mod_num/2]);
    }
    // 新數組中的中位數即為整個數組的中位數
    int median_index = helper.size() / 2;
    bfprt_sort(helper, 0, helper.size()-1, median_index);
    T median = helper[median_index];
    // 使用整個數組的中位數進行劃分
    int pivot_index = partition_big_data(nums, left, right, median);
    int k = len / 2;
    if (len % 2 == 0) {
        bfprt_sort(nums, left, right, k-1);
    } else {
        bfprt_sort(nums, left, right, k);
    }
}