c - 当用户输入每个数组位置的值时对数组进行排序

Question

当用户输入数组的值时，我尝试对数组的值进行排序。

问题是我想避免尝试使用“冒泡”或“快速排序”方法。

这是我的代码及其工作原理:

int i, j, k;
      int number;
      for (i = 0; i < size; i = i + 1) {
          printf("Give me the number #%d to add to the list: ", i + 1);
          while (!scanf("%d", &list[i])) {
            while(getchar() != '\n');
            printf("You can't use chars!.\n");
            printf("Give me the number #%d to add to the list: ", i + 1);
          }
          number = list[i];
          if (number < list[i-1]) {
            list[i-1] = list[i];
            list[i] = number;
          }
      }
      for (i = 0; i < size; i = i + 1) {
        printf("%d,", list[i]);
      }

我得到了什么:

How much numbers do you want to order? 5
Give me the number #1 to add to the list: 5
Give me the number #2 to add to the list: 4
Give me the number #3 to add to the list: 3
Give me the number #4 to add to the list: 2
Give me the number #5 to add to the list: 1
4,3,2,1,1,% // here is the problem, the expected output should be: 1,2,3,4,5 (for example, if I have 5,8,3,2,9 I should get: 2,3,5,8,9).

我希望能解释一下为什么我的代码无法正常工作，如果可能的话，希望能提供有关如何可视化将来此类问题的建议。

预先感谢您的帮助。

Answer 1

为了保持数组有序，您应该对每个输入数字进行(部分)插入排序。

只是提醒您插入排序算法，它对第 i 次迭代执行以下操作:

1. 数组从索引 0 到索引 i-1 排序
2. 您有一个新号码，list[i]。
3. 您应该确定这个新数字在数组中的位置，因此将数字移到后面，直到看到新数字的位置。
4. 一旦您看到一个不大于新数字的数字，您现在就可以在该数字后面添加新数字。

您的代码的问题是您没有正确转换。

您必须将所有大于新数字的数字移到后面，以便为新数字腾出空间。但你的代码只移动最后一个数字。

    int i, j, k;
    int number;
    for (i = 0; i < size; i = i + 1)
    {
        printf("Give me the number #%d to add to the list: ", i + 1);
        while (!scanf("%d", &list[i]))
        {
            while (getchar() != '\n')
                ;
            printf("You can't use chars!.\n");
            printf("Give me the number #%d to add to the list: ", i + 1);
        }
        number = list[i];

        /* Here's the point! Shift all numbers bigger than *number* to the back. */
        for (j = i; j > 0 && number < list[j - 1]; j--)
        {
            list[j] = list[j - 1];
        }
        list[j] = number;
    }
    for (i = 0; i < size; i = i + 1)
    {
        printf("%d,", list[i]);
    }

(请原谅重新格式化，这只是我的 IDE 所做的事情。)