目录
- 归并排序（Merge Sort）的C++实现
- 源代码
- 解释
- 结果
- 小结：
归并排序（Merge Sort）的C++实现
归并排序是一种分而治之的算法，它将数组分成两半，对每半部分递归地应用归并排序，然后将排序好的两半合并成一个有序的数组。以下是一个归并排序的C++实现。
源代码
#include<iostream> using namespace std; // 辅助数组，用于合并两个有序数组
int b[10]; // 合并两个有序数组段到辅助数组b[]
void Merge(int a[], int left, int i, int right){ int l_p = left; // 左数组的起始位置 int r_p = i + 1; // 右数组的起始位置 int b_p = 0; // 辅助数组b的当前位置 // 合并两个有序数组段到b[] while (l_p <= i && r_p <= right){ if (a[l_p] <= a[r_p]){ b[b_p++] = a[l_p++]; } else{ b[b_p++] = a[r_p++]; } } // 将左侧剩余的元素复制到b[] while (l_p <= i){ b[b_p++] = a[l_p++]; } // 将右侧剩余的元素复制到b[] while (r_p <= right){ b[b_p++] = a[r_p++]; }
} // 将排序好的数组段从辅助数组b[]复制回原数组a[]
void Copy(int a[], int left, int right) { for (int i = left; i <= right; i++) { a[i] = b[i - left]; }
} // 归并排序函数
void MergeSort(int a[], int left, int right){ if (left >= right) return; // 如果只有一个元素，则无需排序 else{ int i = (left + right) / 2; // 递归地对左半部分进行归并排序 MergeSort(a, left, i); // 递归地对右半部分进行归并排序 MergeSort(a, i + 1, right); // 合并两个有序的数组段 Merge(a, left, i, right); // 将排序好的数组段复制回原数组a[] Copy(a, left, right); }
} // 主函数
int main() { int a[10] = {5, 3, 7, 8, 4, 2, 10, 9, 1, 6}; MergeSort(a, 0, 9); // 输出排序后的数组 for (int i = 0; i <= 9; i++){ cout << a[i] << ' '; } cout << endl; return 0;
}
解释
Merge 函数：该函数负责将两个已排序的数组段合并成一个有序的数组段，并存储在辅助数组 b 中。合并完成后，通过 Copy 函数将结果复制回原数组 a。
Copy 函数：用于将辅助数组 b 中的数据复制回原数组 a 的指定位置。
MergeSort 函数：这是归并排序的核心函数，采用递归的方式，将数组分成越来越小的部分，直到每个部分只有一个元素（无需排序），然后开始合并过程，直至整个数组排序完成。
main 函数：定义了一个待排序的数组 a，并调用 MergeSort 函数对其进行排序，最后输出排序后的结果。
这个实现展示了归并排序的基本思想和步骤，是理解和实现归并排序的一个很好的例子。
结果
小结：
关注我给大家分享更多有趣的知识，以下是个人公众号，提供 ||竞赛资料|| ||课程资料||
添加我的公众号即可：
