With the rapid adoption of mobile payments, credit card fraud detection (CCFD) has become increasingly critical, exhibiting a significant and persistent upward trend. Accurately identifying fraudulent transactions within large datasets is a major challenge, exacerbated by high data imbalance and overlapping distributions, which frequently result in misclassification and insufficient detection of fraud. Existing algorithms also suffer from inefficiency in handling large-scale data. To overcome these limitations, we propose a Random Sample Partition-based Ensemble Algorithm for Credit Card Fraud Detection (RSP-CCFD). The RSP-CCFD algorithm employs advanced sampling techniques to partition massive datasets into smaller data blocks (RSP blocks), preserving the probability distribution and substantially enhancing computational efficiency. Additionally, we introduce the SAE-SMOTE interpolation algorithm to reduce the overlap between synthetic fraudulent samples and original legitimate transactions. By integrating multiple classifiers via ensemble learning, RSP-CCFD achieves more comprehensive fraud detection coverage and improved accuracy and robustness. Extensive experimental validation demonstrates the superior performance of RSP-CCFD compared to eight existing data-level and algorithm-level methods in CCFD tasks.