遞歸冒泡排序的C程序

冒泡排序是最簡單的排序演算法之一，用於透過比較相鄰元素對資料進行排序。所有元素都分階段進行比較。第一階段將最大值放在最後，第二階段將第二大元素放在倒數第二個位置，依此類推，直到完整清單排序完畢。

冒泡排序演算法

• int arr[5]= { 5,4,2,1,3 };

• int i, j ;

• 從索引i=0 遍歷到i

  • 從索引j=0 遍歷到數組size - i - 1

  • 如果arr[i]>arr[j] 將arr[i] 與arr[j] 交換

• 結束

遞歸冒泡排序

• #如果陣列length 為1 則傳回

• 遍歷數組一次，固定最大元素在末尾​​p>

• 其餘部分遞歸執行步驟2除最後一個元素之外的數組

範例

輸入 − Arr[] = { 5,7,2,3, 1,4}; length=6

輸出  − 排序數組：1 2 3 4 5 7

說明 −

First Pass
5 7 2 3 1 4 → swap → 5 2 7 3 1 4
5 2 7 3 1 4 → swap → 5 2 3 7 1 4
5 2 3 7 1 4 → swap → 5 2 3 1 7 4
5 2 3 1 7 4 → swap → 5 2 3 1 4 7
Second Pass
5 2 3 1 4 7 → swap → 2 5 3 1 4 7
2 5 3 1 4 7 → swap → 2 3 5 1 4 7
2 3 5 1 4 7 → swap → 2 3 1 5 4 7
2 3 1 5 4 7 → swap → 2 3 1 4 5 7
Third Pass
2 3 1 4 5 7 → swap → 2 1 3 4 5 7
2 1 3 4 5 7 no swap
Fourth Pass
2 1 3 4 5 7 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 no swap in further iterations

輸入− Arr[] = { 1, 2, 3, 3, 2 };

輸出− 排序數組：1 2 2 3 3

說明 -

First Pass
1 2 3 3 2 → swap → 1 2 3 2 3
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 no swap in further iterations
Second Pass
1 2 2 3 3 no swap in further iterations

下程序中使用的方法如下

在冒泡排序的遞歸方法中，基本情況是陣列長度= 1。否則使用單一for迴圈遍歷數組並相應地交換元素。 < /p>

• 將輸入陣列 Arr[] 和長度作為其中元素的數量。

• 函數 recurbublSort(int arr[], int len) 取得陣列及其長度，並使用冒泡排序對陣列進行遞歸排序。

• 取得變數 temp。

< li>

如果陣列長度為 1，則傳回 void。

• 否則使用單一 for 迴圈遍歷數組，並針對每個元素 arr[i]>arr[i 1 ]，交換這些元素。

• 設定 temp=arr[i]、arr[i]=arr[i 1] 和 arr[i 1]=temp。 < /p>

• 現在將長度減 1，因為上一個循環將最大元素放置在最後一個位置。

• 遞歸呼叫recurbublSort(arr,len)。

• 在所有呼叫結束時，當 len 變成 1 時，我們將退出遞歸並對陣列進行排序。

  < /li>

• 在 main 中列印排序後的陣列。

範例

#include <stdio.h>
void recurbublSort(int arr[], int len){
   int temp;

   if (len == 1){
      return;
   }
   for (int i=0; i<len-1; i++){
      if (arr[i] > arr[i+1]){
         temp=arr[i];
         arr[i]=arr[i+1];
         arr[i+1]=temp;
      }
   }
   len=len-1;
   recurbublSort(arr, len);
}
int main(){
   int Arr[] = {21, 34, 20, 31, 78, 43, 66};
   int length = sizeof(Arr)/sizeof(Arr[0]);

   recurbublSort(Arr, length);

   printf("Sorted array : ");
   for(int i=0;i<length;i++){
      printf("%d ",Arr[i]);
   }

   return 0;
}

輸出

如果我們執行上面的程式碼，它將產生以下輸出

Sorted array: 20 21 31 34 43 66 78

#

以上是遞歸冒泡排序的C程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！