實現常見演算法的可重用模板函數

一、演算法和模板函數

演算法是程序設計過程中解決問題的具體操作步驟，而模板函數是一種通用的、可重用的函數模板，使得我們能夠專註於問題解決本身，而不需要重複編寫相同的代碼。將演算法轉換為模板函數則能夠使我們獲得更高的代碼重用性和提高代碼的可維護性。

我們將以常見的三種演算法作為例子，介紹如何將它們轉換成模板函數:

二、排序演算法

1、冒泡排序: 冒泡排序是最為基本的排序演算法之一，它是通過比較相鄰元素的大小來實現排序的。

template<typename T>
void bubbleSort(T* arr, int n)
{
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

2、選擇排序: 選擇排序是一種簡單直觀的排序演算法，時間複雜度為O(n^2)，空間複雜度為O(1)。

template<typename T>
void selectionSort(T* arr, int n)
{
    for (int i = 0; i < n - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

3、插入排序: 插入排序是一種簡單直觀的排序演算法，它將待排序的數組分為兩部分（已經排序的和未排序的），一開始已排序數組只包含一個元素，然後將未排序部分的元素一個一個插入到已排序的數組中，進行排序的過程。

template<typename T>
void insertionSort(T* arr, int n)
{
    for (int i = 1; i < n; ++i) {
        for (int j = i; j > 0; --j) {
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
            else {
                break;
            }
        }
    }
}

三、查找演算法

1、順序查找: 順序查找就是按照順序依次查找，它的平均複雜度為O(n)。

template<typename T>
int sequentialSearch(const T* arr, int n, const T& target)
{
    for (int i = 0; i < n; ++i) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

2、二分查找: 二分查找是一種十分常用的查找演算法，它的平均複雜度為O(log n)。

template<typename T>
int binarySearch(const T* arr, int n, const T& target)
{
    int l = 0;
    int r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (target < arr[mid]) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return -1;
}

四、字元串演算法

1、字元串比較: 字元串比較函數用於比較兩個字元串的大小，它的平均複雜度為O(n)。

template<typename T>
int stringCompare(const T& str1, const T& str2)
{
    int len1 = str1.size();
    int len2 = str2.size();
    int len = min(len1, len2);
    for (int i = 0; i < len; ++i) {
        if (str1[i] != str2[i]) {
            return (str1[i] < str2[i]) ? -1 : 1;
        }
    }
    if (len1 == len2) {
        return 0;
    }
    return (len1 < len2) ? -1 : 1;
}

2、字元串匹配: 字元串匹配演算法是指在一個文本串中匹配一個模式串的位置，它的平均複雜度為O(n+m)。

int kmpSearch(const string& text, const string& pattern)
{
    int n = text.length();
    int m = pattern.length();
    vector<int> next(m, 0);
    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        next[i] = j;
    }
    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

五、總結

將演算法轉換為通用的、可重用的模板函數，能夠提高代碼的重用性和可維護性，減少代碼複雜度，方便程序員理解和使用。

在C++中，我們可以通過函數模板來實現通用性，使得函數具有普遍適用性，不需對特定類型進行處理或多次編寫相似的代碼。函數模板的語法非常簡單，只需聲明時使用類似於定義模板函數模板參數的方式即可。