2

有人可以在下面的冒泡排序中解释第二个 for 循环的确切目的吗？我知道第一个循环正在查看数组的第 i 个整数，但是第二个 for 循环查看的到底是什么？

请原谅我对这个话题的无知。我已经编码不到一周了，对这个主题有些困惑。

void sort(int array[], int size) {
  for(int i = 0, x = size - 1; i < x; i++) {
    for(int j = 0; j < x - 1; j++) {
      if(array[j] > array[j + 1]) {
        int tmp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = tmp;
      }
    }
  }
}
4

2 回答 2

4

我猜你的第一个循环也是错误的，考虑到你想要实现Bubble Sort，因为第一个循环告诉了对列表进行排序所需的通过次数。在冒泡排序的情况下，它等于Total Number of elements - 1需要通过的次数来对 n 个元素的列表进行排序 (n - 1) 需要通过，因此i如果我没记错的话，我的拙见必须从 1 开始。此外，就您在需要时声明变量而言，您提供的代码段与 C 语言编码风格不同。

第二个循环基本上是为了减少比较（元素数 - 通过 - 1），在每次迭代之后，因为每次通过，我们将最大的元素放在右侧（逻辑上未排序的列表）。因此，由于该元素处于其应有的位置，因此我们不必将其与其他元素进行比较。

  4 3 2 1 Original List
  3 2 1 4 Pass 1
        -
        Now since this above 4 is in it's rightful place
        we don't need to compare it with other elements.
        Hence we will start from the zeroth element and 
        compare two adjacent values, till 1 (for Pass 2)
        Here comparison will take place between 3 and 2,
        and since 3 is greater than 2, hence swapping 
        between 3 and 2, takes place. Now 3 is comapred
        with 1, again since greater value is on left
        side, so swapping will occur. Now 3 is not compared
        with 4, since both these values are in their 
        rightful place.
  2 1 3 4 Pass 2
      - 
        Now since this above 3 is in it's rightful place
        we don't need to compare it with other elements.
        Hence we will start from the zeroth element and 
        compare two adjacent values, till 1 (for Pass 3)
        Here only one comparison will occur, between
        2 and 1. After swapping 2 will come to it's rightful
        position. So no further comparison is needed.
  1 2 3 4 Pass 3
  Here the list is sorted, so no more comparisons, after Pass 3.    


void bubbleSort(int *ptr, int size)
{
        int pass = 1, i = 0, temp = 0;
        for (pass = 1; pass < size - 1; pass++)
        {
                for (i = 0; i <= size - pass - 1; i++)
                {
                        if (*(ptr + i) > *(ptr + i + 1))
                        {
                                temp = *(ptr + i);
                                *(ptr + i) = *(ptr + i + 1);
                                *(ptr + i + 1) = temp;
                        }
                }
                printf("Pass : %d\n", pass);
                for (temp = 0; temp < size; temp++)
                        printf("%d\t", *(ptr + temp));
                puts("");
        }
}
于 2013-03-10T06:21:47.663 回答
1

您的冒泡排序循环是错误的。这是正确的：

void bubbleSort(int numbers[], int array_size) {
  int i, j, temp;

  for (i = (array_size - 1); i > 0; i--) {
    for (j = 1; j <= i; j++) {
      if (numbers[j-1] > numbers[j]) {
        temp = numbers[j-1];
        numbers[j-1] = numbers[j];
        numbers[j] = temp;
      }
    }
  }
}

第二个循环是做主要工作。它比较每一对并交换它们的位置，以便较大的数字向右（右边更接近数组的末尾）。

于 2013-03-10T06:24:19.080 回答