基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法

方法:最高位优先MSD、最低位优先LSD

思想:最低位优先LSD方案

1、  将待排数字根据个位上的数字进行排序

2、  将待第一步排序结果再按照十位上数字进行排序

3、  按照位数从低到高依次排序

示例:

 

$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
function getIndex($num, $index) {
    $val = pow(10, $index - 1);
    return ($num / $val) % 10;
}
function radix_sort($arr,$max_len) {
    for($i = 1; $i <= $max_len; $i++) {
        $temp = array_fill(0, 10, array());//填充桶
        foreach ($arr as $v) {
            echo $index = getIndex($v, $i);
            echo '#';
            $temp[$index][] = $v;
        }
        $arr = array();
        echo "\n第".$i. '次排序之后:';
        foreach ($temp as $v) {
            for($j =0 ;$j < count($v); $j++) {
                echo $v[$j] ."," ;
                $arr[] = $v[$j];
            }
        }
        echo "\n";
    }
    return $arr;
}
$arr = radix_sort($arr, 3);
print_r($arr);

 

以上示例有一个问题,如果排序的数字是负数呢?

$arr = array(1,4,5,89,22,44,-5,33,-6,7,-82,332);
function getIndex($num, $index) {
    $val = pow(10, $index - 1);
    return 10+($num / $val) % 10;
}
function radix_sort($arr,$max_len) {
    for($i = 1; $i <= $max_len; $i++) {
        $temp = array_fill(0, 19, array());//填充桶,负数填充-9~0~9对应0~10~19
        foreach ($arr as $v) {
            echo $index = getIndex($v, $i);
            echo '#';
            $temp[$index][] = $v;
        }
        $arr = array();
        echo "\n第".$i. '次排序之后:';
        foreach ($temp as $v) {
            for($j =0 ;$j < count($v); $j++) {
                echo $v[$j] ."," ;
                $arr[] = $v[$j];
            }
        }
        echo "\n";
    }
    return $arr;
}
$arr = radix_sort($arr, 3);
print_r($arr);

 

快速排序

思想:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
示例:

 1) {
        $temp = $arr[0];
        $x = $y = array();
        for($i = 1; $i < count($arr); $i++) {
            if($arr[$i] < $temp) {
                $x[] = $arr[$i];
            } else {
                $y[] = $arr[$i];
            }
        }
        $x = quick_sort($x);
        $y = quick_sort($y);
        return array_merge($x, array($temp),  $y);
    } else {
        return $arr;
    }
}
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$result = quick_sort($arr);
print_r($result);

最坏的情况下就是O(n2)

插入排序

原理:
1. 从第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到下一位置中
6. 重复步骤2~5

php
//从小到大排序
function insert_sort($arr){
    for($i = 1; $i < count($arr); $i++){
        $tmp=$arr[$i];
        $key=$i-1;
        while($key>=0 && $tmp < $arr[$key]){
            $arr[$key+1]=$arr[$key];
            $key--;
        }
        if($key+1 != $i)
            $arr[$key+1]=$tmp;
        }
        return $arr;
}
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$result = insert_sort($arr);
print_r($result);

 

选择排序

分类:

选择排序(选择排序,堆排序,平滑排序,笛卡尔树排序,锦标赛排序,圈排序)

思想:

1、从左至右遍历,找到最小(大)的元素,然后与第一个元素交换。

2、从剩余未排序元素中继续寻找最小(大)元素,然后与第二个元素进行交换。

3、以此类推,直到所有元素均排序完毕。

示例:

 

php 
function select_sort($array){
    $count=count($array);
    for($i=0;$i<$count-1;$i++){
        $min=$i;
        for($j=$i+1;$j<$count;$j++){
            if($array[$min]>$array[$j]){
                $min=$j;
            }
        }
        if($min!=$i){
            $temp=$array[$min];
            $array[$min]=$array[$i];
            $array[$i]=$temp;
        }
    }
    return $array;
}
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$result = select_sort($arr);
print_r($result);

 

冒泡排序

原理:
1、比较相邻的元素。如果第一个比第二个大(小),就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大(小)的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
分析:
最好的时间复杂度为O(n),最坏的时间复杂度为O(n2)
稳定性:
属于稳定性排序

