21xrx.com
2024-11-21 22:57:08 Thursday
登录
文章检索 我的文章 写文章
C++实现归并排序
2023-07-13 00:39:47 深夜i     --     --
C++ 归并排序 实现

归并排序是一种基于分治思想的经典排序算法,其时间复杂度为 O(nlogn),在面对大规模数据排序时具有较好的效率。C++语言作为一门高效的编程语言,可以实现归并排序算法并且具有良好的性能。

归并排序的思想是将一个大问题拆分为多个小问题,分别解决后再将结果合并起来。具体实现过程如下:

1. 将待排序序列拆分为两个子序列,每个子序列再进行递归拆分,直到拆分后的子序列只包含一个元素。

2. 合并两个排好序的子序列,使合并后的序列仍然有序。

C++实现归并排序的关键在于合并两个排好序的子序列,这是一个典型的归并操作。合并时需要申请额外的内存空间,将两个子序列中的元素按照大小关系合并到新的空间中,并将结果复制回原来的序列中。C++中可以使用vector或者数组实现归并操作。

下面是C++的代码实现:


void merge(vector<int>& nums, int left, int mid, int right) {

  vector<int> tmp(right - left + 1); // 临时数组用来存储排序结果

  int i = left, j = mid + 1, k = 0;

  while (i <= mid && j <= right) {  // 将两个有序子序列合并

    if (nums[i] < nums[j]) {

      tmp[k++] = nums[i++];

    } else {

      tmp[k++] = nums[j++];

    }

  }

  while (i <= mid) { // 如果左边子序列还有元素,将其全部复制到临时数组中

    tmp[k++] = nums[i++];

  }

  while (j <= right) {  // 如果右边子序列还有元素,将其全部复制到临时数组中

    tmp[k++] = nums[j++];

  }

  for (int i = left, k = 0; i <= right; i++, k++) { // 将排好序的临时数组复制回原序列中

    nums[i] = tmp[k];

  }

}

void mergeSort(vector<int>& nums, int left, int right) {

  if (left >= right) return;

  int mid = (left + right) / 2;  // 分治,拆分子序列

  mergeSort(nums, left, mid);

  mergeSort(nums, mid + 1, right);

  merge(nums, left, mid, right);  // 归并两个有序子序列

}

这个归并排序的实现采用递归方法,先将序列分成左右两个子序列,然后递归排序左右两个子序列,最后再将排好序的左右子序列合并成一个完整的有序序列。

总的来说,C++实现归并排序算法需要注意合并两个子序列的操作,需要使用额外的内存空间,在合并完成后再将结果复制回原序列中。归并排序算法在C++语言中具有较好的性能,比如在处理大规模数据时效率高,应用广泛。

  
  

评论区

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