梳排序-yiteyi-C++库

梳状排序主要是对冒泡排序的改进。气泡排序总是比较相邻的值。所以倒置一个接一个地被移除。梳状排序通过使用大于1的间隙改进了气泡排序。间隙从一个较大的值开始，并在每次迭代中缩小1.3倍，直到达到值1。因此，梳状排序会删除多个反转计数只需一次交换，性能优于气泡排序。根据经验，收缩系数为1.3（通过在超过200000个随机列表上测试Combsort）[来源：维基 ] 虽然平均而言，它比气泡排序更有效，但最坏的情况仍然是O（n） ^2. ). 下面是实现。

null

C++

                         // C++ implementation of Comb Sort                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // To find gap between elements                       
                         int                                     getNextGap(                                     int                                     gap)                       
                         {                       
                                                 // Shrink gap by Shrink factor                       
                                                 gap = (gap*10)/13;                       
           
                                                 if                                     (gap < 1)                       
                                                 return                                     1;                       
                                                 return                                     gap;                       
                         }                       
           
                         // Function to sort a[0..n-1] using Comb Sort                       
                         void                                     combSort(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 // Initialize gap                       
                                                 int                                     gap = n;                       
           
                                                 // Initialize swapped as true to make sure that                       
                                                 // loop runs                       
                                                 bool                                     swapped =                                     true                                     ;                       
           
                                                 // Keep running while gap is more than 1 and last                       
                                                 // iteration caused a swap                       
                                                 while                                     (gap != 1 || swapped ==                                     true                                     )                       
                                                 {                       
                                                 // Find next gap                       
                                                 gap = getNextGap(gap);                       
           
                                                 // Initialize swapped as false so that we can                       
                                                 // check if swap happened or not                       
                                                 swapped =                                     false                                     ;                       
           
                                                 // Compare all elements with current gap                       
                                                 for                                     (                                     int                                     i=0; i<n-gap; i++)                       
                                                 {                       
                                                 if                                     (a[i] > a[i+gap])                       
                                                 {                       
                                                 swap(a[i], a[i+gap]);                       
                                                 swapped =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};                       
                                                 int                                     n =                                     sizeof                                     (a)/                                     sizeof                                     (a[0]);                       
           
                                                 combSort(a, n);                       
           
                                                 printf                                     (                                     "Sorted array: "                                     );                       
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 printf                                     (                                     "%d "                                     , a[i]);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program for implementation of Comb Sort                       
                         class                                     CombSort                       
                         {                       
                                                 // To find gap between elements                       
                                                 int                                     getNextGap(                                     int                                     gap)                       
                                                 {                       
                                                 // Shrink gap by Shrink factor                       
                                                 gap = (gap*                                     10                                     )/                                     13                                     ;                       
                                                 if                                     (gap <                                     1                                     )                       
                                                 return                                     1                                     ;                       
                                                 return                                     gap;                       
                                                 }                       
           
                                                 // Function to sort arr[] using Comb Sort                       
                                                 void                                     sort(                                     int                                     arr[])                       
                                                 {                       
                                                 int                                     n = arr.length;                       
           
                                                 // initialize gap                       
                                                 int                                     gap = n;                       
           
                                                 // Initialize swapped as true to make sure that                       
                                                 // loop runs                       
                                                 boolean                                     swapped =                                     true                                     ;                       
           
                                                 // Keep running while gap is more than 1 and last                       
                                                 // iteration caused a swap                       
                                                 while                                     (gap !=                                     1                                     || swapped ==                                     true                                     )                       
                                                 {                       
                                                 // Find next gap                       
                                                 gap = getNextGap(gap);                       
           
                                                 // Initialize swapped as false so that we can                       
                                                 // check if swap happened or not                       
                                                 swapped =                                     false                                     ;                       
           
                                                 // Compare all elements with current gap                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<n-gap; i++)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+gap])                       
                                                 {                       
                                                 // Swap arr[i] and arr[i+gap]                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[i+gap];                       
                                                 arr[i+gap] = temp;                       
           
                                                 // Set swapped                       
                                                 swapped =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 CombSort ob =                                     new                                     CombSort();                       
                                                 int                                     arr[] = {                                     8                                     ,                                     4                                     ,                                     1                                     ,                                     56                                     ,                                     3                                     , -                                     44                                     ,                                     23                                     , -                                     6                                     ,                                     28                                     ,                                     0                                     };                       
                                                 ob.sort(arr);                       
           
                                                 System.out.println(                                     "sorted array"                                     );                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<arr.length; ++i)                       
                                                 System.out.print(arr[i] +                                     " "                                     );                       
           
                                                 }                       
                         }                       
                         /* This code is contributed by Rajat Mishra */                       

Python3

                         # Python program for implementation of CombSort                       
           
                         # To find next gap from current                       
                         def                                     getNextGap(gap):                       
           
                                                 # Shrink gap by Shrink factor                       
                                                 gap                                     =                                     (gap                                     *                                     10                                     )                                     /                                     /                                     13                       
                                                 if                                     gap <                                     1                                     :                       
                                                 return                                     1                       
                                                 return                                     gap                       
           
                         # Function to sort arr[] using Comb Sort                       
                         def                                     combSort(arr):                       
                                                 n                                     =                                     len                                     (arr)                       
           
                                                 # Initialize gap                       
                                                 gap                                     =                                     n                       
           
                                                 # Initialize swapped as true to make sure that                       
                                                 # loop runs                       
                                                 swapped                                     =                                     True                       
           
                                                 # Keep running while gap is more than 1 and last                       
                                                 # iteration caused a swap                       
                                                 while                                     gap !                                     =                                     1                                     or                                     swapped                                     =                                     =                                     1                                     :                       
           
                                                 # Find next gap                       
                                                 gap                                     =                                     getNextGap(gap)                       
           
                                                 # Initialize swapped as false so that we can                       
                                                 # check if swap happened or not                       
                                                 swapped                                     =                                     False                       
           
                                                 # Compare all elements with current gap                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n                                     -                                     gap):                       
                                                 if                                     arr[i] > arr[i                                     +                                     gap]:                       
                                                 arr[i], arr[i                                     +                                     gap]                                     =                                     arr[i                                     +                                     gap], arr[i]                       
                                                 swapped                                     =                                     True                       
           
           
                         # Driver code to test above                       
                         arr                                     =                                     [                                     8                                     ,                                     4                                     ,                                     1                                     ,                                     3                                     ,                                     -                                     44                                     ,                                     23                                     ,                                     -                                     6                                     ,                                     28                                     ,                                     0                                     ]                       
                         combSort(arr)                       
           
                         print                                     (                                     "Sorted array:"                                     )                       
                         for                                     i                                     in                                     range                                     (                                     len                                     (arr)):                       
                                                 print                                     (arr[i],end                                     =                                     " "                                     )                       
           
           
                         # This code is contributed by Mohit Kumra                       

C#

                         // C# program for implementation of Comb Sort                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 // To find gap between elements                       
                                                 static                                     int                                     getNextGap(                                     int                                     gap)                       
                                                 {                       
                                                 // Shrink gap by Shrink factor                       
                                                 gap = (gap*10)/13;                       
                                                 if                                     (gap < 1)                       
                                                 return                                     1;                       
                                                 return                                     gap;                       
                                                 }                       
           
                                                 // Function to sort arr[] using Comb Sort                       
                                                 static                                     void                                     sort(                                     int                                     []arr)                       
                                                 {                       
                                                 int                                     n = arr.Length;                       
           
                                                 // initialize gap                       
                                                 int                                     gap = n;                       
           
                                                 // Initialize swapped as true to                       
                                                 // make sure that loop runs                       
                                                 bool                                     swapped =                                     true                                     ;                       
           
                                                 // Keep running while gap is more than                       
                                                 // 1 and last iteration caused a swap                       
                                                 while                                     (gap != 1 || swapped ==                                     true                                     )                       
                                                 {                       
                                                 // Find next gap                       
                                                 gap = getNextGap(gap);                       
           
                                                 // Initialize swapped as false so that we can                       
                                                 // check if swap happened or not                       
                                                 swapped =                                     false                                     ;                       
           
                                                 // Compare all elements with current gap                       
                                                 for                                     (                                     int                                     i=0; i<n-gap; i++)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+gap])                       
                                                 {                       
                                                 // Swap arr[i] and arr[i+gap]                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[i+gap];                       
                                                 arr[i+gap] = temp;                       
           
                                                 // Set swapped                       
                                                 swapped =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};                       
                                                 sort(arr);                       
           
                                                 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 implementation of Comb Sort                       
                                   
                                                 // To find gap between elements                       
                                                 function                                     getNextGap(gap)                       
                                                 {                       
                                                 // Shrink gap by Shrink factor                       
                                                 gap = parseInt((gap*10)/13, 10);                       
                                                 if                                     (gap < 1)                       
                                                 return                                     1;                       
                                                 return                                     gap;                       
                                                 }                       
                                   
                                                 // Function to sort arr[] using Comb Sort                       
                                                 function                                     sort(arr)                       
                                                 {                       
                                                 let n = arr.length;                       
                                   
                                                 // initialize gap                       
                                                 let gap = n;                       
                                   
                                                 // Initialize swapped as true to                       
                                                 // make sure that loop runs                       
                                                 let swapped =                                     true                                     ;                       
                                   
                                                 // Keep running while gap is more than                       
                                                 // 1 and last iteration caused a swap                       
                                                 while                                     (gap != 1 || swapped ==                                     true                                     )                       
                                                 {                       
                                                 // Find next gap                       
                                                 gap = getNextGap(gap);                       
                                   
                                                 // Initialize swapped as false so that we can                       
                                                 // check if swap happened or not                       
                                                 swapped =                                     false                                     ;                       
                                   
                                                 // Compare all elements with current gap                       
                                                 for                                     (let i=0; i<n-gap; i++)                       
                                                 {                       
                                                 if                                     (arr[i] > arr[i+gap])                       
                                                 {                       
                                                 // Swap arr[i] and arr[i+gap]                       
                                                 let temp = arr[i];                       
                                                 arr[i] = arr[i+gap];                       
                                                 arr[i+gap] = temp;                       
                                   
                                                 // Set swapped                       
                                                 swapped =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 let arr = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0];                       
                                                 sort(arr);                       
           
                                                 document.write(                                     "sorted array"                                     +                                     "</br>"                                     );                       
                                                 for                                     (let i=0; i<arr.length; ++i)                       
                                                 document.write(arr[i] +                                     " "                                     );                       
                                   
                                                 // This code is contributed by decode2207                       
                         </script>                       

输出：

Sorted array: -44 -6 0 1 3 4 8 23 28 56

插图： 让数组元素

8, 4, 1, 56, 3, -44, 23, -6, 28, 0

初始间隙值=10 收缩后间隙值=>10/1.3= 7. ;

 8 4 1 56 3 -44 23 -6 28 0-6 4 1 56 3 -44 23  8 28 0-6 4 0 56 3 -44 23  8 28 1

新差距值=>7/1.3= 5. ;

-44 4 0 56 3 -6 23 8 28 1-44 4 0 28 3 -6 23 8 56 1-44 4 0 28 1 -6 23 8 56 3

新差距值=>5/1.3= 3. ;

-44 1  0 28 4 -6 23 8 56 3-44 1 -6 28 4  0 23 8 56 3-44 1 -6 23 4  0 28 8 56 3-44 1 -6 23 4  0  3 8 56 28

新差距值=>3/1.3= 2. ;

-44 1 -6 0 4 23 3 8 56 28-44 1 -6 0 3 23 4 8 56 28-44 1 -6 0 3 8 4 23 56 28

新差距值=>2/1.3= 1. ;

-44 -6 1 0 3 8 4 23 56 28-44 -6 0 1 3 8 4 23 56 28-44 -6 0 1 3 4 8 23 56 28-44 -6 0 1 3 4 8 23 28 56 no more swaps required (Array sorted)

时间复杂性： 该算法的平均事例时间复杂度为Ω（N ^2. /2 ^P )，其中p是增量的数量。该算法的最坏情况复杂度为O（n） ^2. )最佳情况复杂度为O（nlogn）。 辅助空间： O（1）。

梳子排序测验

本文由 拉胡尔·阿格拉瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

快照：

scene00505 scene00577 scene00721 scene02305 scene02809 scene02881

GeekSforgeks/GeekSquick上的其他排序算法 选择排序 , 气泡排序 , 插入排序 , 合并排序 , 堆排序 , 快速排序 , 基数排序 , 计数排序 , 斗式分拣 , 贝壳类 , 鸽子洞排序如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章