C++策略模式排序算法切换

2026-04-02 15:50:31 1457阅读 0评论

C++策略模式排序算法切换：灵活应对不同需求

在编程的世界里，选择合适的算法就像选择合适的工具一样重要。对于排序算法来说，不同的场景可能需要不同的策略。本文将介绍如何使用C++中的策略模式来实现排序算法的切换，从而提高代码的灵活性和可维护性。

策略模式的基本概念

策略模式是一种行为设计模式，它允许你定义一系列算法，把它们一个个封装起来，并且使它们可以相互替换。这样可以使算法的变化独立于使用算法的客户。

在排序算法中，我们可以将每种排序算法封装成一个策略类，然后通过一个上下文类来选择并执行具体的策略。

实现步骤

1. 定义策略接口

首先，我们需要定义一个排序策略的接口。这个接口将包含一个纯虚函数，用于执行排序操作。

class SortStrategy {
public:
    virtual ~SortStrategy() = default;
    virtual void sort(std::vector<int>& data) const = 0;
};

2. 实现具体策略类

接下来，我们实现几种具体的排序算法，如冒泡排序、快速排序和归并排序。

class BubbleSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) const override {
        for (size_t i = 0; i < data.size(); ++i) {
            for (size_t j = 0; j < data.size() - i - 1; ++j) {
                if (data[j] > data[j + 1]) {
                    std::swap(data[j], data[j + 1]);
                }
            }
        }
    }
};

class QuickSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) const override {
        quickSortRecursive(data, 0, data.size() - 1);
    }

private:
    void quickSortRecursive(std::vector<int>& data, int low, int high) {
        if (low < high) {
            int pi = partition(data, low, high);
            quickSortRecursive(data, low, pi - 1);
            quickSortRecursive(data, pi + 1, high);
        }
    }

    int partition(std::vector<int>& data, int low, int high) {
        int pivot = data[high];
        int i = low - 1;
        for (int j = low; j < high; ++j) {
            if (data[j] < pivot) {
                ++i;
                std::swap(data[i], data[j]);
            }
        }
        std::swap(data[i + 1], data[high]);
        return i + 1;
    }
};

class MergeSort : public SortStrategy {
public:
    void sort(std::vector<int>& data) const override {
        mergeSortRecursive(data, 0, data.size() - 1);
    }

private:
    void mergeSortRecursive(std::vector<int>& data, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSortRecursive(data, left, mid);
            mergeSortRecursive(data, mid + 1, right);
            merge(data, left, mid, right);
        }
    }

    void merge(std::vector<int>& data, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        std::vector<int> leftArray(n1), rightArray(n2);

        for (int i = 0; i < n1; ++i) {
            leftArray[i] = data[left + i];
        }
        for (int i = 0; i < n2; ++i) {
            rightArray[i] = data[mid + 1 + i];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                data[k++] = leftArray[i++];
            } else {
                data[k++] = rightArray[j++];
            }
        }

        while (i < n1) {
            data[k++] = leftArray[i++];
        }

        while (j < n2) {
            data[k++] = rightArray[j++];
        }
    }
};

3. 创建上下文类

上下文类负责选择并执行具体的排序策略。

class Context {
public:
    Context(SortStrategy* strategy) : strategy_(strategy) {}

    void setStrategy(SortStrategy* strategy) {
        delete strategy_;
        strategy_ = strategy;
    }

    void executeStrategy(std::vector<int>& data) const {
        strategy_->sort(data);
    }

private:
    SortStrategy* strategy_;
};

4. 使用示例

最后，我们编写一个简单的示例程序来演示如何使用策略模式切换排序算法。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};

    // 使用冒泡排序
    Context context(new BubbleSort());
    context.executeStrategy(data);
    std::cout << "Bubble Sort: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 切换到快速排序
    context.setStrategy(new QuickSort());
    context.executeStrategy(data);
    std::cout << "Quick Sort: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 切换到归并排序
    context.setStrategy(new MergeSort());
    context.executeStrategy(data);
    std::cout << "Merge Sort: ";
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 清理内存
    delete context.getStrategy();
    delete new BubbleSort();
    delete new QuickSort();
    delete new MergeSort();

    return 0;
}