<?php

/**
 * PHP排序算法Demo
 */

/**
 * [bubble_sort 冒泡排序]
 * @param  [array] $data [需要排序的数据（相邻的数据进行比较调换位置）]
 * @return [array]       [排序好的数据]
 */
function bubble_sort($data)
{
    if(!empty($data) && is_array($data))
    {
        $len = count($data);
        for($i=0; $i<$len; $i++)
        {
            for($k=0; $k<$len-1; $k++)
            {
                if($data[$k] > $data[$i])
                {
                    $data[$i] = $data[$i] ^ $data[$k];
                    $data[$k] = $data[$i] ^ $data[$k];
                    $data[$i] = $data[$i] ^ $data[$k];
                }
            }
        }
    }
    return $data;
}

/**
 * [select_sort 选择排序]
 * @param  [array] $data [需要排序的数据（选择最小的值与第一个调换位置）]
 * @return [array]       [排序好的数据]
 */
function select_sort($data)
{
    if(!empty($data) && is_array($data))
    {
        $len = count($data);
        for($i=0; $i<$len; $i++)
        {
            $t = $i;
            for($j=$i+1; $j<$len; $j++)
            {
                if($data[$t] > $data[$j])
                {
                    $t = $j;
                }
            }
            if($t != $i)
            {
                $data[$i] = $data[$i] ^ $data[$t];
                $data[$t] = $data[$i] ^ $data[$t];
                $data[$i] = $data[$i] ^ $data[$t];
            }
        }
    }
    return $data;
}

/**
 * [insert_sort 插入排序]
 * @param  [array] $data [需要排序的数据（把第n个数插到前面的有序数组中，以此反复循环直到排序好）]
 * @return [array]       [排序好的数据]
 */
function insert_sort($data)
{
    if(!empty($data) && is_array($data))
    {
        $len = count($data);
        for($i=1; $i<$len; $i++)
        {
            $tmp = $data[$i];
            for($j=$i-1; $j>=0; $j--)
            {
                if($data[$j] > $tmp)
                {
                    $data[$j+1] = $data[$j];
                    $data[$j]   = $tmp;
                } else {
                    break;
                }
            }
        }
    }
    return $data;
}

/**
 * [quick_sort 快速排序]
 * @param  [array] $data [需要排序的数据（选择一个基准元素，将待排序分成小和打两罐部分，以此类推递归的排序划分两罐部分）]
 * @return [array]       [排序好的数据]
 */
function quick_sort($data)
{
    if(!empty($data) && is_array($data))
    {
        $len = count($data);
        if($len <= 1) return $data;

        $base = $data[0];
        $left_array = array();
        $right_array = array();
        for($i=1; $i<$len; $i++)
        {
            if($base > $data[$i])
            {
                $left_array[] = $data[$i];
            } else {
                $right_array[] = $data[$i];
            }
        }
        if(!empty($left_array)) $left_array = quick_sort($left_array);
        if(!empty($right_array)) $right_array = quick_sort($right_array);

        return array_merge($left_array, array($base), $right_array);
    }
}

/**
 * 测试
 */
$data = array(10, 3, 6, 1, 24, 18, 7, 8);
echo '<pre>';

// 冒泡排序
print_r(bubble_sort($data));

// 选择排序
print_r(select_sort($data));

// 插入排序
print_r(insert_sort($data));

// 快速排序
print_r(quick_sort($data));

// 以下是结果
Array
(
    [0] => 1
    [1] => 3
    [2] => 6
    [3] => 7
    [4] => 8
    [5] => 10
    [6] => 18
    [7] => 24
)
Array
(
    [0] => 1
    [1] => 3
    [2] => 6
    [3] => 7
    [4] => 8
    [5] => 10
    [6] => 18
    [7] => 24
)
Array
(
    [0] => 1
    [1] => 3
    [2] => 6
    [3] => 7
    [4] => 8
    [5] => 10
    [6] => 18
    [7] => 24
)
Array
(
    [0] => 1
    [1] => 3
    [2] => 6
    [3] => 7
    [4] => 8
    [5] => 10
    [6] => 18
    [7] => 24
)

?>