Implementation of PHP Comb Sort algorithm

Comb sort or comb sort is a variant of Bubble sort . Similar to Shell sort, Comb Sort increases the gap used in comparisons and exchanges. Some implementations use insertion sort when the interval is less than a certain number. The basic idea is to eliminate small values ​​near the end of the list, since in bubble sort these will slow down the sort significantly. And large values ​​at the beginning of the list will not cause problems in bubble sort.

In bubble sort, when any two elements are compared, they always have a gap of 1. The basic idea of ​​comb sorting is that the gap can be much larger than 1.

PHP comb sorting diagram is as follows:

##The code example is as follows:

<?php
function combSort($my_array){
    $gap = count($my_array);
    $swap = true;
    while ($gap > 1 || $swap){
        if($gap > 1) $gap /= 1.25;
        $swap = false;
        $i = 0;
        while($i+$gap < count($my_array)){
            if($my_array[$i] > $my_array[$i+$gap]){
                list($my_array[$i], $my_array[$i+$gap]) = array($my_array[$i+$gap],$my_array[$i]);
                $swap = true;
            }
            $i++;
        }
    }
    return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 :\n";
echo implode(&#39;, &#39;,$test_array );
echo "\n排序后数组\n:";
echo implode(&#39;, &#39;,combSort($test_array)). PHP_EOL;

Output:

原始数组 : 3, 0, 2, 5, -1, 4, 1
排序后数组 :-1, 0, 1, 2, 3, 4, 5

This article is about the implementation method of PHP Comb Sort algorithm. I hope it will be helpful to friends in need!

The above is the detailed content of Implementation of PHP Comb Sort algorithm. For more information, please follow other related articles on the PHP Chinese website!