21xrx.com
2024-12-22 22:08:36 Sunday
登录
文章检索 我的文章 写文章
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++归并排序可以实现非常高效的排序,并且代码实现也较为简单,值得程序员们深入学习和掌握。

  
  

评论区

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