C中的气泡排序算法–是吗？

Question

我目前是CS50x的学生。

我一直在寻找搜索和排序算法。试图通过代码理解它们。现在，关于冒泡排序：我创建了我认为的冒泡排序算法。但是我不太适合需要将交换计数设置为非零值的想法。我的算法（如下）对所有数字进行排序。但是我在哪里适合掉期想法？如果有人能这么善于解释，我将不胜感激。

#import <stdio.h>
#import <cs50.h>

int main(void)
{

    // Creating an unsorted array

    int count = 10;

    int array[count];

    for (int z = 0; z < count; z++)
        scanf("%i", &array[z]);


    // Bubble Sort

    int buffer;

    for (int b = 0; b < count; b++)
    {

        int a = 0;

        while (a < count)
        {
            if (array[a] > array[a+1])
            {
                buffer = array[a];
                array[a] = array[a+1];
                array[a+1] = buffer;
            }
            a++;
        }

    }

    printf("Sorted: ");

    for (int b = 0; b < count; b++)
        printf("%i ", array[b]);

    printf("\n");

}

Answer 1

指令是#include，而不是#import。计数交换的想法是在没有任何异常的情况下中断外部循环（因为内部循环中不需要交换）。该代码实现了：

#include <stdio.h>

int main(void)
{
    // Creating an unsorted array
    int count = 10;
    int array[count];

    for (int z = 0; z < count; z++)
        scanf("%i", &array[z]);

    putchar('\n');
    printf("%8s:", "Unsorted");
    for (int b = 0; b < count; b++)
        printf(" %i", array[b]);
    printf("\n");

    // Bubble Sort
    for (int b = 0; b < count; b++)
    {
        int a = 0;
        int num_swaps = 0;

        while (a < count - 1)
        {
            if (array[a] > array[a+1])
            {
                int buffer = array[a];
                array[a] = array[a+1];
                array[a+1] = buffer;
                num_swaps++;
            }
            a++;
        }
        if (num_swaps == 0)
            break;
    }

    printf("%8s:", "Sorted");
    for (int b = 0; b < count; b++)
        printf(" %i", array[b]);
    printf("\n");

    return 0;
}

示例运行（源bs97.c编译为bs97；自制的随机数生成器random-所使用的选项将生成10个介于10到99之间的数字）：

$ random -n 10 10 99 | bs97

Unsorted: 68 47 85 39 52 54 31 81 19 59
  Sorted: 19 31 39 47 52 54 59 68 81 85
$ random -n 10 10 99 | bs97

Unsorted: 75 85 36 11 35 87 59 63 26 36 
  Sorted: 11 26 35 36 36 59 63 75 85 87 
$ random -n 10 10 99 | bs97

Unsorted: 90 27 64 90 76 79 52 46 98 99
  Sorted: 27 46 52 64 76 79 90 90 98 99
$ random -n 10 10 99 | bs97

Unsorted: 53 60 87 89 38 68 73 10 69 84
  Sorted: 10 38 53 60 68 69 73 84 87 89
$

请注意，该代码避免在输出中尾随空格。

您还可以在排序int num_swaps = 1;循环之外定义for并在主循环条件下对其进行测试：

for (int b = 0; b < count - 1 && num_swaps > 0; b++)
{
    num_swaps = 0;

并从循环末尾删除if (num_swaps == 0) break;。内部循环也可以是for循环。而且，外循环的第一个循环将最大值移到数组的末尾，因此您可以缩短内循环，从而减少工作量。打印代码也应纳入函数。

#include <stdio.h>

static void dump_array(const char *tag, int size, int data[size])
{
    printf("%8s (%d):", tag, size);
    for (int i = 0; i < size; i++)
        printf(" %i", data[i]);
    printf("\n");
}

int main(void)
{
    // Creating an unsorted array
    int count = 10;
    int array[count];

    for (int z = 0; z < count; z++)
    {
        if (scanf("%i", &array[z]) != 1)
        {
            fprintf(stderr, "Failed to read number %d\n", z + 1);
            return 1;
        }
    }

    putchar('\n');
    dump_array("Unsorted", count, array);

    // Bubble Sort
    int num_swaps = 1;
    for (int b = 0; b < count - 1 && num_swaps > 0; b++)
    {
        for (int a = 0; a < count - b - 1; a++)
        {
            if (array[a] > array[a + 1])
            {
                int buffer = array[a];
                array[a] = array[a + 1];
                array[a + 1] = buffer;
                num_swaps++;
            }
        }
    }

    dump_array("Sorted", count, array);

    return 0;
}

样本输出：

$ random -n 10 10 99 | bs97

Unsorted (10): 31 82 81 40 12 17 70 44 90 12
  Sorted (10): 12 12 17 31 40 44 70 81 82 90
$