21xrx.com
2025-07-14 18:38:35 Monday
登录
文章检索 我的文章 写文章
C++合并排序代码
2023-06-22 04:57:16 深夜i     15     0
C++ 合并排序 代码

合并排序是一种经典的排序算法,它采用分治策略,将一个待排数组不断划分成两个规模较小的子数组,直至每个子数组只含一个或零个元素,然后采用两个已排好序的子数组进行归并,最终得到一个有序的数组。C++语言是一门常用的编程语言,本文将给出C++实现合并排序的代码。

首先,我们需要定义一个函数merge(),这个函数用于将两个有序数组合并成一个有序数组。代码如下:

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++;
  }
}

上述代码的作用就是将一个待排数组的左部分[l, m]和右部分[m+1, r]合并成一个有序数组,其中l,m,r都是数组索引。

接下来,我们定义一个函数mergeSort(),这个函数用于将待排数组不断划分成子数组,直至每个子数组只含一个或零个元素,然后采用merge()函数进行归并。代码如下:

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);
  }
}

上述代码的作用就是将待排数组的左部分[l, m]和右部分[m+1, r]分别进行递归,直到最后只有一个或者零个元素,然后采用merge()函数将两个子数组合并成一个有序数组。

最后,我们编写一个主函数,用来测试上述两个函数的效果。主函数的代码如下:

int main() {
  int arr[] = 6;
  int arr_size = sizeof(arr) / sizeof(arr[0]);
  mergeSort(arr, 0, arr_size - 1);
  cout << "Sorted array: \n";
  for (int i = 0; i < arr_size; i++)
    cout << arr[i] << " ";
  cout << endl;
  return 0;
}

主函数的作用是定义一个待排数组,然后传入mergeSort()函数进行排序,最后输出排序后的有序数组。

综上所述,我们使用C++实现了合并排序算法,并进行了简单的测试,代码简洁可读,是一种常见的排序算法之一。

  
  

评论区