为什么递减阶段的冒泡排序不起作用？

Question

我是 C 的初学者，我正在尝试创建一个程序，在该程序中，我借助冒泡排序算法根据单词的 ASCII 总和对处于递减阶段的单词进行排序（例如，ASCII 总和最大的单词将排在最前面，最后是单词具有最小的 ASCII 和 - 这就是为什么我使用 strcmp 来比较单词）但是当我打印这些词时，我的冒泡排序算法不起作用出了什么问题？

我的代码：

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

void swap(char **xp, char **yp)
{
    char **temp; 
    temp= xp;
    *xp = *yp;
    yp = temp;
}
 
void bubbleSort(char **arr, int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)                
       for (j = 0; j < n-i-1; j++)
           if (strcmp(arr[j] , arr[j+1])>=0)
              swap(&arr[j], &arr[j+1]);
}

int main ()
{
    char *p[5]={"Manolas","tikinio","youssef el arabi"};
    
    bubbleSort(p,3);
    
    char **p1;
    p1=p;
    for(p1=p ; *p1 ; p1++)
    {
        printf("\nthe words are : %s", *p1);
    }
    
    return 0;
}

Answer 1

strcmp(arr[j], arr[j+1]) >= 0 始终是 false，因为输入字符串相对于 strcmp() 的顺序已经正确，而这并不像您想象的那样有效。所以 swap() 永远不会被调用。

swap() 在任何情况下都被错误定义（并且在我尝试它时导致段错误 - 令人困惑的是仅当 printf() 在排序完成后被调用时）：

void swap(char **xp, char **yp)
{
    char* temp = *xp;
    *xp = *yp;
    *yp = temp;
}

您的 `main() 例程被不必要地混淆了，建议：

    char* p[] = {"Manolas","tikinio","youssef el arabi"} ;
    const int count = sizeof(p) / sizeof(*p) ;
    
    bubbleSort( p, count );
    
    printf( "The words are:\n" ) ;
    for( int i = 0; i < count; i++ )
    {
        printf( "%s\n", p[i] ) ; 
    }

strcmp() 不满足您指定的排序条件。 strcmp() returns:

<0  the first character that does not match has a lower value in ptr1 than in ptr2
0   the contents of both strings are equal
>0  the first character that does not match has a greater value in ptr1 than in ptr2

您需要一个不同的比较函数：

int acsiiSumCmp( const char* a, const char* b )
{
    unsigned sum_a = 0 ;
    unsigned sum_b = 0 ;
    for( int i = 0; a[i] != 0; i++ ) sum_a += (unsigned char)a[i] ;
    for( int i = 0; b[i] != 0; i++ ) sum_b += (unsigned char)b[i] ;
    
    return sum_a - sum_b ;
}

其中 returns >1 当 a 的总和大于 b 时，为了实现您指定的排序，您需要：

if( acsiiSumCmp( arr[j] , arr[j + 1] ) < 0 )
{
    swap( &arr[j], &arr[j + 1] ) ;
}

请注意，当项相等时不需要交换，所以不是 >= 或 <=，而是 < 或 >，具体取决于所需顺序。

终于有点“const-correctness”在这里不会出错，如下：

void swap( const char**xp, const char** yp )
           ^^^^^           ^^^^^

void bubbleSort( const char** arr, int n)
                 ^^^^^

const char* p[] = { "ZZ", "Manolas","tikinio","youssef el arabi", "AA" } ;
^^^^^

为什么递减阶段的冒泡排序不起作用？

why bubblesort with decreasing phase does not work?

c

bubble-sort