梳排序(Comb sort)

       在泡沫排序中，只比较阵列中相邻的二项，即比较的二项的间距(Gap)是1，梳排序提出此间距其实可大于1，改自插入排序的希尔排序同样提出相同观点。梳排序中，开始时的间距设定为阵列长度，并在循环中以固定比率递减，通常递减率设定为1.3。在一次循环中，梳排序如同泡沫排序一样把阵列从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。如果间距递减至1，梳排序假定输入阵列大致排序好，并以泡沫排序作最后检查及修正。

假设待数组[8 4 3 7 6 5 2 1]

待排数组长度为8,而8÷1.3=6,则比较8和2,4和1,并做交换

[8 4 3 7 6 5 2 1]

[8 4 3 7 6 5 2 1]

交换后的结果为

[2 1 3 7 6 5 8 4]

第二次循环,更新间距为6÷1.3=4,比较2和6,1和5,3和8,7和4

[2 1 3 7 6 5 8 4]

[2 1 3 7 6 5 8 4]

[2 1 3 7 6 5 8 4]

[2 1 3 7 6 5 8 4]

只有7和4需要交换,交换后的结果为

[2 1 3 4 6 5 8 7]

第三次循环,更新距离为3,没有交换

第四次循环,更新距离为2,没有交换

第五次循环,更新距离为1,三处交换

[2 1 3 4 6 5 8 7]

[2 1 3 4 6 5 8 7]

[2 1 3 4 6 5 8 7]

三处交换后的结果为[1 2 3 4 5 6 7 8]

交换后排序结束,顺序输出即可得到[1 2 3 4 5 6 7 8]

#include <iostream>
#include <time.h>
using namespace std;

void combsort(int *arr, int size) 
{
 
  double shrink_factor = 1.247330950103979;
  int gap = size;
  int swapped = 1;
  int swap;
  int i;
 
  while ((gap > 1) || swapped) 
  {
    if (gap > 1) 
	{
		gap = gap / shrink_factor;
	}
 
    swapped = 0; 
    i = 0;
 
    while ((gap + i) < size) 
	{
      if(arr[i]-arr[i+gap] > 0) 
	  {
        swap = arr[i];
        arr[i] = arr[i+gap];
        arr[i+gap] = swap;
        swapped = 1;
      }
      ++i;
    }
  }
}


void print(int a[],int n)          
{          
    for(int i=0; i<n; i++)          
    {          
        cout<<a[i]<<" ";          
    }          
    cout << endl;          
}          
        
        
void main()          
{          
    int a[10];    
    srand((unsigned)time(NULL));//初始化随机数      
    
    for(int i=0; i<10; i++)    
    {    
        a[i]=rand()%20;    
    }    
    cout << "排序前：";          
    print(a,sizeof(a)/sizeof(a[0]));        
        
    int n=sizeof(a)/sizeof(a[0]);        
    combsort(a,n);     
        
    cout << "排序后：";       
    print(a,sizeof(a)/sizeof(a[0]));          
}      

递减率的设定影响着梳排序的效率，原作者以随机数作实验，得到最有效递减率为1.3的。如果此比率太小，则导致一循环中有过多的比较，如果比率太大，则未能有效消除阵列中的乌龟。亦有人提议用

混合梳排序和其他