int列表中弹出不需要的元素

Question

我已经编写了一个C程序来生成随机数，然后使用bubbleort-algorithm对它们进行排序。但是，不管随机生成的数字是什么，打印出这些数字（通过数组，请参见代码）都将显示第一个元素为63。是什么原因造成的？有没有比跳过列表的第一个元素更好的绕过此方法的方法？

int list[10];
int cache_num;
srand((unsigned) (time(NULL))); //Gives the rand() function a new seed from the current time

for (int i = 0; i < 10; i++) {
    list[i] = rand();
    printf("\n%d", list[i]);
}

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < (10 - i); j++) {
        if (list[j] > list[j + 1]) {
            cache_num = list[j];
            list[j] = list[j + 1];
            list[j + 1] = cache_num;
        }
    }
}
for (int i = 0; i < 10; i++) {
    printf("\n%d", list[i]);
}

Answer 1

在这些循环的内部循环中

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < (10 - i); j++) {
        if (list[j] > list[j + 1]) {
            cache_num = list[j];
            list[j] = list[j + 1];
            list[j + 1] = cache_num;
        }
    }
}

可以使用索引10访问数组的不存在的元素

            list[j] = list[j + 1];
                          ^^^^^^

当j等于9时。

最好像这样编写循环

    for (int j = 1; j < (10 - i); j++) {
        if (list[j - 1] > list[j]) {
            cache_num = list[j];
            list[j] = list[j - 1];
            list[j - 1] = cache_num;
        }

Answer 2

当变量j达到9的值时，您将越过数组。使用(10 - i - 1)解决问题：

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

int main(void) {
    int list[10];
    int cache_num;

    srand((unsigned) (time(NULL))); //Gives the rand() function a new seed from the current time

    for (int i = 0; i < 10; i++) {
        list[i] = rand();
        printf("%d\n", list[i]);
    }

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < (10 - i - 1); j++) { // note here ...
            if (list[j] > list[j + 1]) {
                cache_num = list[j];
                list[j] = list[j + 1];
                list[j + 1] = cache_num;
            }
        }
    }

    putchar('\n');
    for (int i = 0; i < 10; i++) {
        printf("%d\n", list[i]);
    }

    return 0;
}

Answer 3

在以下几行中，您超出了范围，因此您将获得垃圾值，从而改变了最终结果。例：当i = 0且j = 9时，此循环的终止条件为9 < 10-0，该条件为true，它将执行。但是对于list [j + 1]，由于没有list [10]，它将超出范围。

for (int j = 0; j < (10 - i); j++){ ... }

它的条件应为-1，(10-i-1)

for (int j = 0; j < (10 - i - 1); j++) { ... }

Answer 4

您可以使用以下实现来代替对冒泡排序进行排序以对10个元素的数据进行排序的实现。

背后的想法是，当您分析（which you should）时，冒泡排序算法基本上是如何对数据进行排序的，您会看到一个模式，即在内部循环的每一遍中，最大的元素（在排序的情况下）数据按升序排列）将自动转到正确的位置，因此，您不必再考虑该元素，因为它已经处于正确的位置。

#include<stdio.h> // For basic I/O functions.
#include<stdlib.h> // For srand() & rand() functions.
#include<time.h> // For time(NULL) functions.

#define MAX_ARRAY_SIZE 10

int main(void) {
    int list[10];
    srand(time(NULL));
    for(int i = 0; i < MAX_ARRAY_SIZE; ++i) {
        list[i] = rand();
    }
    // Implementation of Bubble-Sort

    for(int i = (MAX_ARRAY_SIZE - 1); i >=0; --i) {
        bool is_sorted = true;
        for(int j = 0; j < i; ++j) {
            if(list[j] > list[j + 1]) {
                int cache_num = list[j];
                list[j] = list[j + 1];
                list[j + 1] = cache_num;
                is_sorted = false;
            }
        }
        if(is_sorted) {
            break;
        }
    }

    for(int i = 0; i < MAX_ARRAY_SIZE; ++i) {
        printf("%d ", list[i]);
    }
    printf("\n");
    return 0;
}

P.S。由于仅排序10个元素，因此使用冒泡排序不会有任何区别，但我建议您使用插入排序而不是冒泡排序，因为对于小尺寸数组，插入排序速度更快。请参阅Comparison Between Bubble-Sort/Selection-Sort/Insertion-Sort。