归并排序C++例题讲解
时间: 2023-06-09 08:07:59 浏览: 77
好的,让我来为您详细解答归并排序的C语言例题。首先,归并排序是一种采用分治策略排序的算法。下面是一个小例子,以数组为例:
void Merge(int *a,int s,int m,int e){
int n1=m-s+1,n2=e-m;
int L[n1],R[n2],i,j,k;
for(i=0;i<n1;i++)L[i]=a[s+i];
for(i=0;i<n2;i++)R[i]=a[m+1+i];
i=0,j=0,k=s;
while(i<n1&&j<n2){
if(L[i]<=R[j])a[k++]=L[i++];
else a[k++]=R[j++];}
while(i<n1)a[k++]=L[i++];
while(j<n2)a[k++]=R[j++];}
void MergeSort(int *a,int s,int e){
if(s<e){
int m=s+(e-s)/2;//防止溢出
MergeSort(a,s,m);
MergeSort(a,m+1,e);
Merge(a,s,m,e);}}
这个C语言例子中,Merge函数是用来合并两个子数组的,MergeSort函数是归并排序的核心,主要实现了分治和逐级归并的思想。数组被分成多个小数组,然后逐级合并排序,最终得到一个排好序的完整数组。
当然,这个例子仅供参考,实际代码实现可能会因为问题的不同而有所不同。希望对您有所帮助。
相关问题
归并排序c++
好的,以下是C++实现归并排序的代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& nums, int left, int mid, int right) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
}
else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (int p = 0; p < temp.size(); p++) {
nums[left + p] = temp[p];
}
}
void mergeSort(vector<int>& nums, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
}
int main() {
vector<int> nums = { 12, 11, 13, 5, 6, 7 };
mergeSort(nums, 0, nums.size() - 1);
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
```
在这个代码中,我们使用了一个`vector`来存储数组元素,这样可以方便地进行合并操作。`merge()`函数将两个已排序的子数组合并成一个子数组。`mergeSort()`函数使用递归的方式将数组分成两半,直到每个子数组的长度为1,然后调用`merge()`函数将它们合并成一个已排序的数组。最后,`main()`函数初始化一个`vector`并调用`mergeSort()`函数对其进行排序。
快速排序和归并排序c++实现
快速排序和归并排序都是常见的排序算法,下面分别给你介绍它们的C++实现。
1. 快速排序(Quick Sort):
快速排序是一种基于分治思想的排序算法,它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分小,然后再按此方法对这两部分数据分别进行快速排序,整个过程递归进行,最终得到有序的结果。
以下是快速排序的C++实现代码:
```cpp
#include <iostream>
using namespace std;
// 交换两个元素的值
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 分割函数,将数组划分为左右两部分
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // 以第一个元素作为基准
int i = low, j = high;
while (i < j) {
// 从右向左找到第一个小于基准的元素
while (i < j && arr[j] >= pivot)
j--;
if (i < j)
swap(arr[i++], arr[j]);
// 从左向右找到第一个大于基准的元素
while (i < j && arr[i] <= pivot)
i++;
if (i < j)
swap(arr[i], arr[j--]);
}
// 将基准元素放到正确的位置上
arr[i] = pivot;
return i;
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotPos = partition(arr, low, high); // 划分数组
quickSort(arr, low, pivotPos - 1); // 对左子数组进行快速排序
quickSort(arr, pivotPos + 1, high); // 对右子数组进行快速排序
}
}
int main() {
int arr[] = {5, 2, 9, 3, 7, 6, 1, 8, 4};
int n = sizeof(arr) / sizeof(arr);
quickSort(arr, 0, n - 1);
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```