c - C 中的合并排序不起作用

标签 c arrays sorting mergesort

我的合并排序实现不起作用,我不明白为什么。

方法如下:

    void merge_sort(int A[], int i, int j)
    {
       if(i<j)
       {
           int n = j-i+1;
           int k = n/2;

           merge_sort(A, i, i+k-1);
           merge_sort(A, i+k, j);
           merge(A, i, i+k, j);
       }
    }

这就是合并方法:

 void merge(int A[], int a, int b, int j)
{
    int* T = malloc(sizeof(int)*DIM);
    int c=0;
    int h=a;

    while(a<b && b<=j)
    {
    if(A[a] > A[b])
        T[c++] = A[a++];
    else
        T[c++] = A[b++];
    }
    while(a<b) T[c++] = A[a++];
    while(b<=j) T[c++] = A[b++];

    c=0;
    while(h<=j)
    A[h++] = T[c++];


}

这是我调用 merge_sort 的方法:

merge_sort(A, 0, DIM-1);

其中 DIM 是数组长度减一。

这就是输出:

5 2 4 6 8 9 7 1 3 10 
0 9
0 4
0 1
2 4
3 4
5 9
5 6
7 9
8 9
10 9 8 7 10 6 5 4 3 2 

前半部分是完美有序的,后半部分也是减一。 我不知道问题出在哪里。

最佳答案

您的代码有 2 个问题。

  1. 计算边界不正确。
  2. 您的 while 条件不正确。

此处的 while 不正确:

while(a<b && b<=j)
{
if(A[a] > A[b])
    T[c++] = A[a++];
else
    T[c++] = A[b++];
}

在此循环中,您在处于您的条件时增加 b,这将影响您的循环。

这是我更正的代码(i 包含在数组中,而 j 被排除):

void merge_sort(int A[], int i, int j)
{
   if(j-i>=2) // since j is excluded, this condition means that we have more than 1 member.
   {
       int k = (j+i)/2;

       merge_sort(A, i, k);
       merge_sort(A, k, j);
       merge(A, i, k, j);
   }
}

void merge(int A[], int a, int b, int j)
{
    int* T = malloc(sizeof(int)*DIM);
    int c=0;
    int h=a;
    int m = b;

    while(a<b && m<j) // b and j are excluded
    {
    if(A[a] > A[m])
        T[c++] = A[a++];
    else
        T[c++] = A[m++];
    }
    while(a<b) T[c++] = A[a++];
    while(m<j) T[c++] = A[m++];

    c=0;
    while(h<j)
    A[h++] = T[c++];
}

并运行它:

merge_sort(A, 0, DIM);

关于c - C 中的合并排序不起作用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50569129/

相关文章:

javascript - 根据输出对 HTML 数组进行排序

c - 为什么c中只使用下划线来命名变量?

c - 传递 strcpy 的参数 2 使指针来自整数而不进行强制转换

c++ - 字谜检测方法c++。将字符串转换为 ascii 值时出现问题

javascript - 更好的做法 : Always get a range of 6 Items out of an array

php - array_key_exists 不工作

c - 为什么头文件中的全局变量会导致链接错误?

c - Makefile 条件语句不起作用

c - 在c中使用qsort进行排序

javascript - 根据字符串中的数字对数组中的字符串进行排序