21xrx.com
2024-11-10 00:53:03 Sunday
登录
文章检索 我的文章 写文章
C++合并排序代码实现
2023-06-28 07:01:32 深夜i     --     --
C++ 合并排序 代码实现

合并排序是一种经典的排序算法,它采用了分治策略来使得排序的效率更高。C++是一种广泛使用的编程语言,因其效率高、语法简洁、功能强大而备受开发者青睐,下面我们来看一下如何在C++中实现合并排序。

合并排序主要有两个步骤,分别是分割和合并。在分割阶段,我们将待排序数组分成两个子数组,然后再对这两个子数组进行递归操作,直到子数组中只剩下一个元素。在合并阶段,我们将两个已排好序的子数组合并成一个排序好的数组。接下来是C++合并排序代码实现:


void merge(int arr[], int left[], int lenL, int right[], int lenR) {

  int i = 0, j = 0, k = 0;

  while (i < lenL && j < lenR) {

    if (left[i] <= right[j]) {

      arr[k++] = left[i++];

    } else {

      arr[k++] = right[j++];

    }

  }

  while (i < lenL) {

    arr[k++] = left[i++];

  }

  while(j < lenR) {

    arr[k++] = right[j++];

  }

}

void mergeSort(int arr[], int n) {

  if (n < 2)

    return;

  

  int mid = n / 2;

  int* left = new int[mid];

  int* right = new int[n - mid];

  for (int i = 0; i < mid; ++i) {

    left[i] = arr[i];

  }

  for (int i = mid; i < n; ++i) {

    right[i - mid] = arr[i];

  }

  mergeSort(left, mid);

  mergeSort(right, n - mid);

  merge(arr, left, mid, right, n - mid);

  delete[] left;

  delete[] right;

}

以上代码中,merge()函数用于合并两个已排好序的子数组,使用了三个指针来标记左右两个子数组和合并后的数组。mergeSort()函数则用于递归分割数组,并最终调用merge()函数完成合并。

在main()函数中,我们可以使用以下代码来调用mergeSort()函数进行排序:


int main() {

  int arr[] = 12;

  int n = sizeof(arr) / sizeof(arr[0]);

  mergeSort(arr, n);

  for (int i = 0; i < n; ++i) {

    cout << arr[i] << " ";

  }

  cout << endl;

  return 0;

}

以上代码将数组 13进行排序并输出排序后的结果。

通过以上代码,我们可以看出,C++合并排序代码实现简单、易懂、具有极高的实用价值,为开发者提供了一种可靠的排序方法,可以应用于各种场合,如排序算法竞赛、数据处理等方面。

  
  

评论区

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