C/C++编程实现归并快速排序算法 |21xrx.com

C/C++编程实现归并快速排序算法

2023-07-10 07:06:14 深夜i -- --

C/C++编程归并排序快速排序算法

归并排序和快速排序是两种常用的排序算法，在C/C++编程中，我们可以通过实现这两个算法来提高程序的效率和可靠性。

1. 归并排序

归并排序是一种分治算法，其基本思想是将待排序数组分成两个子数组，再将这两个子数组分别排序，最后将排好序的子数组合并成一个有序数组。其时间复杂度为O(nlogn)，属于稳定排序算法。

以下是C++实现的归并排序代码：


#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
  int n1 = m - l + 1;
  int n2 = r - m;
  int L[n1];
  int R[n2];
  for (int i = 0; i < n1; i++) {
    L[i] = arr[l + i];
  }
  for (int j = 0; j < n2; j++) {
    R[j] = arr[m + 1 + j];
  }
  int i = 0;
  int j = 0;
  int 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);
  }
}
int main() {
  int arr[] = 12;
  int arr_size = sizeof(arr) / sizeof(arr[0]);
  mergeSort(arr, 0, arr_size - 1);
  cout << "Sorted array: ";
  for (int i = 0; i < arr_size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

2. 快速排序

快速排序也是一种分治算法，其基本思想是选择一个基准元素，将数组中小于基准元素的放在其左边，大于基准元素的放在其右边，然后对基准左右两部分分别进行递归排序。其时间复杂度为O(nlogn)，平均情况下效率较高。

以下是C++实现的快速排序代码：


#include <iostream>
using namespace std;
void swap(int* a, int* b) {
  int t = *a;
  *a = *b;
  *b = t;
}
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);
  }
}
int main() {
  int arr[] = 10;
  int arr_size = sizeof(arr) / sizeof(arr[0]);
  quickSort(arr, 0, arr_size - 1);
  cout << "Sorted array: ";
  for (int i = 0; i < arr_size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

综上所述，通过对归并排序和快速排序的代码实现可以提高我们对排序算法的理解和掌握，也有助于我们编写高质量的程序。

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

下一篇: C++和Python是否有重叠部分？

评论区

()

相似文章