C语言实现归并排序——2路归并排序

C语言实现归并排序

文章目录

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};