21xrx.com
2025-03-21 19:25:17 Friday
文章检索 我的文章 写文章
C++归并排序代码实现
2023-06-30 20:20:37 深夜i     --     --
C++ 归并排序 代码实现

C++归并排序是一种基于分治策略的排序算法,其核心思想是将一个大问题拆分成小的子问题进行求解,然后将子问题的解合并起来得到大问题的解。这种算法的时间复杂度为O(nlogn),具有稳定性,适用于大规模数据的排序。

下面给出C++归并排序的代码实现:

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

在以上代码中,`merge()`函数实现的是归并的过程,它将两个有序的子数组合并成一个有序的数组。`mergeSort()`函数则是整个归并排序的核心算法,它将原始数组递归地拆分成较小的子数组进行排序,然后再将子数组合并得到有序的数组。

使用C++归并排序可以实现非常高效的排序,并且代码实现也较为简单,值得程序员们深入学习和掌握。

  
  

评论区