奇偶排序/砖块排序-yiteyi-C++库

这基本上是气泡排序 .此算法分为两个阶段-奇数阶段和偶数阶段。该算法一直运行，直到数组元素被排序，并且在每次迭代中出现两个阶段——奇数和偶数阶段。在奇数阶段，我们对奇数索引元素执行气泡排序，在偶数阶段，我们对偶数索引元素执行气泡排序。

null

C++

                         // A C++ Program to implement Odd-Even / Brick Sort                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A function to sort the algorithm using Odd Even sort                       
                         void                                     oddEvenSort(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 bool                                     isSorted =                                     false                                     ;                                     // Initially array is unsorted                       
           
                                                 while                                     (!isSorted)                       
                                                 {                       
                                                 isSorted =                                     true                                     ;                       
           
                                                 // Perform Bubble sort on odd indexed element                       
                                                 for                                     (                                     int                                     i=1; i<=n-2; i=i+2)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+1])                       
                                                 {                       
                                                 swap(arr[i], arr[i+1]);                       
                                                 isSorted =                                     false                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Perform Bubble sort on even indexed element                       
                                                 for                                     (                                     int                                     i=0; i<=n-2; i=i+2)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+1])                       
                                                 {                       
                                                 swap(arr[i], arr[i+1]);                       
                                                 isSorted =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 return                                     ;                       
                         }                       
           
                         // A utility function ot print an array of size n                       
                         void                                     printArray(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i=0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 cout <<                                     ""                                     ;                       
                         }                       
           
                         // Driver program to test above functions.                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {34, 2, 10, -9};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
           
                                                 oddEvenSort(arr, n);                       
                                                 printArray(arr, n);                       
           
                                                 return                                     (0);                       
                         }                       

JAVA

                         // Java Program to implement                       
                         // Odd-Even / Brick Sort                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 public                                     static                                     void                                     oddEvenSort(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 boolean                                     isSorted =                                     false                                     ;                                     // Initially array is unsorted                       
           
                                                 while                                     (!isSorted)                       
                                                 {                       
                                                 isSorted =                                     true                                     ;                       
                                                 int                                     temp =                                     0                                     ;                       
           
                                                 // Perform Bubble sort on odd indexed element                       
                                                 for                                     (                                     int                                     i=                                     1                                     ; i<=n-                                     2                                     ; i=i+                                     2                                     )                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+                                     1                                     ])                       
                                                 {                       
                                                 temp = arr[i];                       
                                                 arr[i] = arr[i+                                     1                                     ];                       
                                                 arr[i+                                     1                                     ] = temp;                       
                                                 isSorted =                                     false                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Perform Bubble sort on even indexed element                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<=n-                                     2                                     ; i=i+                                     2                                     )                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+                                     1                                     ])                       
                                                 {                       
                                                 temp = arr[i];                       
                                                 arr[i] = arr[i+                                     1                                     ];                       
                                                 arr[i+                                     1                                     ] = temp;                       
                                                 isSorted =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 return                                     ;                       
                                                 }                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     34                                     ,                                     2                                     ,                                     10                                     , -                                     9                                     };                       
                                                 int                                     n = arr.length;                       
           
                                                 oddEvenSort(arr, n);                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i < n; i++)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
           
                                                 System.out.println(                                     " "                                     );                       
                                                 }                       
                         }                       
                         // Code Contribute by Mohit Gupta_OMG <(0_o)>                       

Python3

                         # Python Program to implement                       
                         # Odd-Even / Brick Sort                       
           
                         def                                     oddEvenSort(arr, n):                       
                                                 # Initially array is unsorted                       
                                                 isSorted                                     =                                     0                       
                                                 while                                     isSorted                                     =                                     =                                     0                                     :                       
                                                 isSorted                                     =                                     1                       
                                                 temp                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     -                                     1                                     ,                                     2                                     ):                       
                                                 if                                     arr[i] > arr[i                                     +                                     1                                     ]:                       
                                                 arr[i], arr[i                                     +                                     1                                     ]                                     =                                     arr[i                                     +                                     1                                     ], arr[i]                       
                                                 isSorted                                     =                                     0                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n                                     -                                     1                                     ,                                     2                                     ):                       
                                                 if                                     arr[i] > arr[i                                     +                                     1                                     ]:                       
                                                 arr[i], arr[i                                     +                                     1                                     ]                                     =                                     arr[i                                     +                                     1                                     ], arr[i]                       
                                                 isSorted                                     =                                     0                       
                                   
                                                 return                       
           
           
                         arr                                     =                                     [                                     34                                     ,                                     2                                     ,                                     10                                     ,                                     -                                     9                                     ]                       
                         n                                     =                                     len                                     (arr)                       
           
                         oddEvenSort(arr, n);                       
                         for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
                                                 print                                     (arr[i], end                                     =                                     ' '                                     )                       
                                   
                         # Code Contribute by Mohit Gupta_OMG <(0_o)>                       

