算法设计与分析（合并排序

目录

• 归并排序（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 函数对其进行排序，最后输出排序后的结果。

这个实现展示了归并排序的基本思想和步骤，是理解和实现归并排序的一个很好的例子。

结果