按升序排列数组元素的函数

Question

我尝试创建一个按升序排列数组元素的函数。但结果并不好。我想我忘记了一件事...谢谢你的帮助。

#include <stdio.h>

void ft_sort_int_tab(int *tab, int size) {
    int i;
    int j;
    int temp;
    size -= 1;

    i = 0;
    while (i < size) {
        if (tab[i] > tab[i + 1]) {
            temp = tab[i];
            tab[i] = tab[i + 1];
            tab[i + 1] = temp;
        }
        i++;
    }
}

int main(void) {
    int tab[9] = {9, 5, 2, 3, 8, 4, 16, 20, 24};
    ft_sort_int_tab(tab, 9);
    for (int i = 0; i < 9; i++) {
        printf("%d ", tab[i]);
    }
}

结果：5 2 3 8 4 9 16 20 24

Answer 1

如果需要，您的代码会交换这两个元素，然后移动到数组中的下一个位置。在您的示例的开头，交换了 9 和 5，因此 5 位于第一个位置，但 5 永远不会与其他元素进行比较。

有很多排序算法，您应该阅读它们。您的代码看起来最相似的一种称为“冒泡排序”。要到达那里，请修改您的代码，使其多次遍历数组，直到数组完全排序。例如，如果你进行第二次传递，5 和 2 将被交换，你会更接近排序结果。

冒泡排序不是最快的排序方法，但它很容易理解。其他方法包括快速排序、归并排序和堆排序。维基百科可以解释其中的每一个，如果您需要更好的性能，它们值得研究。

Answer 2

您已经编写了冒泡排序的内部扫描循环，但您显然错过了算法的要点，因为这只是算法的一半。

如果相邻元素彼此之间的顺序不正确（而不是 整个序列），则每次通过冒泡排序都会交换相邻元素。一次通过完成后，您可以保证极值（最大或最小，取决于您的比较器选择）已在扫描分区的末尾找到它的位置。届时，不应再次访问它。下一次扫描运行直到，但不包括该元素。每次扫描都会让越来越多的元素更接近它们的正确位置，并且至少有一个（该分区长度的最后一个）在其永久位置中）。作为优化，您可以跟踪当前扫描是否每次都实际交换了任何值。

可选地，如果扫描完成且没有交换，您可以完全弹出；序列已排序。这个属性是 bubblesort 唯一可取之处。在最好的情况下，当输入序列在使用交换检测时已经排序时，它是 O(n)。但它在一般情况下也是 O(n^2) 和最坏的情况，这使得它通常是一个糟糕的排序选择。

不管

#include <stdio.h>

void ft_sort_int_tab(int *tab, int size) 
{
    while (size-- > 0) // note descending ceiling
    {
        int swapped = 0;

        for (int i=0; i<size; ++i) // partition sweep 
        {
            if (tab[i] > tab[i + 1]) 
            {
                int temp = tab[i];
                tab[i] = tab[i + 1];
                tab[i + 1] = temp;
                swapped = 1;
            }
        }

        if (!swapped) // early exit on no-swap sweep
            break;
    }
}

int main(void) 
{
    int tab[9] = {9, 5, 2, 3, 8, 4, 16, 20, 24};
    ft_sort_int_tab(tab, 9);
    
    for (int i = 0; i < 9; i++) 
        printf("%d ", tab[i]);
    fputc('\n', stdout);
}

输出

2 3 4 5 8 9 16 20 24

Answer 3

您似乎正在尝试实施冒泡排序算法。

您的函数仅使用一个循环将最大元素移动到其目标位置。但是您需要对数组的所有其他元素重复该过程。

函数如下面的演示程序所示。

#include <stdio.h>

void ft_sort_int_tab( int *tab, size_t size )
{
    for ( size_t last = size; !( size < 2 ); size = last )
    {
        for ( size_t i = last = 1; i < size; ++i )
        {
            if ( tab[i] < tab[i-1] )
            {
                int tmp = tab[i];
                tab[i] = tab[i - 1];
                tab[i - 1] = tmp;
                
                last = i;
            }
        }
    }
}
    
int main(void) 
{
    int tab[] = { 9, 5, 2, 3, 8, 4, 16, 20, 24 };
    const size_t N = sizeof( tab ) / sizeof( *tab );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", tab[i] );
    }
    putchar( '\n' );
    
    ft_sort_int_tab( tab, N );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", tab[i] );
    }
    putchar( '\n' );

    return 0;
}

程序输出为

9 5 2 3 8 4 16 20 24 
2 3 4 5 8 9 16 20 24

注意，一般情况下，数组中的元素个数应该由size_t类型的对象指定。它是运算符 sizeof 返回值的类型。 int 类型的对象可能不够大，无法存储数组中可能的元素数。

一种更通用的方法是向函数添加一个参数，用于指定数组排序的标准。使用这种方法，您可以使用同一个函数按升序或降序对数组进行排序。

这是一个演示程序。

#include <stdio.h>

int ascending( int x, int y )
{
    return x < y;
}

int descending( int x, int y )
{
    return y < x;
}

void ft_sort_int_tab( int *tab, size_t size, int cmp( int, int ) )
{
    for ( size_t last = size; !( size < 2 ); size = last )
    {
        for ( size_t i = last = 1; i < size; ++i )
        {
            if ( cmp( tab[i], tab[i-1] ) )
            {
                int tmp = tab[i];
                tab[i] = tab[i - 1];
                tab[i - 1] = tmp;
                
                last = i;
            }
        }
    }
}
    
int main(void) 
{
    int tab[] = { 9, 5, 2, 3, 8, 4, 16, 20, 24 };
    const size_t N = sizeof( tab ) / sizeof( *tab );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", tab[i] );
    }
    putchar( '\n' );
    
    ft_sort_int_tab( tab, N, ascending );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", tab[i] );
    }
    putchar( '\n' );

    ft_sort_int_tab( tab, N, descending );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", tab[i] );
    }
    putchar( '\n' );

    return 0;
}

程序输出为

9 5 2 3 8 4 16 20 24 
2 3 4 5 8 9 16 20 24 
24 20 16 9 8 5 4 3 2

按升序排列数组元素的函数

function which arranges the elements of an array in ascending order

c

arrays

sorting

bubble-sort

function-definition