简单易学的合并排序算法c++代码 |21xrx.com

简单易学的合并排序算法c++代码

2023-07-09 11:57:10 深夜i -- --

合并排序算法 C++ 简单易学

合并排序算法是计算机科学领域中一种经典的算法，也是一种最常见的排序算法之一。该算法使用分治策略，即将待排序的数列递归地拆分成两个子序列，直到无法再拆分为止，再将两个子序列合并为一个更大的有序序列。这种算法的时间复杂度为O(nlogn)，而且还可以进行并行处理。

C++是一门流行的编程语言，它也实现了合并排序算法，下面我们来介绍一下在C++语言中如何简单易学地实现合并排序算法。

首先，我们需要定义一个函数来实现合并排序算法，该函数接受三个参数，即待排序的数列、数列的起始位置和结束位置。代码如下：

void mergeSort(int arr[], int start, int end) {

if (start < end) {

int mid = (start + end) / 2;

mergeSort(arr, start, mid);

mergeSort(arr, mid + 1, end);

merge(arr, start, mid, end);

}

其中，merge()函数是用来将两个已经排好序的子序列合并成一个更大的有序序列。代码如下：

void merge(int arr[], int start, int mid, int end) {

int leftSize = mid - start + 1;

int rightSize = end - mid;

int leftArr[leftSize], rightArr[rightSize];

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

leftArr[i] = arr[start + i];

}

for (int j = 0; j < rightSize; j++) {

rightArr[j] = arr[mid + 1 + j];

}

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

while (i < leftSize && j < rightSize) {

if (leftArr[i] <= rightArr[j]) {

arr[k] = leftArr[i];

i++;

} else {

arr[k] = rightArr[j];

j++;

}

k++;

}

while (i < leftSize) {

arr[k] = leftArr[i];

i++;

k++;

}

while (j < rightSize) {

arr[k] = rightArr[j];

j++;

k++;

}

注意，这里我们利用C++语言的特性，使用了数组的动态定义，需要在编码时注意数组的大小问题。

最后，我们只要在主函数中调用mergeSort()函数就可以实现合并排序。代码如下：

int main() {

int arr[] = 2;

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

mergeSort(arr, 0, n - 1);

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

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

}

cout << endl;

return 0;

}

通过以上的代码实现，我们可以轻松地使用C++编写出一个简单易学的合并排序算法。

上一篇: idea打包java可执行jar包

下一篇: C++三次方根函数

评论区

()

相似文章