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

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

2023-06-30 04:30:33 深夜i 10 0

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

归并排序和快速排序是两种常见的排序算法，它们在实际应用中都有着广泛的应用。下面我们解释一下如何使用C/C++编程实现归并快速排序算法。

归并排序算法

归并排序算法通过将一个数组分成两个子数组来工作，然后递归地排序这两个子数组。排序的过程是通过将两个已经排好序的子数组粘在一起来完成的。其中，粘合操作是排序的最核心部分。以下是一个C++实现的归并排序函数：

void mergeSort(vector<int>& arr, int l, int r) {
  if (l < r) {
    int m = (l + r) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }
}
void merge(vector<int>& arr, int l, int m, int r) {
  int i, j, k;
  int n1 = m - l + 1;
  int n2 = r - m;
  vector<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++;
  }
}

快速排序算法

快速排序算法通过选择一个枢纽值并将数组分成两个不同的部分来工作。左边的部分包含所有比枢纽值小的元素，右边的部分包含所有比枢纽值大的元素。然后，递归地对左右两部分进行排序。以下是一个C++实现的快速排序函数：

void quickSort(vector<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 partition(vector<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);
}

总结

本文介绍了如何使用C/C++编程实现归并快速排序算法。归并排序算法通过将一个数组分成两个子数组来工作，然后递归地排序这两个子数组，排序的过程是通过将两个已经排好序的子数组粘在一起来完成的。快速排序算法通过选择一个枢纽值并将数组分成两个不同的部分来工作。左边的部分包含所有比枢纽值小的元素，右边的部分包含所有比枢纽值大的元素。然后，递归地对左右两部分进行排序。希望读者能够掌握这两种常见的排序算法并进行实践应用。

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

下一篇: C++的作用域

评论区

相似文章