使用第二個循環在泡沫排序

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

第二個循環正在做主要工作。它比較每一對並交換它們的位置，以使較大的數字向右（右邊靠近陣列的末端）。