这篇文章上次修改于 339 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

冒泡排序

• 1、比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
• 3、排除最大的数，接着下一轮继续相同的操作，确定第二大的数...
• 4、重复步骤1-3，直到排序完成。

function bubbleSort( $data ){

    if( count($data) <= 1){
        return $data;
    }

    $len = count($data);
    for( $i =0; $i < $len-1; $i++ ){
        for($j=0; $j < $len - $i - 1; $j++){
            if($data[$j] > $data[$j+1]){
                $tmp = $data[$j];
                $data[$j] = $data[$j+1];
                $data[$j+1] = $tmp;
            }
        }
    }

    return  $data;
}

//测试
$ar = [10,2,15,13,8,9,7,5];
print_r(bubbleSort($ar));

插入排序

• 1、从第一个元素开始，该元素可以认为已经被排序；
• 2、取出下一个元素，在前面已排序的元素序列中，从后向前扫描；
• 3、如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 5、将新元素插入到该位置后；
• 6、重复步骤2~5。

//插入排序
function insertSort( $data ){
    if( count($data) <= 1){
        return $data;
    }

    $len = count($data) - 1;
    for( $i=0; $i < $len; $i++){
        $nowValue = $data[$i+1]; //15
        $preKey = $i; //1
        while ($preKey >= 0 && $nowValue < $data[$preKey]){
            $data[$preKey+1] = $data[$preKey];
            $preKey--;
        }
        $data[$preKey+1] = $nowValue;
    }

    return $data;
}


$ar = [10,2,15,13,8,9,7,5];
print_r(insertSort($ar));

选择排序

• 1、第一轮，找到最小的元素，和数组第一个数交换位置。
• 2、第二轮，找到第二小的元素，和数组第二个数交换位置...
• 3、直到最后一个元素，排序完成。

//选择排序
function selectSort($data){
    if( count($data) <= 1){
        return $data;
    }

    $len = count($data) - 1;

    $minKey = 0;

    for( $i = 0; $i <= $len; $i++ ){
        for( $j = $i; $j <= $len; $j++ ){
            if( $data[$j] < $data[$minKey] ){
                $minKey = $j;
            }
        }
        if( $minKey != $i ){
            $tmp = $data[$i];
            $data[$i] = $data[$minKey];
            $data[$minKey] = $tmp;
        }

    }

    return  $data;
}

$ar = [10,2,15,13,8,9,7,5];
print_r(selectSort($ar));

快速排序

• 1.从数列中挑出一个元素（通常是第一个元素），称为"基准"（pivot），
• 2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
• 3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

function fastSort(&$data, $start, $end){
    if( count($data) <= 1){
        return $data;
    }
    if($start > $end){
        return  $data;
    }
    $posData = $data[$start];
    $left = $start;
    $right = $end;

    while ($left < $right){
        while ($left < $right ){
            if( $data[$right] > $posData ){
                $right--;
            }else{
                break;
            }
        }

        $data[$left] = $data[$right];

        while ($left < $right ){
            if( $data[$left] <= $posData ){
                $left++;
            }else{
                break;
            }
        }

        $data[$right] = $data[$left];

    }
    $data[$left] = $posData;
    fastSort($data, $start, $left-1);
    fastSort($data, $left+1, $end);
    return  $data;
}

$ar = [10,2,15,13,8,9,7,5];
print_r(fastSort($ar, 0, 7));

希尔排序

• 把数组分割成若干(h)个小组(一般数组长度length/2)，然后对每一个小组分别进行插入排序。每一轮分割的数组的个数逐步缩小，h/2->h/4->h/8，并且进行排序，保证有序。当h=1时，则数组排序完成。

//希尔排序
function shellSort($data){
    if( count($data) <= 1){
        return $data;
    }
    $len = count($data);
    $gap = floor($len/2);

    while ($gap > 0){
        for($i = $gap; $i < $len; $i++){
            $temp = $data[$i];
            $preKey = $i - $gap;
            while ($preKey >= 0 && $temp < $data[$preKey]){
                $data[$preKey + $gap] = $data[$preKey];
                $preKey -= $gap;
            }
            $data[$preKey+$gap] = $temp;
        }
        $gap /= 2;
    }

    return  $data;
}

$ar = [10,2,15,13,8,9,7,5];
print_r(shellSort($ar));