合肥seo按天扣费,网站同时做竞价和优化可以吗,苏州信息网,网站在那里C/C编程语言因其高效、灵活和底层的特性#xff0c;被广大开发者用于实现各种复杂算法。本文将通过10个具体的算法案例#xff0c;详细探讨C/C在算法实现中的技巧和应用。 一、冒泡排序#xff08;Bubble Sort#xff09;
冒泡排序#xff08;Bubble Sort#xff09;是一…C/C编程语言因其高效、灵活和底层的特性被广大开发者用于实现各种复杂算法。本文将通过10个具体的算法案例详细探讨C/C在算法实现中的技巧和应用。 一、冒泡排序Bubble Sort
冒泡排序Bubble Sort是一种简单的排序算法。它重复地遍历要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
以下是使用C实现冒泡排序的代码
#includeiostream
using namespace std;void bubbleSort(int arr[], int n) {for(int i 0; i n-1; i) { for (int j 0; j n-i-1; j) { if (arr[j] arr[j1]) {// swap arr[j] and arr[j1]int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}
}void printArray(int arr[], int size) {for (int i0; i size; i) {cout arr[i] ;}cout endl;
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr)/sizeof(arr[0]);bubbleSort(arr, n);coutSorted array: \n;printArray(arr, n);return 0;
}这段代码首先定义了一个名为bubbleSort的函数该函数接受一个整数数组和数组的长度作为输入。在函数内部我们使用两个嵌套的for循环来进行排序。外层循环表示我们总共需要进行的排序轮数内层循环表示每轮排序中我们需要进行的比较次数。如果当前元素大于下一个元素我们就交换这两个元素的位置。这样经过多轮排序后最大的元素就会被冒泡到数组的末尾。然后我们继续对剩下的元素进行同样的操作直到所有元素都被排序。最后我们在main函数中调用bubbleSort函数对数组进行排序并打印出排序后的结果。
二、快速排序Quick Sort
快速排序Quick Sort是由C.A.R. Hoare在1960年提出的一种排序算法。快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小然后分别对这两部分继续进行排序以达到整个序列有序。
以下是使用C实现快速排序的代码
#includeiostream
using namespace std;int partition(int arr[], int low, int high) {int pivot arr[high]; int i (low - 1); for (int j low; j high - 1; j) {if (arr[j] pivot) {i; swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return (i 1);
}void quickSort(int arr[], int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); }
}void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}int main() {int arr[] {10, 7, 8, 9, 1, 5};int n sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);cout Sorted array: \n;printArray(arr, n);return 0;
}这段代码首先定义了一个名为partition的函数该函数接受一个整数数组以及两个索引low和high作为输入。这个函数的主要目的是选取一个基准元素这里我们选择了数组的最后一个元素然后将数组分为两部分一部分的元素都小于基准元素另一部分的元素都大于基准元素。partition函数返回的是基准元素的最终位置。然后我们定义了一个名为quickSort的函数该函数递归地对基准元素左右两侧的子数组进行同样的操作直到整个数组都被排序。最后我们在main函数中调用quickSort函数对数组进行排序并打印出排序后的结果。
三、插入排序Insertion Sort
插入排序Insertion Sort是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上通常采用in-place排序即只需用到O(1)的额外空间的排序因而在从后向前扫描过程中需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。
以下是使用C实现插入排序的代码
#includeiostream
using namespace std;void insertionSort(int arr[], int n) {int i, key, j;for (i 1; i n; i) {key arr[i];j i - 1;/* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}arr[j 1] key;}
}void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}int main() {int arr[] {12, 11, 13, 5, 6};int n sizeof(arr) / sizeof(arr[0]);insertionSort(arr, n);cout Sorted array: \n;printArray(arr, n);return 0;
}这段代码首先定义了一个名为insertionSort的函数该函数接受一个整数数组以及数组的长度作为输入。在函数内部我们使用一个for循环来遍历数组中的每个元素。对于每个元素我们都将其保存到一个名为key的变量中然后将其与前面已经排序好的元素进行比较。如果前面的元素大于key我们就将前面的元素向后移动一位为key腾出位置。我们一直这样操作直到找到key应该插入的位置然后将key插入到该位置。最后我们在main函数中调用insertionSort函数对数组进行排序并打印出排序后的结果。
四、选择排序Selection Sort
选择排序算法详解
选择排序是一种简单且直观的排序算法它的基本思想是遍历数组找到最小或最大的元素将其放到排序序列的起始位置。然后从剩余未排序元素中继续寻找最小或最大元素放到已排序序列的末尾。如此重复直到所有元素均排序完毕。
算法步骤
在未排序序列中找到最小或最大元素存放到排序序列的起始位置。从剩余未排序元素中继续寻找最小或最大元素然后放到已排序序列的末尾。重复第二步直到所有元素均排序完毕。
时间复杂度
最好情况O(n^2)最坏情况O(n^2)平均情况O(n^2)
空间复杂度O(1)
稳定性不稳定考虑[3, 3, 2]这个例子第一个3会被移动到2的后面从而两个3的顺序颠倒了。
C/C代码实现
下面是一个使用C实现的选择排序的例子
#include iostream
using namespace std;void selectionSort(int 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; // 更新最小元素的位置}}// 将找到的最小元素与第一个未排序的元素交换位置if (minIndex ! i) {swap(arr[i], arr[minIndex]);}}
}int main() {int arr[] {64, 25, 12, 22, 11};int n sizeof(arr) / sizeof(arr[0]);selectionSort(arr, n);cout Sorted array: \n;for (int i 0; i n; i) {cout arr[i] ;}return 0;
}在这个例子中selectionSort函数实现了选择排序算法。它接受一个整数数组和数组的长度作为输入并按升序对数组进行排序。main函数创建了一个待排序的数组并调用selectionSort函数对其进行排序。最后它打印出排序后的数组。
五、归并排序Merge Sort
归并排序Merge Sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为2-路归并。
以下是使用C实现归并排序的代码
#includeiostream
#includevector
using namespace std;void merge(vectorint arr, int l, int m, int r) {int i, j, k;int n1 m - l 1;int n2 r - m;vectorint L(n1), R(n2);for (i 0; i n1; i)L[i] arr[l i];for (j 0; j n2; j)R[j] arr[m 1 j];i 0; j 0; k l; while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];i;} else {arr[k] R[j];j;}k;}while (i n1) {arr[k] L[i];i;k;}while (j n2) {arr[k] R[j];j;k;}
}void mergeSort(vectorint arr, int l, int r) {if (l r) {int m l (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m 1, r);merge(arr, l, m, r);}
}void printArray(vectorint arr) {int arr_size arr.size();for (int i 0; i arr_size; i) {cout arr[i] ;}cout endl;
}int main() {vectorint arr {12, 11, 13, 5, 6, 7};int arr_size arr.size();cout Given array is \n;printArray(arr);mergeSort(arr, 0, arr_size - 1);cout \nSorted array is \n;printArray(arr);return 0;
}这段代码首先定义了一个名为merge的函数该函数用于合并两个已经排序好的子数组。然后定义了一个名为mergeSort的函数该函数使用递归的方式将数组不断地拆分为更小的子数组直到每个子数组只包含一个元素然后将这些子数组合并起来。在main函数中我们创建了一个整数数组然后调用mergeSort函数对数组进行排序并打印出排序后的结果。
六、堆排序Heap Sort
堆排序算法详解
堆排序Heap Sort是一种基于二叉堆Binary Heap的排序算法。它利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构并同时满足堆积的性质即子节点的键值或索引总是小于或者大于它的父节点。
算法步骤
创建一个最大堆或最小堆。最大堆的父节点大于或等于其子节点最小堆则相反。将堆顶元素与末尾元素互换这样最大元素或最小元素就被移到了数组末尾。减小堆的大小并重新调整堆结构使其保持最大堆或最小堆的性质。重复步骤2和3直到整个数组排序完成。
时间复杂度
最好情况O(nlogn)最坏情况O(nlogn)平均情况O(nlogn)
空间复杂度O(1)
稳定性不稳定考虑[3, 3, 2]这个例子第一个3会被移动到2的后面从而两个3的顺序颠倒了。
C/C代码实现
以下是一个使用C实现堆排序的例子
#include iostream
#include vector
#include algorithm
using namespace std;// 调整堆结构使其保持最大堆的性质
void maxHeapify(vectorint nums, int i, int heapSize) {int largest i; // 初始化最大值为当前节点iint left 2 * i 1; // 左子节点索引int right 2 * i 2; // 右子节点索引// 如果左子节点大于当前最大值则更新最大值索引if (left heapSize nums[left] nums[largest]) {largest left;}// 如果右子节点大于当前最大值则更新最大值索引if (right heapSize nums[right] nums[largest]) {largest right;}// 如果最大值不是当前节点i则交换它们的值并递归调整子堆结构if (largest ! i) {swap(nums[i], nums[largest]);maxHeapify(nums, largest, heapSize);}
}// 构建最大堆
void buildMaxHeap(vectorint nums) {int heapSize nums.size();// 从最后一个非叶子节点开始逐个向上调整堆结构for (int i heapSize / 2 - 1; i 0; i--) {maxHeapify(nums, i, heapSize);}
}// 堆排序函数
void heapSort(vectorint nums) {int heapSize nums.size();// 构建最大堆buildMaxHeap(nums);// 将堆顶元素与末尾元素交换并重新调整堆结构直到整个数组排序完成for (int i nums.size() - 1; i 0; i--) {swap(nums[0], nums[i]); // 将堆顶元素与末尾元素交换heapSize--; // 减小堆的大小maxHeapify(nums, 0, heapSize); // 重新调整堆结构使其保持最大堆的性质}
}int main() {vectorint nums {3, 7, 1, 9, 2, 8, 5, 6, 4}; // 待排序数组heapSort(nums); // 使用堆排序对数组进行排序cout Sorted array: ; // 输出排序后的数组for (int num : nums) {cout num ;}cout endl; // 换行符使输出更美观return 0; // 程序正常结束返回0作为状态码
}七、二分查找Binary Search
二分查找算法详解
二分查找Binary Search是一种在有序数组中查找特定元素的搜索算法。它的工作原理是首先将数组的中间元素与目标值进行比较如果两者相等则查找成功如果目标值小于中间元素则在数组的左半部分继续查找如果目标值大于中间元素则在数组的右半部分继续查找。如此重复每次都将搜索范围缩小一半直到找到目标值或者搜索范围为空即找不到目标值。
算法步骤
确定数组的中间元素的下标 mid (left right) / 2。如果数组为空或 left right则返回 -1 或抛出异常表示未找到目标值。如果中间元素等于目标值则返回 mid。如果目标值小于中间元素则在左半部分left, mid - 1继续查找。如果目标值大于中间元素则在右半部分mid 1, right继续查找。重复步骤 1-5直到找到目标值或确定目标值不存在于数组中。
时间复杂度O(log n)其中 n 是数组的长度。
C/C代码实现
以下是使用C实现二分查找算法的一个例子
#include iostream
#include vector
using namespace std;int binarySearch(vectorint nums, int target) {int left 0;int right nums.size() - 1;while (left right) {int mid left (right - left) / 2; // 防止溢出if (nums[mid] target) {return mid; // 找到目标值返回其下标} else if (nums[mid] target) {left mid 1; // 在右半部分继续查找} else {right mid - 1; // 在左半部分继续查找}}return -1; // 未找到目标值返回 -1
}int main() {vectorint nums {1, 3, 5, 7, 9}; // 有序数组int target 5; // 要查找的目标值int result binarySearch(nums, target); // 调用二分查找函数if (result ! -1) {cout Target found at index: result endl; // 输出找到目标值的下标} else {cout Target not found in the array. endl; // 输出未找到目标值的消息}return 0;
}在这个例子中我们定义了一个名为 binarySearch 的函数它接受一个有序整数数组 nums 和一个目标值 target 作为输入并返回目标值在数组中的下标如果找到的话否则返回 -1。在主函数 main 中我们创建了一个有序数组 nums 和一个目标值 target然后调用 binarySearch 函数进行查找。最后根据函数的返回值输出相应的消息。
八、动态规划Dynamic Programming
动态规划算法详解
动态规划Dynamic Programming简称DP是一种在数学、计算机科学和经济学中使用的通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
动态规划的基本思想是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。
基本步骤
描述问题的最优解的结构这一步通常是通过递归关系式来描述原问题的最优解是如何由子问题的最优解构成的。定义状态这一步是定义一个或多个状态变量来刻画子问题的解。状态转移方程根据上一步定义的状态写出状态转移方程描述如何从子问题的解构造出原问题的解。边界条件明确问题的边界条件也就是最小的子问题的解。计算最优解根据状态转移方程和边界条件从最小的子问题开始逐步计算原问题的最优解。
举例说明0-1背包问题
问题描述给定一组物品每种物品都有自己的重量和价值在限定的总重量内我们如何选择才能使得物品的总价值最大。
假设物品数量为n每种物品i的重量为w[i]价值为v[i]背包的总容量为W。定义dp[i][j]为考虑前i个物品且背包容量为j时的最大价值。
状态转移方程为dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) (当j w[i])
边界条件为dp[0][j] 0 (0 j W) 和 dp[i][0] 0 (0 i n)
C代码实现如下
#includeiostream
#includevector
#includealgorithm
using namespace std;int knapsack(int W, vectorint wt, vectorint val, int n) {vectorvectorint dp(n 1, vectorint(W 1, 0));for (int i 1; i n; i) {for (int w 1; w W; w) {if (wt[i - 1] w) {dp[i][w] max(val[i - 1] dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);} else {dp[i][w] dp[i - 1][w];}}}return dp[n][W];
}int main() {int W 50; // 背包容量vectorint wt {10, 20, 30}; // 物品重量vectorint val {60, 100, 120}; // 物品价值int n wt.size(); // 物品数量cout 最大价值为 knapsack(W, wt, val, n) endl;return 0;
}这段代码通过动态规划解决了0-1背包问题输出了在背包容量为50时可以获得的最大价值。
九、深度优先搜索Depth-First Search, DFS
深度优先搜索是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点则选择其中一个作为源节点并重复以上过程整个进程反复进行直到所有节点都被访问为止。
基本步骤
访问初始节点v。标记节点v为已访问。对于v的每一个相邻节点n如果n没有被访问过则递归地深度优先搜索n。
适用场景 深度优先搜索通常用于遍历树或图寻找路径解决迷宫问题等。
C代码示例使用DFS遍历图
下面是一个简单的C代码示例用于通过深度优先搜索遍历一个图
#includeiostream
#includelist
using namespace std;class Graph {int numVertices;listint* adjLists;bool* visited;public:Graph(int vertices); void addEdge(int src, int dest);void DFS(int vertex);
};Graph::Graph(int vertices) {numVertices vertices;adjLists new listint[vertices];visited new bool[vertices];
}void Graph::addEdge(int src, int dest) {adjLists[src].push_back(dest);
}void Graph::DFS(int vertex) {visited[vertex] true;cout Visited vertex endl;listint::iterator i;for(i adjLists[vertex].begin(); i ! adjLists[vertex].end(); i) {if(!visited[*i]) {DFS(*i);}}
}int main() {Graph g(5); // 创建一个有5个顶点的图g.addEdge(0, 1); // 添加边 (0, 1)g.addEdge(0, 2); // 添加边 (0, 2)g.addEdge(1, 3); // 添加边 (1, 3)g.addEdge(2, 4); // 添加边 (2, 4)g.addEdge(3, 4); // 添加边 (3, 4)g.DFS(0); // 从顶点0开始深度优先搜索return 0;
}这个代码示例创建了一个有5个顶点的图并添加了一些边。然后它从顶点0开始进行深度优先搜索并打印出访问的顶点。注意这个示例仅用于教学目的实际应用中可能需要更复杂的错误处理和优化。
十、分治算法Divide and Conquer
分治算法Divide and Conquer详解
分治算法是一种处理大型问题的有效方法。它的核心思想是将一个难以直接解决的大问题分解成两个或更多的规模较小的相同问题直到最后子问题可以简单的直接求解然后将这些子问题的解合并得到原问题的解。
基本步骤
分解将原问题分解为若干个规模较小相互独立与原问题形式相同的子问题。解决若子问题规模较小而容易被解决则直接解否则递归地解各个子问题。合并将各个子问题的解合并为原问题的解。
适用场景 分治算法可以解决的问题一般具有以下几个特征
该问题的规模缩小到一定的程度就可以容易地解决。该问题可以分解为若干个规模较小的相同问题即该问题具有最优子结构性质。利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的即子问题之间不包含公共的子问题。
C代码示例归并排序
归并排序是分治算法的典型应用。其基本原理是将两个或更多已排序的数据序列合并成一个新的有序序列。
以下是使用C实现归并排序的代码
#includeiostream
#includevector
using namespace std;void merge(vectorint arr, int l, int m, int r) {int i, j, k;int n1 m - l 1;int n2 r - m;// 创建临时数组vectorint L(n1), R(n2);// 拷贝数据到临时数组 L[] 和 R[]for (i 0; i n1; i)L[i] arr[l i];for (j 0; j n2; j)R[j] arr[m 1 j];// 合并临时数组到 arr[l..r]i 0; // 初始化第一个子数组的索引j 0; // 初始化第二个子数组的索引k l; // 初始化合并子数组的索引while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];i;} else {arr[k] R[j];j;}k;}// 将 L[] 的剩余元素复制到 arrwhile (i n1) {arr[k] L[i];i;k;}// 将 R[] 的剩余元素复制到 arrwhile (j n2) {arr[k] R[j];j;k;}
}void mergeSort(vectorint arr, int l, int r) {if (l r) {// 找到中间点将数组一分为二进行递归排序然后合并结果。int m l (r - l) / 2;// 分治递归进行排序并合并结果。mergeSort(arr, l, m);mergeSort(arr, m 1, r);merge(arr, l, m, r); //合并结果。 对于每个数组段先排序然后合并这就实现了归并排序。这也是典型的分治策略应用。将大问题划分为小问题来解决然后将结果合并起来解决整个问题。在归并排序中我们将数组分成两半对每一半进行排序然后将两个排序好的数组合并成一个大的有序数组。这个过程一直递归进行下去直到我们得到一个完全有序的数组。递归发生在“mergeSort()”函数中而“merge()”函数是用来合并两个已经排序好的数组段。在上面的代码中“mergeSort()”函数递归地将数组分割成更小的数组直到数组的大小为1这意味着它已经排序好了。然后“merge()”函数被调用来将这些小数组两两合并成更大的有序数组。这个过程一直进行下去直到我们得到原始数组的一个完全有序的版本。在这个实现中“merge()”函数用了一个非常简单的技巧来避免额外的空间复杂度——它使用了两个临时的数组L和R来存储分割的数组段然后将它们合并回原始数组中。这意味着归并排序的空间复杂度是O(n)其中n是输入数组的大小。这是因为在任何时候我们都需要有足够的空间来存储原始数组的两个分割段。总的来说归并排序是一个非常有效且易于理解的排序算法它的时间复杂度是O(n log n)其中n是输入数组的大小。虽然它的空间复杂度比一些其他排序算法高例如堆排序和快速排序但是在许多情况下它的稳定性和简单性使得它成为了一个非常实用的选择。此外由于它的并行性即它可以很容易地分解成独立的子任务它在某些应用中例如多核处理器或多线程环境中可能会比其他排序算法更加高效。所以归并排序是分治算法的一个很好的例子展示了如何将一个大问题分解成小问题来解决然后将结果合并起来解决整个问题。它也是一个在实践中广泛使用的算法特别是在需要处理大量数据的情况下。它的时间复杂度和空间复杂度都是可预测的并且它的稳定性和简单性使得它在许多情况下都是一个非常实用的选择。最后需要注意的是虽然归并排序在理论上是一个非常优秀的算法但是在实际应用中它的性能可能会受到一些因素的影响例如数据的分布、内存访问模式等。因此在选择使用哪种排序算法时需要综合考虑这些因素以及具体的应用场景和需求。以上代码就是使用C实现归并排序的示例代码并且包含了对于分治策略应用的详细解释和代码注释说明。 endl; // 输出提示信息以帮助理解代码运行过程
}
int main() {
vectorint arr {12, 11, 13, 5, 6, 7};
int arr_size arr.size();
cout 给定的数组是\n;
for (int i 0; i arr_size; i) {
cout arr[i] ;} cout \n\n;
mergeSort(arr, 0, arr_size - 1);
cout 排序后的数组是\n;
for (int i 0; i arr_size; i) {
cout arr[i] ;} cout endl;
return 0;
} //主函数结束
