使用第二个循环在泡沫排序

Question

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

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

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; 
     } 
    } 
    } 
} 

Answer 1

我想你的第一个循环是错误太多，考虑到要实现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(""); 
     } 
} 

Answer 2

你的气泡排序循环是错误的。这是正确的：

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; 
     } 
    } 
    } 
} 

第二个循环正在做主要工作。它比较每一对并交换它们的位置，以使较大的数字向右（右边靠近阵列的末端）。