归并排序算法C++
时间: 2025-04-28 17:19:55 浏览: 18
归并排序是一种经典的分治算法,它通过将数组不断分割成较小的部分来进行排序。以下是关于如何使用 C++ 实现归并排序的详细介绍:
### 原理
1. **分解**:将序列分成两个子序列;
2. **递归地对每个子序列进行排序;**
3. **合并**:把已经有序的子序列组合起来。
这个过程会一直持续到所有的元素都被拆分为单个为止,并逐渐构建出完全有序的整体列表。
### 伪代码及解释
```cpp
#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
// 定义左右两部分临时存储空间
int n1 = m - l + 1;
int n2 = r - m;
// 创建临时数组用于存放左半边和右半边的数据
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
// 合并操作
int i = 0; // 初始索引 of 左半部
int j = 0; // 初始索引 of 右半部
int k = l; // 初始索引 of 被合并区域
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
/* 将剩余未处理完的一方直接复制过去 */
while (i < n1){
arr[k++] = L[i++];
}
while(j<n2){
arr[k++]=R[j++];
}
}
/* 主函数负责调用上述辅助函数完成整个归并排序流程 */
void mergesort(int a[], int left, int right){
if(left<right){
int mid=(left+right)/2 ;
mergesort(a,left,mid);
mergesort(a,mid+1,right);
merge(a,left ,mid,right );
}
}
```
以上就是完整的C++版归并排序实现。该算法的时间复杂度稳定为O(n logn),无论最好最坏情况都是如此。而且由于每次都将数据均匀分配给左右两边处理,在实际应用中有较好的性能表现。
#### 示例程序
为了测试我们写的`mergesort()`功能是否正常工作,可以添加下面几行简单的主程序段落:
```cpp
int main(){
const size_t SIZE=7 ;
static int data[SIZE]={54,-6,89,34,78,12,2 };
cout<<"原始数组:"<<endl;
for(auto& d:data )cout<<d<<"\t";
cout<<endl;
mergesort(data ,0,SIZE-1);
cout <<"经过升序排列后的结果为:\n";
for(auto & d :data )
cout <<d<<"\t" ;
return EXIT_SUCCESS ;
}
```
阅读全文
相关推荐














