用C语言根据void MergeSort(int* a, int begin, int end, int* temp)写出归并排序函数

void MergeSort(int* a, int begin, int end, int* temp) {
if (begin >= end) return;

int mid = (begin + end) / 2;
MergeSort(a, begin, mid, temp);
MergeSort(a, mid + 1, end, temp);

int i = begin, j = mid + 1, k = 0;
while (i <= mid && j <= end) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= mid) temp[k++] = a[i++];
while (j <= end) temp[k++] = a[j++];

for (i = 0; i < k; i++) {
a[begin + i] = temp[i];
}
}

相关问题

我有一个c++函数,参数是int* NumList ,请使用Merge Sort算法排序

好的，以下是基于 Merge Sort 算法对 int* NumList 进行排序的 C 函数代码：

void Merge(int* NumList, int iStart, int iMid, int iEnd)
{
    int i, j, k;
    int* TempList = (int*)malloc((iEnd-iStart+1) * sizeof(int));
    i = iStart, j = iMid+1, k = 0;
    while (i <= iMid && j <= iEnd) {
        if (NumList[i] <= NumList[j]) {
            TempList[k++] = NumList[i++];
        } else {
            TempList[k++] = NumList[j++];
        }
    }
    while (i <= iMid) {
        TempList[k++] = NumList[i++];
    }
    while (j <= iEnd) {
        TempList[k++] = NumList[j++];
    }
    for (i = iStart, k = 0; i <= iEnd; ++i, ++k) {
        NumList[i] = TempList[k];
    }
    free(TempList);
}

void MergeSort(int* NumList, int iStart, int iEnd)
{
    if (iStart < iEnd) {
        int iMid = (iStart+iEnd) / 2;
        MergeSort(NumList, iStart, iMid);
        MergeSort(NumList, iMid+1, iEnd);
        Merge(NumList, iStart, iMid, iEnd);
    }
}

void Sort(int* NumList)
{
    int iLen = sizeof(NumList)/sizeof(int);
    MergeSort(NumList, 0, iLen-1);
}

你可以将需要排序的 int 数组传递给 Sort 函数，它将按照升序排列这个数组，具体用法可以参考如下示例：

int main()
{
    int i;
    int NumList[] = {5, 3, 4, 2, 1};
    Sort(NumList);
    for (i = 0; i < sizeof(NumList)/sizeof(int); ++i) {
        printf("%d ", NumList[i]);
    }
    printf("\n");
    return 0;
}

以下代码采用分而治之算法实现归并排序。请补充函数mergesort（）的代码。提示：mergesort（）函数可用递归实现，其中参数n在递归调用中不需要变化。 函数接口定义： void mergesort(int a[],int n,int left,int right)；

void merge(int a[], int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    int* tmp = new int[right - left + 1];
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        }
        else {
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = a[i++];
    }
    while (j <= right) {
        tmp[k++] = a[j++];
    }
    for (int x = 0; x < k; x++) {
        a[left + x] = tmp[x];
    }
    delete[] tmp;
}

void mergesort(int a[], int n, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergesort(a, n, left, mid);
        mergesort(a, n, mid + 1, right);
        merge(a, left, mid, right);
    }
}