在C中实现合并排序程序中的气泡排序时出错

Question

我正在学习数据结构和算法。该程序在数组中获取一定数量的输入，并使用合并排序对它们进行排序。条件是，每当子数组的大小等于或小于10时，它应该使用冒泡排序对元素进行排序，然后将它们合并在一起。我的问题是如何让程序进行冒泡排序。到目前为止，我还没有发现我的程序中的错误。我每天都在学习。如果有人能帮我找出错误并修复它，我将非常感激。非常感谢，祝您愉快。

下面是代码：

#include<stdio.h>
#include<stdlib.h>
#define arrsize 10
void merge_sort(int, int);
void merge_array(int, int, int, int);
int arr_sort[arrsize];
void bubblesort(int a[],int size);
void main()
{
  int a[50],n,i;
   printf("\nEnter %d Elements for Sorting\n", arrsize);
  for (i = 0; i < arrsize; i++)
    scanf("%d", &arr_sort[i]);

  printf("\nYour Data   :");
  for (i = 0; i < arrsize; i++) {
    printf("\t%d", arr_sort[i]);
  }

  merge_sort(0, arrsize - 1);

  printf("\n\nSorted Data :");
  for (i = 0; i < arrsize; i++) {
    printf("\t%d", arr_sort[i]);
  }

}
void bubblesort(int arr_sort[],int size)
{
  int temp,i,j;
  for(i=0;i<size;i++)
  {
   for(j=0;j<size-1;j++)
   {
    if(arr_sort[j]>arr_sort[j+1])
    {
     temp=arr_sort[j];
     arr_sort[j]=arr_sort[j+1];
     arr_sort[j+1]=temp;
    }
  }
 }
}
void merge_sort(int i, int j) {
  int m;
  if (i < j) {
    m = (i + j) / 2;
       if(m<=5)
    {
        for(i=0;i<=m;i++){
            for(j=i+1;j<=m;j++){
        bubblesort(arr_sort[i],m);
        bubblesort(arr_sort[j],m);}}
        merge_array(i,m,m+1,j);
    }
    else
         merge_sort(i, m);
    merge_sort(m + 1, j);
    merge_array(i, m, m + 1, j);
  }
}

void merge_array(int a, int b, int c, int d) {
  int t[50];
  int i = a, j = c, k = 0;

  while (i <= b && j <= d) {
    if (arr_sort[i] < arr_sort[j])
      t[k++] = arr_sort[i++];
    else
      t[k++] = arr_sort[j++];
  }
  while (i <= b)
    t[k++] = arr_sort[i++];

  while (j <= d)
    t[k++] = arr_sort[j++];

  for (i = a, j = 0; i <= d; i++, j++)
    arr_sort[i] = t[j];
}

Answer 1

在代码中的问题中：

1. 从merge_sort，您应该调用bubble_sort为给定的地板大小，硬固定在您的merge_sort，指定的全局，或作为参数您的函数。前者是最容易实现的。从一开始就调用present.
2. Your
3. bubble_sort是错误的，因为在传递int值( int*应该是int*)时，应该将数组作为参数进行排序，至少长度也应该是参数。这使得函数更加健壮，并且由于指针算法的存在，实现起来比您想象的更容易。

修复这个需要做大手术。

merge_array 更新版

首先做一些merge_array功能的手术。这假设您支持可变长度数组(VLA)。注意，函数接受数组基地址、中间点和整个长度。

void merge_array(int a[], int mid, int len)
{
    // change to int tmp[arrsize], or use dynamic allocation, if your
    // platform doesn't support VLAs
    int tmp[len];

    int i = 0, j = mid, k = 0;
    while (i < mid && j < len)
        tmp[k++] = ((a[i] < a[j]) ? a[i++] : a[j++]);

    while (i < mid)
        tmp[k++] = a[i++];

    for (i = 0; i < k; ++i)
        a[i] = tmp[i];
}

merge_sort 更新版

现在，问题分析中描述的merge_sort函数。和上面的一样，它应该有一个数组基地址和一个长度，但这就是它所需要的。指针算法将允许我们对递归调用进行分区。

void merge_sort(int a[], int len)
{
    if (len < 5)
    {
        // bubblesort short partitions (less than length:5)
        bubble_sort(a, len);
    }
    else
    {
        int mid = len / 2;
        merge_sort(a, mid);
        merge_sort(a + mid, len - mid); // note pointer arithmetic here
        merge_array(a, mid, len);
    }
}

bubble_sort 更新版

这种简单的冒泡排序使用前向交换检测，以便在已经排序的检测早期离开。和前面的函数一样，我们有一些数组的基址和指定的长度。

void bubble_sort(int a[], int size)
{
    int swapped = 1;
    while (swapped && size-- > 0)
    {
        swapped = 0;
        for (int i = 0; i < size; ++i)
        {
            if (a[i + 1] < a[i])
            {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = 1;
            }
        }
    }
}

把所有的东西放在一起，

下面是完整的程序，其中包括一个打印助手，用于将数组转储到控制台，以及一个随机生成器，以避免冗长的键盘输入。提供的main()创建一个随机填充的数组，打印它，排序，然后打印结果。显然，输出将随每次运行而变化，但您希望了解如何调用上述函数。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define arrsize 40

void merge_sort(int a[], int len);
void merge_array(int a[], int mid, int len);
void bubble_sort(int a[], int size);

void merge_array(int a[], int mid, int len)
{
    // change to int tmp[arrsize], or use dynamic allocation, if your
    // platform doesn't support VLAs
    int tmp[len];

    int i = 0, j = mid, k = 0;
    while (i < mid && j < len)
        tmp[k++] = ((a[i] < a[j]) ? a[i++] : a[j++]);

    while (i < mid)
        tmp[k++] = a[i++];

    for (i = 0; i < k; ++i)
        a[i] = tmp[i];
}

void merge_sort(int a[], int len)
{
    if (len < 5)
    {
        // bubblesort short partitions (less than length:5)
        bubble_sort(a, len);
    }
    else
    {
        int mid = len / 2;
        merge_sort(a, mid);
        merge_sort(a + mid, len - mid); // note pointer arithmetic here
        merge_array(a, mid, len);
    }
}

void bubble_sort(int a[], int size)
{
    int swapped = 1;
    while (swapped && size-- > 0)
    {
        swapped = 0;
        for (int i = 0; i < size; ++i)
        {
            if (a[i + 1] < a[i])
            {
                int tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = 1;
            }
        }
    }
}

void print_arr(int const arr[], int len)
{
    while (len-- > 0)
        printf("%d ", *arr++);
    fputc('\n', stdout);
}

int main()
{
    srand((unsigned)time(NULL));

    int arr_sort[arrsize];

    // generate random array
    for (int i = 0; i < arrsize; ++i)
        arr_sort[i] = 1 + rand() % 99;
    print_arr(arr_sort, arrsize);

    // sort the array
    merge_sort(arr_sort, arrsize);
    print_arr(arr_sort, arrsize);
}

样本输出

16 81 73 86 87 66 14 93 19 13 62 32 70 56 29 88 20 21 7 27 70 46 72 42 95 83 24 2 5 43 67 79 8 18 82 39 81 56 56 45
2 5 7 8 13 14 16 18 19 20 21 24 27 29 32 39 42 43 45 46 56 56 56 62 66 67 70 70 72 73 79 81 81 82 83 86 87 88 93 95

希望能帮上忙。