php常用排序算法

排序的几个要点

  1. 什么叫做排序?
  2. 内排序和外排序
  3. 什么是稳定的排序算法?
  4. 正序和逆序比较次数是一样的
  5. 评价排序算法的标准有:执行时间所需的辅助空间,其次是算法的稳定性

冒泡排序

例:设有关键字序列为:23, 38, 22, 45, 23, 67, 31, 15, 41,冒泡排序的过程如下:
冒泡排序

function bubbleSort($numbers){
    $cnt=count($numbers);
    for($i=0;$i<$cnt-1;$i++){//循环比较
        for($j=0;$j<$cnt-1-$i;$j++){
            if($numbers[$j]>$numbers[$j+1]){//执行交换
                $temp=$numbers[$j+1];
                $numbers[$j+1]=$numbers[$j];
                $numbers[$j]=$temp;
            }
        }
    }
    return$numbers;
}
$list = array(39, 38, 22, 45, 23, 67, 31, 15, 41);
$newlist = bubbleSort($list);
print_r($newlist);

另外一种冒泡,使用递归的实现方式

function bubble($num){
    global $list,$count;
    if($num < $count){
        for ($i=0; $i < $count-1 ; $i++) { 
            if($list[$i] > $list[$i+1] ){
                $tem = $list[$i];
                $list[$i] = $list[$i+1];
                $list[$i+1] = $tem;
            }   
        }
        $num++;
        bubble($num);
    }   
}
$count = count($list);
$num = 0;
$list = array(39, 38, 22, 45, 23, 67, 31, 15, 41);
bubble($num);
print_r($list);

快速排序

排序思想:通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,再分别对这两部分记录进行下一趟排序,以达到整个序列有序。

快速排序就是比较适合用递归来处理的。

function quicksort($arr) {
    if (count($arr) > 1) {
        $k = $arr[0];
        $x = array();
        $y = array();
        $size = count($arr);
        for ($i = 1; $i < $size; $i++) {
            if ($arr[$i] <= $k) {
                $x[] = $arr[$i];
            } else {
                $y[] = $arr[$i];
            }
        }
        $x = quicksort($x);
        $y = quicksort($y);
        return array_merge($x, array($k), $y);
    } else {
        return $arr;
    }
}

$list = array(10, 3, 5, 7, 11, 45, 64, 74, 23, 21, 6);
$result = quicksort($list);
print_r($result);

简单选择排序

排序思想:设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小的记录,与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。

例:设有关键字序列为:7, 4, -2, 19, 13, 6,简单选择排序的过程如下图:
简单选择排序

function selectsort($numbers){
    $cnt=count($numbers);
    for($i=0;$i<$cnt-1;$i++){//循环比较
        for($j=$i+1;$j<$cnt;$j++){
            if($numbers[$j]<$numbers[$i]){//执行交换
                $temp=$numbers[$i];
                $numbers[$i]=$numbers[$j];
                $numbers[$j]=$temp;
            }
        }
    }
    return$numbers;
}
$list = array(10,3,5,7,18,11,45,64,74,23,21,6);
$list = selectsort($list);
print_r($list);

直接插入排序

排序思想:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

例:设有关键字序列为:7, 4, -2, 19, 13, 6,直接插入排序的过程如下所示:
直接插入排序

function insertSort($arr1) {
    $count = count($arr1);
    for ($i = 1; $i < $count; $i++) {
        $tmp = $arr1[$i];
        $j = $i - 1;
        while ($j >= 0 && $tmp < $arr1[$j]) {
            $arr1[$j + 1] = $arr1[$j];
            $j--;
        }
        $arr1[$j + 1] = $tmp;
    }
    return $arr1;
}

$list = array(10, 3, 5, 7, 18, 11, 45, 64, 74, 23, 21, 6);
$list = insertSort($list);
print_r($list);