算法实现/排序/梳排序

Java

public static int[] sortArray(int[] arr){
		double shrinkFactor = 1.3;
		if(arr.length >0){
			double gap = (arr.length-1)/ shrinkFactor;
			
			while(gap>1){
				int i = 0;
				int j = (int) (i+ Math.floor(gap));
				while(j != arr.length){
					if(arr[i]> arr[j]){
						arr[i] = arr[i] ^ arr[j];
						arr[j] = arr[j] ^ arr[i];
						arr[i] = arr[i] ^ arr[j];						
					}
					i++;
					j++;
				}
				gap =gap/ shrinkFactor;
			}
		}
		return arr;
	}

C++

int newGap(int gap){
	gap /= 1.3;
	if(gap == 9 || gap == 10)
		gap = 11;
	if(gap < 1)
		return 1;
	return gap;
}
        
void combSort(int a[], int len){
	int gap = len;
	bool swapped;
	do{
		swapped = false;
		gap = newGap(gap);
		for(int i=0; i < len-gap; ++i){
			if(a[i] > a[i+gap]){
				swapped = true;
				swap(a[i], a[i+gap]);
			}
			if(a[i] == a[i+gap]){
				swapped = true;
			}
		}
	}while(gap > 1 || swapped);
}

C

void comb_sort(int *input, size_t size) {
    const float shrink = 1.3f;
    int swap;
    size_t i, gap = size;
    bool swapped = false;

    while ((gap > 1) || swapped) {
        if (gap > 1) {
            gap = (size_t)((float)gap / shrink);
        }

        swapped = false;

        for (i = 0; gap + i < size; ++i) {
            if (input[i] > input[i + gap]) {
                swap = input[i];
                input[i] = input[i + gap];
                input[i + gap] = swap;
                swapped = true;
            }
            if (input[i] == input[i + gap]) {
                swapped = true;
            }
        }
    }
}

梳排序 11

void comb_sort11(int *input, size_t size)
{ int i,j,top,tmp,switched=0,gap=size;
  if (7==gap) gap=8;  //optional line - improves single case
  while (1<gap || switched)
  {	if ((gap=(size_t)(gap*49L/64)) < 11)  // *49/64 approximates /1.3
  	  if (9<=gap) gap=11;
  	  else if (!gap) gap=1;
  	for (switched=0,	top=size-gap, i=0;i<top;++i)
  	{	j=i+gap;
		if (input[i]<input[j])
		{ tmp=input[i]; input[i]=input[j]; input[j]=tmp; switched=1; }	//swap
  }	}
}

梳排序 9

//comb_sort9 is a stripped combsort(tested OK for ALL permutations of size 0-9)
// in the applicable range, this sort has tiny code and excellent performance
//comparison/conditonal swaps approximate: 
// (n*n+n)/2-(-1.314286 - 0.7285714*n + 0.2142857*n*n) ;n=(size-1) 
//                                 (* = need to use full combsort11 for this)
// size                 2	3	4	5	6	7	8	9	10*	11*	12*   
// cmp/swap             1	3	6	9	14	19	24	29 36+n	42+n 49+n
// ceil(log2(size!))    1	3	5	7	10	13	16	19	22	26	29
//stripped combsort(tested OK for ALL permutations of size 0-9)
void comb_sort9(int *input, size_t size)
{	int i, j, tmp, top, gap=size;	
	assert(size<=9);	//ONLY for 9 entries or less
	if (7==gap) gap=8;  //important line - required for this case
	while (1<=(gap=(size_t)(gap*49L/64)))   // *49/64 approximates /1.3
	{	for (top=size-gap, i=0; i<top; ++i)
		{	j=i+gap;
			if (input[i]<input[j])
			{ tmp=input[i]; input[i]=input[j]; input[j]=tmp; }	//swap
	}	}	
}

Perl

sub comb_sort {
  my @v = @_;
  my $max = scalar (@v);
  my $gap = $max;
  while (1) {
     my $swapped = 0;
     $gap = int ($gap / 1.3);
     $gap = 11 if $gap == 10 or $gap == 9; # (optimization Combsort11)
     $gap = 1 if $gap < 1;
     my $lmax = $max - $gap - 1;
     foreach my $i (0..$lmax) {
          ($v[$i], $v[$i+$gap], $swapped) = ($v[$i+$gap], $v[$i], 1) if $v[$i] > $v[$i+$gap];
     }
     last if $gap == 1 and $swapped == 0;
  }
  return @v;
}

Phix

function comb_sort(sequence s)
integer gap = length(s)-1
    while 1 do
        gap = max(floor(gap/1.3),1)
        integer swapped = 0
        for i=1 to length(s)-gap do
            object si = s[i]
            if si>s[i+gap] then
                s[i] = s[i+gap]
                s[i+gap] = si
                swapped = 1
            end if
        end for
        if gap=1 and swapped=0 then exit end if
    end while
    return s
end function

Python

def update_gap(gap):
    gap = (gap * 10) / 13
    if gap == 9 or gap == 10:
        gap = 11
    return int(max(1, gap))

def combsort(x):
    gap = len(x)
    swapped = True
    if gap < 2:
        return
    while gap > 1 or swapped:
        gap = update_gap(gap)
        swapped = False
        for i in range(0, len(x) - gap):
            if x[i] > x[i + gap]:
                x[i], x[i + gap] = x[i + gap], x[i]
                swapped = True