C语言实现归并排序
文章目录
C语言实现归并排序2路归并排序算法1.定义动态数组2.初始化动态数组3.归并操作4.归并排序算法实现项目完整代码运行效果图2路归并排序算法
1.定义动态数组
//定义一个动态数组
typedef struct {int *data;
} DSqList;
2.初始化动态数组
//动态数组初始化
void InitDSqList(DSqList &L, int len) {//根据数组A的长度动态分配辅助数组B的空间L.data = (int *) malloc(len * sizeof(int));
}
3.归并操作
//归并操作——表A中的两个子表A[low...mid]与A[mid+1...high]各自有序,将它们合并为一个有序表
void Merge(int A[], int low, int mid, int high) {int i, j, k;for (int p = low; p <= high; ++p) { //将数组A中的元素对应复制到辅助数组B中B.data[p] = A[p];}for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {if (B.data[i] <= B.data[j]) //比较辅助数组B左右两段子表中的元素,并将较小的值复制到A中相应位置A[k] = B.data[i++];elseA[k] = B.data[j++];}while (i <= mid) //如果左子表未检查完,将剩余元素依次复制到A中A[k++] = B.data[i++];while (j <= high) //如果右子表未检查完,将剩余元素依次复制到AA[k++] = B.data[j++];
}
4.归并排序算法实现
//归并排序
void MergeSort(int A[], int low, int high) {if (low < high) {int mid = (low + high) / 2; //从中间进行划分,分成两个子表MergeSort(A, low, mid); //递归的对左边的子表进行归并排序MergeSort(A, mid + 1, high); //递归的对右边的子表进行归并排序Merge(A, low, mid, high); //将左右子表进行归并}
}
项目完整代码
//归并排序(稳定,空间效率为O(n),时间效率为O(nlogn))
#include <stdio.h>
#include <stdlib.h>//定义一个动态数组
typedef struct {int *data;
} DSqList;//声明一个全局动态辅助数组B
DSqList B;//动态数组初始化
void InitDSqList(DSqList &L, int len) {//根据数组A的长度动态分配辅助数组B的空间L.data = (int *) malloc(len * sizeof(int));
}//归并操作——表A中的两个子表A[low...mid]与A[mid+1...high]各自有序,将它们合并为一个有序表
void Merge(int A[], int low, int mid, int high) {int i, j, k;for (int p = low; p <= high; ++p) { //将数组A中的元素对应复制到辅助数组B中B.data[p] = A[p];}for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {if (B.data[i] <= B.data[j]) //比较辅助数组B左右两段子表中的元素,并将较小的值复制到A中相应位置A[k] = B.data[i++];elseA[k] = B.data[j++];}while (i <= mid) //如果左子表未检查完,将剩余元素依次复制到A中A[k++] = B.data[i++];while (j <= high) //如果右子表未检查完,将剩余元素依次复制到AA[k++] = B.data[j++];
}//归并排序
void MergeSort(int A[], int low, int high) {if (low < high) {int mid = (low + high) / 2; //从中间进行划分,分成两个子表MergeSort(A, low, mid); //递归的对左边的子表进行归并排序MergeSort(A, mid + 1, high); //递归的对右边的子表进行归并排序Merge(A, low, mid, high); //将左右子表进行归并}
}int main() {int A[] = {49, 38, 65, 97, 76, 13, 27};int len = sizeof(A) / sizeof(int);//初始化辅助数组BInitDSqList(B, len);//归并排序MergeSort(A, 0, len - 1);//输出排序后的结果printf("归并排序后的结果为:");for (int i = 0; i < len; ++i) {printf("%d ", A[i]);}return 0;
}
运行效果图
int A[] = {49, 38, 65, 97, 76, 13, 27};
更多推荐
语言
发布评论