c - 面临 C 中冒泡排序算法的困难

Question

首先，我是 C 的初学者，所以如果我的问题看起来很愚蠢，我很抱歉。
我正在学习如何在 C 中使用冒泡排序算法，我通过以下代码:

#include <stdio.h>

int main() {
    int ctr, inner, outer, didSwap, temp;
    int nums[10] = {
        78,
        16,
        21,
        7,
        13,
        9,
        22,
        52,
        67,
        19
    };

    //Listing the array before sorting

    for (ctr = 0; ctr < 10; ctr++) {
        printf("%d\n", nums[ctr]);
    }

    //Sorting the arrays

    for (outer = 0; outer < 9; outer++) {
        didSwap = 0;
        for (inner = outer; inner < 10; inner++) {
            if (nums[inner] < nums[outer]) {
                temp = nums[inner];
                nums[inner] = nums[outer];
                nums[outer] = temp;
                didSwap = 1;
            }
        }
        if (didSwap == 0) {
            break;
        }
    }

    //Listing the array after sorting

    printf("\n\nThis is the sorted array\n");
    for (ctr = 0; ctr < 10; ctr++) {
        printf("%d\n", nums[ctr]);
    }

    return 0;
}

代码工作正常，但我想了解的是如何在第二个 for 循环中编写 inner = outer ，并且在下一个 if 语句中，它比较数组的元素，其中一个与内部的编号相同，另一个与外部的编号相同。
既然我们说了 inner = outer ，这意味着我们正在比较相同的元素。
我的想法是，如果 outer = 0 ，以及自 inner = outer ，然后 inner将是 0同样，所以下一个 if 语句将是 if (nums[0] < nums[0])这没有任何意义。

我知道我可能错了，因为代码运行良好，但我认为哪里错了？

提前致谢。

Answer 1

冒泡排序的本质是每次扫描时“冒泡”是迄今为止看到的最大值，因此在扫描结束时，最大值“冒泡”到顶部。然后你从头开始重复，但每次(显然)你需要考虑的值(value)减少。此外，如果在扫描结束时没有任何移动，则一切正常，您可以停止。

所以冒泡排序可能看起来像这样:

    for (int n = 10 ; n > 0 ; n--)
      {
        bool no_swaps ;

        no_swaps = true ;
        for (int i = 1 ; i < n ; ++i)
          {
            if (nums[i-1] > nums[i])
              {
                int temp ;
                temp = nums[i-1];
                nums[i-1] = nums[i];
                nums[i]   = temp;
                no_swaps = false ;
              } ;
          } ;

        if (no_swaps)
          break ;
      } ;

或者:

    for (int n = 10 ; n > 0 ; n--)
      {
        bool no_swaps ;
        int bubb ;

        no_swaps = true ;
        bubb = nums[0] ;
        for (int i = 1 ; i < n ; ++i)
          {
            int this ;

            this = nums[i] ;
            if (bubb <= this)
              bubb = this ;
            else
              {
                nums[i-1] = this ;
                nums[i]   = bubb ;
                no_swaps = false;
              } ;
          } ;

        if (no_swaps)
          break ;
      } ;

这也许更清楚地表明，同名的“气泡”( bubb )是当前扫描中发现的最大值(或最右边的最大值，如果已经看到 2 个或更多具有该值的值)。

如果删除 didSwap从你的排序来看，它会正常工作。与冒泡排序一样，排序的每一次传递都会将一个项目移动到其最终目的地。你的排序总是这样 (n-1)*(n-2)/2比较，这与冒泡排序的最坏情况相同。但是冒泡排序最好的情况是 (n-1) - 如果值已经是有序的!

所以真正的冒泡排序比你的排序有优势。尽管如此，冒泡排序一般也是 O(n^2) 因此，除了 之外，它几乎和巧克力茶壶一样有用是小。