C：指向數組的指針和破壞性排序

Question

我寫了一段簡短的代碼。它有兩個功能：bubbleSort是一個氣泡排序功能（從小到大），「int main」用於測試這段代碼的大小爲5的int數組。

我希望這個破壞性地排序該數組，而不是簡單地通過一個副本。我看了看，但我還不完全清楚這應該如何工作。我在這裏錯過了什麼？

#include <stdio.h> 

void bubbleSort(int values[], int n); 

int main(void) { 
//set simple test array to make sure bubbleSort works 
    int arr[5] = {5,4,3,2,1}; 
//run it through function, and then print the now sorted array to make sure 
    bubbleSort(arr, 5); 
    printf("%i", arr); 
    return 0; 
} 


void bubbleSort(int values[], int n) 
{ 
    for (int i = 0; i < n; i++) { 
     for (int j = 0, hold = 0; j < n-i; j++) { 
      if (values[j] > values[j+1]) { 
       hold = values[j+1]; 
       values[j+1] = values[j]; 
       values[j] = hold; 
      } 
     } 
    } 
    return; 
} 

注：我的代碼的其餘部分看起來聲音我的業餘編碼的頭腦，但請給我指點什麼我可以提高，有什麼可以更好，等等。我想過使用遞歸冒泡排序，但我還不喜歡C，因爲我希望實現這一點。但是，如果你有建議，我會很樂意閱讀它們。

謝謝！

Answer 1

看起來你的函數正在對數組進行排序（雖然有一些錯誤），但你只是錯誤地輸出了結果。 printf不知道如何打印數組。相反，你需要使用一個循環，在每次打印每個整數之一：

for(int i=0; i<5; i++){ 
    printf("%d ", arr[i]); 
} 
printf("\n"); 

改變之後，輸出1 2 3 4 5，符合市場預期。

但是，正如評論中所提到的，在實現bubblesort時存在一些錯誤。例如，它試圖在數組結束後從indedex讀取元素，這是未定義的行爲（即，j+1可能是5，這是超出範圍）。我會建議再次檢查您的書籍，以正確實施bubblesort。

Answer 2

你的代碼已經對數組進行了原地排序 - 雖然它有一個錯誤。我只會解決這個問題的主題（在C中對數組進行就地排序），因爲註釋已經使用排序功能突出了錯誤。

結果的打印輸出是不正確雖然因爲它試圖打印arr指針爲一個整數：

sort.c:10:18: warning: format specifies type 'int' but the argument has type 'int *' [-Wformat] 
    printf("%i", arr); 
      ~~ ^~~ 
1 warning generated. 

但是改變這對：

for (int i = 0; i < 5; i++) 
     printf("%i", arr[i]); 

修復與所述問題輸出。

也許你的困惑來自於數組如何實際上是一種訪問C中指針的句法方式。arr是一個指針。 arr[1]與*(arr + 1)（指針arr + 1使用指針算術的內容相同，該指針通過sizeof類型遞增指針）。所以當你將arr傳遞給函數時，你傳遞一個指向現有數組的指針，然後你正在修改它的內容，就地排序數組。

Answer 3

有一個問題在你的氣泡分類代碼中，必須被修復。你的內循環有問題：

/* for (int j = 0, hold = 0; j < n-i; j++) { */ // ISSUE here 
for (int j = 0, hold = 0; j < n-i-1; j++) { // j < n-i-1 should be the condition 

這是becasue，採取循環外時i = 0，即第一iterartion的情況。這一次，當j小於n時，j < n - i將爲真 - 這是數組的最後一個索引。然後你在values[j]和values[j+1]之間進行合作，其中values[j+1]明顯超出了你的數組範圍。這將調用undefined behavior，你的函數不會給出確定性的結果。

接下來的改進可能是你的外循環只需要從i = 0 till i < n-1迭代，即比總元素少一倍。你正在交談一次以上。

第三，您可以使用一個標記在內部循環中至少記錄一次天氣swap。如果在內部循環中沒有交換，則意味着該數組已經排序。因此，在內部循環的每次迭代結束時，您可以看到是否有交換完成，如果沒有交換完成，則從外部循環中跳出。這會在數組已經幾乎排序的情況下提高性能。

void bubbleSort(int values[], int n) 
{   
    int swap; // To use as a flag 

    // for (int i = 0; i < n; i++) { 
    for (int i = 0; i < n-1; i++) {     
      swap = 0;  // set swap flag to zero 
      // for (int j = 0, hold = 0; j < n-i; j++) { 
      for (int j = 0, hold = 0; j < n-i-1; j++) { 
        if (values[j] > values[j+1]) { 
          hold = values[j+1]; 
          values[j+1] = values[j]; 
          values[j] = hold; 
          swap = 1;  // swap was done 
        } 
      } 
      if (swap == 0) // If no swap was done 
        break; // Means array already sorted 
    } 
    return; 
} 

而且，雖然不相關的排序功能，正如其他人所指出的那樣，printf("%i", arr);是錯誤的，因爲你是在printf使用了錯誤的格式說明將調用undefined behavior。看起來你正在嘗試打印數組。對於您可以這樣做：

// printf("%i", arr); 
for (int i = 0; i < 5; i++) 
    printf("%d ", arr[i];) 
printf("\n");