C++合并排序代码实现 |21xrx.com

C++合并排序代码实现

2023-06-28 07:01:32 深夜i 24 0

C++ 合并排序代码实现

合并排序是一种经典的排序算法，它采用了分治策略来使得排序的效率更高。C++是一种广泛使用的编程语言，因其效率高、语法简洁、功能强大而备受开发者青睐，下面我们来看一下如何在C++中实现合并排序。

合并排序主要有两个步骤，分别是分割和合并。在分割阶段，我们将待排序数组分成两个子数组，然后再对这两个子数组进行递归操作，直到子数组中只剩下一个元素。在合并阶段，我们将两个已排好序的子数组合并成一个排序好的数组。接下来是C++合并排序代码实现：

void merge(int arr[], int left[], int lenL, int right[], int lenR) {
  int i = 0, j = 0, k = 0;
  while (i < lenL && j < lenR) {
    if (left[i] <= right[j]) {
      arr[k++] = left[i++];
    } else {
      arr[k++] = right[j++];
    }
  }
  while (i < lenL) {
    arr[k++] = left[i++];
  }
  while(j < lenR) {
    arr[k++] = right[j++];
  }
}
void mergeSort(int arr[], int n) {
  if (n < 2)
    return;
  
  int mid = n / 2;
  int* left = new int[mid];
  int* right = new int[n - mid];
  for (int i = 0; i < mid; ++i) {
    left[i] = arr[i];
  }
  for (int i = mid; i < n; ++i) {
    right[i - mid] = arr[i];
  }
  mergeSort(left, mid);
  mergeSort(right, n - mid);
  merge(arr, left, mid, right, n - mid);
  delete[] left;
  delete[] right;
}

以上代码中，merge()函数用于合并两个已排好序的子数组，使用了三个指针来标记左右两个子数组和合并后的数组。mergeSort()函数则用于递归分割数组，并最终调用merge()函数完成合并。

在main()函数中，我们可以使用以下代码来调用mergeSort()函数进行排序：

int main() {
  int arr[] = 12;
  int n = sizeof(arr) / sizeof(arr[0]);
  mergeSort(arr, n);
  for (int i = 0; i < n; ++i) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

以上代码将数组 13进行排序并输出排序后的结果。

通过以上代码，我们可以看出，C++合并排序代码实现简单、易懂、具有极高的实用价值，为开发者提供了一种可靠的排序方法，可以应用于各种场合，如排序算法竞赛、数据处理等方面。

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

下一篇: C++ 程序解决放苹果问题

评论区

相似文章