21xrx.com
2024-11-10 00:38:05 Sunday
登录
文章检索 我的文章 写文章
C++合并排序:实现从小到大排序代码
2023-07-04 22:20:16 深夜i     --     --
C++ 合并排序 从小到大排序 代码实现 排序算法

C++合并排序是一种高效的排序算法,其核心思想是分治策略。该算法将待排序数组划分为若干个子数组,将每个子数组递归地进行排序,最后合并子数组得到有序数组。下面是从小到大排序的C++代码实现。


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

  }

}

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

  }

}

该代码中的`merge`函数将两个已经排好序的子数组合并为一个有序数组。`mergeSort`函数则根据待排序数组的左边界`l`和右边界`r`来递归地排序子数组。算法的时间复杂度为$O(n\log n)$,其中$n$是待排序数组的大小。

  
  
下一篇: C++编程软件

评论区

{{item['qq_nickname']}}
()
回复
回复