归并排序c++代码（归并排序c++代码加讲解）

【归并排序C代码】

简介：

归并排序（Merge Sort）是一种经典的排序算法，采用分治思想，将待排序的序列分为若干个子序列，每个子序列都是有序的，然后再将这些有序的子序列合并为一个有序的序列。归并排序的核心操作是将两个有序的子序列合并为一个有序的序列。

多级标题：

一、归并排序的基本原理

二、归并排序的步骤

1.划分子序列

2.递归分解子序列

3.合并子序列

三、归并排序的C代码实现

1.归并函数（merge）

2.归并排序函数（mergeSort）

3.主函数（main）

一、归并排序的基本原理

归并排序采用分治思想，将待排序的序列分为若干个子序列，然后将这些子序列两两合并，直到合并成一个有序的序列。核心操作是合并两个有序的子序列，这可以通过一个辅助数组来实现。

二、归并排序的步骤

1. 划分子序列：将待排序的序列划分成一个个子序列，直到每个子序列只有一个元素。

2. 递归分解子序列：对每个子序列进行递归，继续将每个子序列划分成更小的子序列，直到所有子序列都只有一个元素。

3. 合并子序列：依次将相邻的子序列进行合并，直到最终只有一个有序的序列。

三、归并排序的C代码实现

1. 归并函数（merge）：用于将两个有序的子序列合并为一个有序的序列。

```c

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

int i, j, k;

int n1 = mid - left + 1;

int n2 = right - mid;

int L[n1], R[n2];

for (i = 0; i < n1; i++)

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

for (j = 0; j < n2; j++)

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

i = 0;

j = 0;

k = left;

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

}

}

```

2. 归并排序函数（mergeSort）：用于递归地将子序列进行划分和合并。

```c

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

}

}

```

3. 主函数（main）：用于测试归并排序函数。

```c

#include

int main() {

int arr[] = { 12, 11, 13, 5, 6, 7 };

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

printf("Original array: \n");

for (int i = 0; i < arr_size; i++)

printf("%d ", arr[i]);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array: \n");

for (int i = 0; i < arr_size; i++)

printf("%d ", arr[i]);

return 0;

}

```

以上是归并排序的C代码实现，通过调用归并排序函数（mergeSort），可以对待排序的序列进行排序，并输出排序后的结果。

总结：

归并排序是一种高效的排序算法，采用分治思想，通过递归将序列不断划分和合并，最终得到一个有序的序列。归并排序的C代码实现简洁明了，可以对任意大小的序列进行排序。归并排序的时间复杂度为O(nlogn)，是一种稳定的排序算法。