C#

                         // C# Program to implement                       
                         // Odd-Even / Brick Sort                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 public                                     static                                     void                                     oddEvenSort(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 // Initially array is unsorted                       
                                                 bool                                     isSorted =                                     false                                     ;                       
           
                                                 while                                     (!isSorted)                       
                                                 {                       
                                                 isSorted =                                     true                                     ;                       
                                                 int                                     temp =0;                       
           
                                                 // Perform Bubble sort on                       
                                                 // odd indexed element                       
                                                 for                                     (                                     int                                     i = 1; i <= n - 2; i = i + 2)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+1])                       
                                                 {                       
                                                 temp = arr[i];                       
                                                 arr[i] = arr[i+1];                       
                                                 arr[i+1] = temp;                       
                                                 isSorted =                                     false                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // Perform Bubble sort on                       
                                                 // even indexed element                       
                                                 for                                     (                                     int                                     i = 0; i <= n - 2; i = i + 2)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+1])                       
                                                 {                       
                                                 temp = arr[i];                       
                                                 arr[i] = arr[i+1];                       
                                                 arr[i+1] = temp;                       
                                                 isSorted =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     ;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []arr = {34, 2, 10, -9};                       
                                                 int                                     n = arr.Length;                       
                                   
                                                 // Function calling                       
                                                 oddEvenSort(arr, n);                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
           
                                                 Console.WriteLine(                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

Javascript

                         <script>                       
           
                         // Javascript Program to implement                       
                         // Odd-Even / Brick Sort                       
           
                                                 function                                     oddEvenSort(arr, n)                       
                                                 {                       
                                                 // Initially array is unsorted                       
                                   
                                                 let isSorted =                                     false                                     ;                       
                                   
                                                 while                                     (!isSorted)                       
                                                 {                       
                                                 isSorted =                                     true                                     ;                       
                                                 let temp =0;                       
                                   
                                                 // Perform Bubble sort on odd indexed element                       
                                                 for                                     (let i=1; i<=n-2; i=i+2)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+1])                       
                                                 {                       
                                                 temp = arr[i];                       
                                                 arr[i] = arr[i+1];                       
                                                 arr[i+1] = temp;                       
                                                 isSorted =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 // Perform Bubble sort on even indexed element                       
                                                 for                                     (let i=0; i<=n-2; i=i+2)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+1])                       
                                                 {                       
                                                 temp = arr[i];                       
                                                 arr[i] = arr[i+1];                       
                                                 arr[i+1] = temp;                       
                                                 isSorted =                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     ;                       
                                                 }                       
           
                         // Driver Code                       
                                   
                                                 let arr = [34, 2, 10, -9];                       
                                                 let n = arr.length;                       
                                   
                                                 oddEvenSort(arr, n);                       
                                                 for                                     (let i=0; i < n; i++)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                   
                                                 document.write(                                     " "                                     );                       
                                   
                         </script>                       

输出：

-9 2 10 34

我们在数组＝{3,2,3,8,5,6,4,1}上使用下图演示上述算法

图片[1]-奇偶排序/砖块排序-yiteyi-C++库

请参考维基为了证明正确性。时间复杂度：O（N） ^2. )其中，N=输入数组中的元素数。辅助空间：O（1）。就像气泡排序一样，这也是一种就地算法。运动在我们的程序中，在每次迭代中，我们首先对奇数索引元素进行冒泡排序，然后对偶数索引元素进行冒泡排序。如果我们先对偶数索引元素执行冒泡排序，然后对奇数索引元素执行冒泡排序，我们会得到排序结果吗？ 工具书类 https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort 本文由Rachit Belwariar撰稿。如果你喜欢GeekSforgeks，并且想贡献自己的力量，你也可以写一篇文章，然后把你的文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

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

THE END

技术文章