递归冒泡排序-yiteyi-C++库

背景： 气泡排序是最简单的排序算法，如果相邻元素的顺序错误，则重复交换相邻元素。 例子： 第一关： ( 5. 1. 4 2 8 ) –> ( 1. 5. 4.2.8），这里，算法比较前两个元素，并从5>1开始交换。 ( 1 5. 4. 2 8 ) –> ( 1 4. 5. 2.8），从5>4开始交换 ( 1 4 5. 2. 8 ) –> ( 1 4 2. 5. 8），从5>2开始交换 ( 1 4 2 5. 8. ) –> ( 1 4 2 5. 8. )现在，由于这些元素已经按顺序排列（8>5），所以算法不会交换它们。 第二关： ( 1. 4. 2 5 8 ) –> ( 1. 4. 2 5 8 ) ( 1 4. 2. 5 8 ) –> ( 1 2. 4. 5.8），从4>2开始交换 ( 1 2 4. 5. 8 ) –> ( 1 2 4. 5. 8 ) ( 1 2 4 5. 8. ) –> ( 1 2 4 5. 8. ) 现在，数组已经排序，但我们的算法不知道它是否完成。算法需要一个整体不经过任何交换以知道它已排序。 第三关： ( 1. 2. 4 5 8 ) –> ( 1. 2. 4 5 8 ) ( 1 2. 4. 5 8 ) –> ( 1 2. 4. 5 8 ) ( 1 2 4. 5. 8 ) –> ( 1 2 4. 5. 8 ) ( 1 2 4 5. 8. ) –> ( 1 2 4 5. 8. ) 以下是迭代气泡排序算法：

null

// Iterative Bubble SortbubbleSort(arr[], n){  for (i = 0; i < n-1; i++)           // Last i elements are already in place        for (j = 0; j < n-i-1; j++)     {         if(arr[j] > arr[j+1])             swap(arr[j], arr[j+1]);     }}

看见气泡排序更多细节。 如何递归地实现它？ 递归冒泡排序没有性能/实现方面的优势，但对于检查人们对冒泡排序和递归的理解来说，这是一个很好的问题。如果我们仔细观察冒泡排序算法，我们可以注意到，在第一次遍历中，我们将最大的元素移动到末尾（假设排序顺序是递增的）。在第二步中，我们将第二大元素移动到最后一个位置，以此类推。 递归思想。

基本情况：如果数组大小为1，则返回。
做一次普通的气泡排序。此过程修复当前子阵列的最后一个元素。
对除当前子阵列的最后一个元素以外的所有元素重复出现。

下面是上述想法的实现。

C++

                         // C/C++ program for recursive implementation                       
                         // of Bubble sort                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A function to implement bubble sort                       
                         void                                     bubbleSort(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Base case                       
                                                 if                                     (n == 1)                       
                                                 return                                     ;                       
           
                                                 // One pass of bubble sort. After                       
                                                 // this pass, the largest element                       
                                                 // is moved (or bubbled) to end.                       
                                                 for                                     (                                     int                                     i=0; i<n-1; i++)                       
                                                 if                                     (arr[i] > arr[i+1])                       
                                                 swap(arr[i], arr[i+1]);                       
           
                                                 // Largest element is fixed,                       
                                                 // recur for remaining array                       
                                                 bubbleSort(arr, n-1);                       
                         }                       
           
                         /* Function to print an array */                       
                         void                                     printArray(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i=0; i < n; i++)                       
                                                 printf                                     (                                     "%d "                                     , arr[i]);                       
                                                 printf                                     (                                     ""                                     );                       
                         }                       
           
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {64, 34, 25, 12, 22, 11, 90};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 bubbleSort(arr, n);                       
                                                 printf                                     (                                     "Sorted array : "                                     );                       
                                                 printArray(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program for recursive implementation                       
                         // of Bubble sort                       
           
                         import                                     java.util.Arrays;                       
           
                         public                                     class                                     GFG                       
                         {                       
                                                 // A function to implement bubble sort                       
                                                 static                                     void                                     bubbleSort(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 // Base case                       
                                                 if                                     (n ==                                     1                                     )                       
                                                 return                                     ;                       
                                   
                                                 // One pass of bubble sort. After                       
                                                 // this pass, the largest element                       
                                                 // is moved (or bubbled) to end.                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<n-                                     1                                     ; i++)                       
                                                 if                                     (arr[i] > arr[i+                                     1                                     ])                       
                                                 {                       
                                                 // swap arr[i], arr[i+1]                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[i+                                     1                                     ];                       
                                                 arr[i+                                     1                                     ] = temp;                       
                                                 }                       
                                   
                                                 // Largest element is fixed,                       
                                                 // recur for remaining array                       
                                                 bubbleSort(arr, n-                                     1                                     );                       
                                                 }                       
                                   
                                                 // Driver Method                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     64                                     ,                                     34                                     ,                                     25                                     ,                                     12                                     ,                                     22                                     ,                                     11                                     ,                                     90                                     };                       
                                   
                                                 bubbleSort(arr, arr.length);                       
                                   
                                                 System.out.println(                                     "Sorted array : "                                     );                       
                                                 System.out.println(Arrays.toString(arr));                       
                                                 }                       
                         }                       

Python3

                         # Python Program for implementation of                       
                         # Recursive Bubble sort                       
                         class                                     bubbleSort:                       
                                                 """                       
                                                 bubbleSort:                       
                                                 function:                       
                                                 bubbleSortRecursive : recursive                       
                                                 function to sort array                       
                                                 __str__ : format print of array                       
                                                 __init__ : constructor                       
                                                 function in python                       
                                                 variables:                       
                                                 self.array = contains array                       
                                                 self.length = length of array                       
                                                 """                       
           
                                                 def                                     __init__(                                     self                                     , array):                       
                                                 self                                     .array                                     =                                     array                       
                                                 self                                     .length                                     =                                     len                                     (array)                       
           
                                                 def                                     __str__(                                     self                                     ):                       
                                                 return                                     " "                                     .join([                                     str                                     (x)                       
                                                 for                                     x                                     in                                     self                                     .array])                       
           
                                                 def                                     bubbleSortRecursive(                                     self                                     , n                                     =                                     None                                     ):                       
                                                 if                                     n                                     is                                     None                                     :                       
                                                 n                                     =                                     self                                     .length                       
           
                                                 # Base case                       
                                                 if                                     n                                     =                                     =                                     1                                     :                       
                                                 return                       
           
                                                 # One pass of bubble sort. After                       
                                                 # this pass, the largest element                       
                                                 # is moved (or bubbled) to end.                       
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     1                                     ):                       
                                                 if                                     self                                     .array[i] >                                     self                                     .array[i                                     +                                     1                                     ]:                       
                                                 self                                     .array[i],                                     self                                     .array[i                                     +                       
                                                 1                                     ]                                     =                                     self                                     .array[i                                     +                                     1                                     ],                                     self                                     .array[i]                       
           
                                                 # Largest element is fixed,                       
                                                 #  recur for remaining array                       
                                                 self                                     .bubbleSortRecursive(n                                     -                                     1                                     )                       
           
                         # Driver Code                       
                         def                                     main():                       
                                                 array                                     =                                     [                                     64                                     ,                                     34                                     ,                                     25                                     ,                                     12                                     ,                                     22                                     ,                                     11                                     ,                                     90                                     ]                       
                                   
                                                 # Creating object for class                       
                                                 sort                                     =                                     bubbleSort(array)                       
                                   
                                                 # Sorting array                       
                                                 sort.bubbleSortRecursive()                       
                                                 print                                     (                                     "Sorted array :"                                     , sort)                       
           
           
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
                                                 main()                       
           
                         # Code contributed by Mohit Gupta_OMG,                       
                         # improved by itsvinayak                       

C#

                         // C# program for recursive                       
                         // implementation of Bubble sort                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // A function to implement                       
                         // bubble sort                       
                         static                                     void                                     bubbleSort(                                     int                                     []arr,                       
                                                 int                                     n)                       
                         {                       
                                                 // Base case                       
                                                 if                                     (n == 1)                       
                                                 return                                     ;                       
           
                                                 // One pass of bubble                       
                                                 // sort. After this pass,                       
                                                 // the largest element                       
                                                 // is moved (or bubbled)                       
                                                 // to end.                       
                                                 for                                     (                                     int                                     i = 0; i < n - 1; i++)                       
                                                 if                                     (arr[i] > arr[i + 1])                       
                                                 {                       
                                                 // swap arr[i], arr[i+1]                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[i + 1];                       
                                                 arr[i + 1] = temp;                       
                                                 }                       
           
                                                 // Largest element is fixed,                       
                                                 // recur for remaining array                       
                                                 bubbleSort(arr, n - 1);                       
                         }                       
           
                         // Driver code                       
                         static                                     void                                     Main()                       
                         {                       
                                                 int                                     []arr = {64, 34, 25,                       
                                                 12, 22, 11, 90};                       
           
                                                 bubbleSort(arr, arr.Length);                       
                                   
                                                 Console.WriteLine(                                     "Sorted array : "                                     );                       
                                                 for                                     (                                     int                                     i = 0; i < arr.Length; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by Sam007                       

Javascript

                         <script>                       
                         // javascript program for recursive                       
                         // implementation of Bubble sort                       
           
                         // A function to implement                       
                         // bubble sort                       
                                                 function                                     bubbleSort(arr, n)                       
                         {                       
           
                                                 // Base case                       
                                                 if                                     (n == 1)                       
                                                 return                                     ;                       
                                   
                                                 // One pass of bubble                       
                                                 // sort. After this pass,                       
                                                 // the largest element                       
                                                 // is moved (or bubbled)                       
                                                 // to end.                       
                                   
                                                 for                                     (                                     var                                     i = 0; i < n - 1; i++)                       
                                                 if                                     (arr[i] > arr[i + 1])                       
                                                 {                       
                                   
                                                 // swap arr[i], arr[i+1]                       
                                                 var                                     temp = arr[i];                       
                                                 arr[i] = arr[i + 1];                       
                                                 arr[i + 1] = temp;                       
                                                 }                       
                                   
                                                 // Largest element is fixed,                       
                                                 // recur for remaining array                       
                                                 bubbleSort(arr, n - 1);                       
                         }                       
                                   
                         // Driver code                       
           
                                                 var                                     arr = [64, 34, 25, 12, 22, 11, 90 ]                       
                                                 bubbleSort(arr, arr.length);                       
                                                 document.write(                                     "Sorted array : "                                     +                                     "<br>"                                     );                       
                                                 for                                     (                                     var                                     i = 0; i < arr.length; i++) {                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                                 }                       
                                   
                                                 // This code is contributed by bunnyram19.                       
                                                 </script>                       

输出：

Sorted array :11 12 22 25 34 64 90

本文由 超级机器人 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章