C++ 经典算法代码 |21xrx.com

C++ 经典算法代码

2023-07-05 02:31:42 深夜i -- --

C++ 算法经典代码数据结构

C++是一种功能丰富，速度快，更具可移植性的编程语言。一些经典算法可以轻松地通过C++实现。在这篇文章中，我们将介绍一些C++经典算法代码。

1.快速排序：

快速排序是一种常见的排序算法，它基于分治策略，在平均情况下，时间复杂度为O(nlogn)，可以轻松地用C++编写。

void quickSort(int arr[], int left, int right)

{

int i = left, j = right;

int tmp;

int pivot = arr[(left + right) / 2];

/* partition */

while (i <= j) {

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)

j--;

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

i++;

j--;

}

};

/* recursion */

if (left < j)

quickSort(arr, left, j);

if (i < right)

quickSort(arr, i, right);

}

2. 二分查找：

二分查找算法是在有序数组中查找特定元素的常用算法。它的时间复杂度为O(logn)。可以使用C++编写以下代码：

int binarySearch(int arr[], int left, int right, int x)

{

if (right >= left) {

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

if (arr[mid] == x)

return mid;

if (arr[mid] > x)

return binarySearch(arr, left, mid - 1, x);

return binarySearch(arr, mid + 1, right, x);

}

// 没有找到元素

return -1;

}

3. 合并排序：

合并排序是一种基于归并（Merge）操作的分治算法。它的时间复杂度为O(nlogn)，可以用C++实现。

void merge(int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

int 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(int 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);

}

最后，以上是C++实现的三种经典算法。我们可以通过他们更好地理解C++语言的强大功能。

上一篇: idea打包java可执行jar包

下一篇: C++模板的使用

评论区

()

相似文章