ComboSort

Combosort是一个基于swap的排序, 和冒泡排序一样, 它改良了冒泡排序中只对相邻元素做比较然后swap的特点, 通过使用gap 表示两个数时间的index位置, 然后用gap除以一个经验定值1.3,获得当前比较的两个数的位置. gap从n一直减小到1, 然后完成排序.

#include <iostream>
using namespace std;


int findgap(int x)
{
    x = (x * 10) / 13;
    return max(1, x);
}
void combosort(int a[], int l, int r)
{
    int gap = r;
    bool swapped = true;
    while (gap != 1 || swapped)
    {
        gap = findgap(gap);
        swapped = false;
        for (int i = l; i < r - gap; i++)
        {
            if (a[i] > a[i + gap])
            {
                swap(a[i], a[i+gap]);
                swapped = true;
            }
            
        }
        
    }
}
void sort(int a[], int n)
{
   combosort(a, 0, n); 
}