实现常见算法的可重用模板函数

terry 2年前 (2023-10-01) 阅读数 382 #c++

文章标签 winxpphpmysql

一、算法和模板函数

算法是程序设计过程中解决问题的具体操作步骤，而模板函数是一种通用的、可重用的函数模板，使得我们能够专注于问题解决本身，而不需要重复编写相同的代码。将算法转换为模板函数则能够使我们获得更高的代码重用性和提高代码的可维护性。

我们将以常见的三种算法作为例子，介绍如何将它们转换成模板函数:

二、排序算法

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;
}