Continue reading

桶排序

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)
思想:
设待排序序列的元素取值范围为0到m,则我们新建一个大小为m+1的临时数组并把初始值都设为0,遍历待排序序列,把待排序序列中元素的值作为临时数组的下标,找出临时数组中对应该下标的元素使之+1;然后遍历临时数组,把临时数组中元素大于0的下标作为值按次序依次填入待排序数组,元素的值作为重复填入该下标的次数,遍历完成则排序结束序列有序。
示例:

 $v){
    for($i = 0; $i < $v; $i++) {
        echo $k;
    }
}

 
应用大量数据排序
比如9亿不重复的9位数字排序,可以初始化10亿个bit来标示存在这个数字是否存在,如果该位是1就输出该位整数

经典笔试题目[算法篇]

php 
/**
 * 两个已经按照从大到小排序的数组,元素个数不确定
 * 仅使用一次循环,找出其中相等元素并输出(使用空格分开)
*/
$a = array(123,110,100,98,76,56,44,23,12);
$b = array(123,100,98,56,44,33,22,11);
$bNum = count($b);//计算b的个数
$aNum = count($a);//计算a的个数
$i = $j = 0;
while ($i < $aNum && $j < $bNum) {
   if ($a[$i] < $b[$j]) { 
       ++$j;    
    } else if ($a[$i] == $b[$j]) { 
       echo $a[$i]." ";        
       $i++;        
       $j++;    
    } else {        
        ++$i;    
    }  
} 
?>

方案二:

 $v) {
    if ($v == 2) {
        echo $k.' ';
    }
}
?>

算法,需要不停的积累,日复一日,年复一年!

蛇形矩阵

<?php
/*
* 蛇形矩阵一
*/
$n = 5;
//填充数组,array_fill第一个参数是起始下标,第二个是总个数,第三个是元素
$arr = array_fill(0, $n, array_fill(0, $n, 0));
$x = 0;
$y = $n – 1;
$p = $arr[$x][$y] = 1;//开始位置
//向下,向左,向上,向右(注意范围)
while($p < $n * $n) {
while($x + 1 < $n && $arr[$x+1][$y] == 0) {
++$x;
$arr[$x][$y] = ++$p;
}
while($y – 1 >= 0 && $arr[$x][$y-1] == 0) {
–$y;
$arr[$x][$y] = ++$p;
}
while($x – 1 >= 0 && $arr[$x-1][$y] == 0) {
–$x;
$arr[$x][$y] = ++$p;
}
while($y + 1 < $n && $arr[$x][$y+1] == 0) {
++$y;
$arr[$x][$y] = ++$p;
}
}
for ($i = 0;$i < $n;$i++) {
for($j = 0; $j < $n;$j++) {
echo $arr[$i][$j].” “;
}
echo “<br>”;
}
?>

输出结构是:

13 14 15 16 1
12 23 24 17 2
11 22 25 18 3
10 21 20 19 4
9 8 7 6 5

今天看书看到的,就写出来。今天又加强学习了array_fill数组填充函数

开灯问题

<?php

/*

* 开灯问题

* 描述:

* n盏灯,编号为1——n,第一个人把所有的灯打开,第二个人会按下所有编号为2的倍数的开关

* 这样本来开着的灯会关上,第三个人会按下3的倍数的开关,那么关的灯会打开,开的灯会

* 关掉,依次类推,问最后开着的灯的编号是?(k<=n<=1000)

*/

$n = 100;

$k = 10;

//第一个参数是开始的索引,第二个是填充个数,第三个是填充的元素值

$deng = array_fill(1, $n, 0);

for ($i = 1;$i <= $k;$i++) {

for ($j = 1;$j <= $n;$j++) {

if ($j % $i == 0) {

$deng[$j] = !$deng[$j];

}

}

}

for ($i = 1;$i <= $n; $i++) {

if($deng[$i]) {

echo $i.” “;

}

}

?>

这样不论如何变换都可以知道结果了,比如:关着的编号是?刚开始灯是开着的,然后求关着和开着的呢???是不是很有意思呢?