奇偶排序

原理

奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对,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就输出该位整数

Sed详解

1、说明
sed 一种在线编辑器,它一次处理一行内容。处理时,把当前处理的行存储在临时缓冲区中,称为“模式空间”(pattern space),接着用sed命令处理缓冲区中的内容,处理完成后,把缓冲区的内容送往屏幕。接着处理下一行,这样不断重复,直到文件末尾。文件内容并没有改变,除非你使用重定向存储输出。Sed主要用来自动编辑一个或多个文件;简化对文件的反复操作;编写转换程序等。
2、用法
sed:
用法: sed [选项]... {脚本(如果没有其他脚本)} [输入文件]...

  -n, --quiet, --silent
                 取消自动打印模式空间
  -e 脚本, --expression=脚本
                 添加“脚本”到程序的运行列表
  -f 脚本文件, --file=脚本文件
                 添加“脚本文件”到程序的运行列表
  --follow-symlinks
                 直接修改文件时跟随软链接
  -i[SUFFIX], --in-place[=SUFFIX]
                 edit files in place (makes backup if SUFFIX supplied)
  -l N, --line-length=N
                 指定“l”命令的换行期望长度
  --posix
                 关闭所有 GNU 扩展
  -r, --regexp-extended
                 在脚本中使用扩展正则表达式
  -s, --separate
                 将输入文件视为各个独立的文件而不是一个长的连续输入
  -u, --unbuffered
                 从输入文件读取最少的数据,更频繁的刷新输出
  -z, --null-data
                 separate lines by NUL characters
      --help     打印帮助并退出
      --version  输出版本信息并退出
示例:sed '2,5d' 
其中2,5表示2-5行(包含);d表示删除
a新增
c取代
d删除
i插入
p列印
s取代,通常搭配正则使用
举个栗子
sed '3,$d'					删除第三行到最后一行,$标示最后一行
sed '2a 这是追加的内容'		在第二行后追加内容
sed '2i 这是插入的内容'		在第二行前插入内容
sed '2c 这是替换后的内容'	替换第2~5行内容
sed '2-5p'					打印第2~5行内容
sed  -n '/root/p'			打印包含有root的行
/sbin/ifconfig eth0 |grep 'inet 地址'| sed 's/^.*地址://g' | sed 's/广播.*$//g'
等同于
/sbin/ifconfig eth0 |grep 'inet 地址'| sed -e 's/^.*地址://g' -e 's/广播.*$//g'
备注:/sbin/ifconfig eth0 |grep 'inet addr'| sed -e 's/^.*addr://g' -e 's/Bcast.*$//g'
3、实战案例-替换安卓AndroidManifest.xml配置项
echo ' '|sed -e 's#name=".*"#name="123456"#g'
备注:s后面跟着的是匹配符可以为/或者?或者#,g是全部替换

 

AWK第二课

1、工作原理
例子:
cat /etc/passwd |awk -F ‘:’ ‘BEGIN {print “name”} {print $1} END {print “Joyous”}’
说明:
awk是先执行BEGIN,然后去读文件,一行一行读取,-F指定了每行按照:分割,其中$0标示当前行,$1标示分割第一个区域,$n标示第n个区域。一直到读取完毕,最后执行END
2、正则匹配
awk -F: ‘/^root/{print $1}’ /etc/passwd
说明:搜索root开头的行打印第一个区域
3、内置变量
ARGC 命令行参数个数
ARGV 命令行参数排列
ENVIRON 支持队列中系统环境变量的使用
FILENAME awk浏览的文件名
FNR 浏览文件的记录数
FS 设置输入域分隔符,等价于命令行 -F选项
NF 浏览记录的域的个数
NR 已读的记录数
OFS 输出域分隔符
ORS 输出记录分隔符
RS 控制记录分隔符
示例:
awk -F’:’ ‘{print “filename:” FILENAME “,line:” NR “,cols:” NF}’ /etc/passwd
4、printf格式化输出
awk -F ‘:’ ‘{printf(“filename:%s,linenumber:%s,columns:%s,linecontent:%s\n”,FILENAME,NR,NF,$0)}’ /etc/passwd
5、编程
定义变量可以在action块定义,语句使用;分开
awk ‘BEGIN {count=0;} {count++; print $0;} END{print “user count is “, count}’ /etc/passwd
条件语句if(){}else{}
6、函数
length(string)返回字符串的长度
index(string,find)返回子字符串在父字符串位置
tolower(string)将所有字符都转成小写
toupper(string)将所有字符都转成大写
substr(string,strat,length)截取字符串
match(string,ereg)支持正则匹配
sub(reg,rep,string)替换匹配的第一个字符序列
gsub(reg,rep,string)替换匹配的全部字符序列
split(string,arr,char)分割字符

参考:
http://www.gnu.org/software/gawk/manual/gawk.html

Ubuntu安装JDK

sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java7-installer
sudo apt-get install oracle-java7-set-default
查看版本
java -version
java version “1.7.0_80”
Java(TM) SE Runtime Environment (build 1.7.0_80-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.80-b11, mixed mode)
设置jdk
vi /etc/profile
export JAVA_HOME=/usr/lib/jvm/java-7-oracle
export JRE_HOME=${JAVA_HOME}/jre
export CLASSPATH=.:${JAVA_HOME}/lib:${JRE_HOME}/lib
export PATH=${JAVA_HOME}/bin:$PATH