21xrx.com
2024-11-22 03:26:53 Friday
登录
文章检索 我的文章 写文章
C++经典算法题解析
2023-07-08 05:07:40 深夜i     --     --
C++ 经典算法 题解 数据结构 编程思路

C++作为一门面向对象的编程语言，被广泛应用于软件开发、数据结构和算法研究等领域。在算法研究领域，C++常常被用于解决一些经典算法问题，如排序、查找、串匹配、图算法、动态规划等。本文将重点讨论C++中一些经典算法及其实现。

一、排序算法

排序算法是一种将一个序列按照一定顺序重新排列的算法，是常用的算法之一。常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等。

1.冒泡排序

冒泡排序是一种基本的交换排序算法，思路是在每一轮排序过程中，将相邻的两个数进行比较，如果前面的数大于后面的数，则交换两个数的位置，直到最后两个数都排好序为止。

C++代码：

void bubbleSort(int array[], int n) {

  for (int i = 0; i < n - 1; i++) {

    for (int j = 0; j < n - i - 1; j++) {

      if (array[j] > array[j + 1]) {

        swap(array[j], array[j + 1]);

      }

    }

  }

}

2.插入排序

插入排序是一种通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入的算法。插入排序属于稳定排序，时间复杂度为O(n^2)。

C++代码：

void insertionSort(int array[], int n) {

  for (int i = 1; i < n; i++) {

    int key = array[i];

    int j = i - 1;

    while (j >= 0 && array[j] > key) {

      array[j + 1] = array[j];

      j--;

    }

    array[j + 1] = key;

  }

}

3.选择排序

选择排序是一种简单直观的排序算法，思想是每次从待排序的数据中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的部分中选出最小（或最大）的一个元素，以此类推，直到整个序列有序为止。

C++代码：

void selectionSort(int array[], int n) {

  for (int i = 0; i < n - 1; i++) {

    int minIndex = i;

    for (int j = i + 1; j < n; j++) {

      if (array[j] < array[minIndex])

        minIndex = j;

    }

    swap(array[i], array[minIndex]);

  }

}

4.快速排序

快速排序是一种常用的排序算法，采用分治思想，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有元素都比另外一部分小，然后再按此方法对这两部分分别进行快速排序，最终得到有序序列。

C++代码：

int partition(int array[], int low, int high) {

  int pivot = array[low];

  while (low < high) {

    while (low < high && array[high] >= pivot)

      high--;

    array[low] = array[high];

    while (low < high && array[low] <= pivot) {

      low++;

    }

    array[high] = array[low];

  }

  array[low] = pivot;

  return low;

}

void quickSort(int array[], int low, int high) {

  if (low < high) {

    int pivotPos = partition(array, low, high);

    quickSort(array, low, pivotPos - 1);

    quickSort(array, pivotPos + 1, high);

  }

}

5.归并排序

归并排序是一种分治算法，它的思路是将待排序的元素分成大小相同的两个子序列，分别对两个子序列进行排序，最后合并两个有序序列得到一个有序序列。

C++代码：

void merge(int array[], int left, int mid, int right, int temp[]) {

  int i = left, j = mid + 1;

  int k = left;

  while (i <= mid && j <= right) {

    if (array[i] <= array[j]) {

      temp[k++] = array[i++];

    } else {

      temp[k++] = array[j++];

    }

  }

  while (i <= mid) {

    temp[k++] = array[i++];

  }

  while (j <= right) {

    temp[k++] = array[j++];

  }

  for (int p = left; p <= right; p++) {

    array[p] = temp[p];

  }

}

void mergeSort(int array[], int left, int right, int temp[]) {

  if (left < right) {

    int mid = left + (right - left) / 2;

    mergeSort(array, left, mid, temp);

    mergeSort(array, mid + 1, right, temp);

    merge(array, left, mid, right, temp);

  }

}

二、查找算法

查找是一种常用的算法，其作用是在给定的数据集合中寻找特定数据。常见的查找算法有线性查找、折半查找、哈希查找等。

1.线性查找

线性查找是一种基本的查找算法，它的思想是逐一扫描待查找的数据，直到找到目标数据或扫描完整个数据集合为止。

C++代码：

int linearSearch(int array[], int n, int target) {

  for (int i = 0; i < n; i++) {

    if (array[i] == target)

      return i;

  }

  return -1;

}

2.折半查找

折半查找又称二分查找，是一种非常高效的查找算法，它的思路是先将待查找的数据按升序排列，然后通过不断二分的方式逐步缩小查找区间，最终找到目标数据或确认目标数据不存在于数据集合中。

C++代码：

int binarySearch(int array[], int left, int right, int target) {

  while (left <= right) {

    int mid = left + (right - left) / 2;

    if (array[mid] == target)

      return mid;

     else if (array[mid] < target) {

      left = mid + 1;

    } else

      right = mid - 1;

  }

  return -1;

}

三、动态规划

动态规划是解决最优化问题的一种常用算法，其思路是通过将原问题分解成多个子问题，逐步求解子问题的最优解，最终得到原问题的最优解。

1.背包问题

背包问题是一类经典的优化问题，其基本思想是用有限的空间容器装载一些物品，使得装载的物品价值最大。常见的背包问题有0-1背包、完全背包等。

C++代码：

int knapsack(int weight[], int value[], int capacity, int n) {

  vector > dp(n + 1, vector (capacity + 1, 0));

  for (int i = 1; i <= n; i++) {

    for (int j = 1; j <= capacity; j++) {

      if (j < weight[i - 1]) {

        dp[i][j] = dp[i - 1][j];

      } else {

        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);

      }

    }

  }

  return dp[n][capacity];

}

2.最长公共子序列

最长公共子序列问题是一类经典问题，其基本思想是在两个序列中找到一个最长的公共子序列，即从两个给定序列中找到一个新的序列，新序列中的元素也在原序列中出现，但顺序可以不同。

C++代码：

int longestCommonSubsequence(string str1, string str2) {

  int m = str1.length(), n = str2.length();

  vector > dp(m + 1, vector (n + 1, 0));

  for (int i = 1; i <= m; i++) {

    for (int j = 1; j <= n; j++) {

      if (str1[i - 1] == str2[j - 1]) {

        dp[i][j] = dp[i - 1][j - 1] + 1;

      } else {

        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

      }

    }

  }

  return dp[m][n];

}

以上就是C++中一些经典的算法及其实现，这些算法在程序员的日常工作中有着广泛的应用。希望读者能够通过学习这些算法，增长自己的知识储备，提高自己的编程能力。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复