基数排序

基数排序(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);

 

奇偶排序

原理

奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对,a[j]和a[j+1],j是奇数(j=1, 3, 5……)。如果它们的关键字的值次序颠倒,就交换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=2, 4,6……)。重复进行这样两趟的排序直到数组全部有序。

示例

php
//奇偶排序
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$sort = true;
while ($sort) {
    $sort = false;
    for($i = 0; $i<$num;$i+=2) {
        if($arr[$i] > $arr[$i+1]) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$i+1];
            $arr[$i + 1] = $temp;
            $sort = true;
        }
    }
    for($j=1; $j<$num-1;$j+=2) {
        if($arr[$j] > $arr[$j + 1]) {
            $temp = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j + 1] = $temp;
            $sort = true;
        }
    }
    if(!$sort) {
        break;
    }
 
}
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、一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

分析:随着模块n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高

2、在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出 T(n) 的同数量级(它的同数量级有以下:1,log2n,n,n log2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n) = 该数量级,若 T(n)/f(n) 求极限可得到一常数c,则时间复杂度T(n) = O(f(n))

例:算法:

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

{

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

{

A=123;//该步骤属于基本操作执行次数:n的平方次

for(k=1; k<=n; ++k)

A++;//该步骤属于基本操作执行次数:n的三次方次

}

}

则有 T(n) = n 的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级

则有 f(n) = n的三次方,然后根据 T(n)/f(n) 求极限可得到常数c

则该算法的时间复杂度:T(n) = O(n3) 注:n3即是n的3次方。

时间复杂度分类
1 < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! (1是一个常量)。

算法效率依次降低

时间复杂度为log2n例子

$a = 1;

$n = 1000;

while($a < $n) {

    $a*=2;

    echo $a;

}

 计算时间复杂度

     1.去掉运行时间中的所有加法常数。

     2.只保留最高阶项。

     3.如果最高阶项存在且不是1,去掉与这个最高阶相乘的常数得到时间复杂度

排序法

最差时间分析

平均时间复杂度

稳定度

空间复杂度

冒泡排序

O(n2)

O(n2)

稳定

O(1)

快速排序

O(n2)

O(n*log2n)

不稳定

O(log2n)~O(n)

选择排序

O(n2)

O(n2)

稳定

O(1)

二叉树排序

O(n2)

O(n*log2n)

不稳定

O(n)

插入排序

O(n2)

O(n2)

稳定

O(1)

堆排序

O(n*log2n)

O(n*log2n)

不稳定

O(1)

 

空间复杂度

算法程序所占用的空间

输入的数据所占存储空间

执行过程所需额外空间

冒泡排序

原理:
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就输出该位整数

【算法】猴子大王

一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去…,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。

$s = 0;
$n = isset($_GET['n']) ?  $_GET['n'] : 9;
$m = isset($_GET['m']) ?  $_GET['m'] : 2;
for($i=1;$i<=$n;$i++) {
	$s = ($s+$m)%$i;
}
echo $s+1;

参考:[百科]