21xrx.com
2024-09-19 09:41:51 Thursday
登录
文章检索 我的文章 写文章
C++经典算法代码合集
2023-07-06 00:29:51 深夜i     --     --
C++ 经典算法 代码合集 数据结构 排序算法

C++是一种被广泛使用的计算机编程语言,它不仅易于学习,而且具有强大的功能和灵活性,在算法开发领域占有重要地位。下面就是一些经典算法的C++代码合集。

1. 快速排序

快速排序是一种高效的排序算法,具有O(nlogn)的平均时间复杂度。以下是快速排序的C++代码实现:

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

  int i = low;

  int j = high;

  int pivot = arr[(low + high) / 2];

  while (i <= j) {

    while (arr[i] < pivot) {

      i++;

    }

    while (arr[j] > pivot)

      j--;

    if (i <= j) {

      swap(arr[i], arr[j]);

      i++;

      j--;

    }

  }

  if (low < j) {

    quickSort(arr, low, j);

  }

  if (i < high) {

    quickSort(arr, i, high);

  }

}

2. 堆排序

堆排序是一种使用堆数据结构的排序算法,具有O(nlogn)的时间复杂度。以下是堆排序的C++代码实现:

void heapify(int arr[], int n, int i) {

  int largest = i;

  int l = 2 * i + 1;

  int r = 2 * i + 2;

  if (l < n && arr[l] > arr[largest])

    largest = l;

  if (r < n && arr[r] > arr[largest])

    largest = r;

  if (largest != i) {

    swap(arr[i], arr[largest]);

    heapify(arr, n, largest);

  }

}

void heapSort(int arr[], int n) {

  for (int i = n / 2 - 1; i >= 0; i--) {

    heapify(arr, n, i);

  }

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

    swap(arr[0], arr[i]);

    heapify(arr, i, 0);

  }

}

3. 归并排序

归并排序是一种基于分治思想的排序算法,具有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++代码实现,它们都具有良好的时间复杂度和空间复杂度,为算法开发者提供了核心的代码框架和思想。

  
  

评论区

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