PHP的怎样实现快速排序法和冒泡排序法呀?

推荐图书

  • O'Reilly:Head First PHP & MySQL(中文版)


1个回答

<?php 
header('content-type:text/html; charset=utf-8');
//示例数组
$arr = array(125,15,138,8,46,85,92,100,14,114,325,8,125,100);

//----------------------------------快速排序算法------------------------------------------
/**
* 快速排序算法
* ============================================================
* @todo 原理:
* 1、选择一个中枢元素(有很多选法,我的实现里使用第一个元素为中枢)
* 2、以该中枢元素为基准点,将小于中枢的元素放在中枢后集合的前部分,比它大的在集合后部分,待集合基本排序完成后(此时前部分元素小于后部分元素),把中枢元素放在合适的位置。
* 3、根据中枢元素最后确定的位置,把数组分成三部分,左边的,右边的,枢纽元素自己,对左边的,右边的分别递归调用快速排序算法即可。
* ============================================================
*/
/**
* 快速排序算法1-----(第二步用的冒泡)
*/
function quick_sort_1($arr)
{
    if (count($arr) <= 1) return $arr;
    $ckey = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for ($i=1;$i<count($arr);$i++){
        if ($arr[$i] < $ckey){
            $left_arr[] = $arr[$i];
        }else {
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quick_sort_1($left_arr);
    $right_arr = quick_sort_1($right_arr);
    return array_merge((array)$left_arr, (array)$ckey, (array)$right_arr);
}
echo '<pre>';
echo '[-----------------快速排序算法--------------]<br>';
print_r(quick_sort_1($arr));
echo '</pre>';


//----------------------------------冒泡排序算法------------------------------------------
/**
* 冒泡排序算法
* ============================================================
* @todo 原理:
* 依次比较相邻的两个数,将小数放在前面,大数放在后面。
* 第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。
* 第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。
* 如此下去,重复以上过程,直至最终完成排序。 
* @todo 实现方法:
* 用二重循环实现,外循环变量设为i,内循环变量设为j。
* 外循环重复9次,内循环依次重复8,7...,1次。
* 每次进行比较的两个元素都是与内循环j有关的,它们可以分别用a[j]和a[j+1]标识,i的值依次为1,2,...,9,对于每一个i, j的值依次为1,2,...10-i。 
* ============================================================
*/
function bubble_sort($arr)
{
    $count = count($arr);
    if ($count <= 1) return $arr;
    for ($i=0;$i<$count;$i++){
        for ($j=0;$j<$count-1-$i;$j++){
            if ($arr[$j] > $arr[$j+1]){
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
        }
    }
    return $arr;
}
echo '<pre>';
echo '[-----------------冒泡排序算法--------------]<br>';
print_r(bubble_sort($arr));
echo '</pre>';