冒泡排序是最被人熟知的排序算法。什么是冒泡排序？冒泡排序的特点是好邻居好说话，核心思想是一个每次比较两个相邻的元素，如果他们的大小顺序反了，就把他们交换过来。N个数就有N-1轮，每一轮把一个数字放在它正确的位置上。冒泡排序时间复杂度是O(N2)。C语言代码如下：

#include <stdio.h>

int main(){

    int i, j, num, score, tmp;

    printf("How many?\n");

    scanf("%d", &num);

    int rank[num];

    for(i=0; i<num; i++){

        printf("Enter Score:\n");

        scanf("%d", &score);

        //我们的试卷是0-100分的哦

        if(score<0 || score > 100){

            printf("Error");

            return 1;

        }

        rank[i] = score;

    }

    printf("Rank:\n");

    //冒泡排序

    for(i=0; i<num-1; i++){

        for(j=0; j<num-i; j++){

            if(rank[j] > rank[j+1]){

                tmp = rank[j];

                rank[j] = rank[j+1];

                rank[j+1] = tmp;

            }

        }

    }

    for(i=0; i<num; i++){

        printf("%d,", rank[i]);

    }

    return 0;

}

桶排序， 是最快最简单的排序。有多宽维度，就要申请多大的数组。比如100分的试卷，就要申请101个数组（试卷是0-100分），有人考了100分，就把array[100]加1，有人考了90，就把array[90]加1，有人考了70，就把array[70]+1，又有人考了90，就把array[90]加1，那么从高到底打印，如果是某个分数是0个人，就不打印，如果某个分数是1个人，就打印一次，如果某个分数是2个人，就打印两次，上面的例子就是100，90，90，90，70。

桶排序快是毋庸置疑的，但是，浪费了空间。比如打游戏，新手村里的小鸡攻击力是1，而最后一个副本的大BOSS的攻击力是999999999，那么就要对这个游戏的所有玩家和怪物的攻击力排序，就要申请一个1000000000长度的数组，就是array[1000000000]。假如每个字段的值都是1，1是整形，需要是4-8个字节（到底是4还是8取决于机器），那么这个数组就是1000000000/8/1024/1024=119MB。嗯哼？一个数组就要119M，你就是13年淘宝双11的160G内存的机器也拖不起吧。

桶排序的时间复杂度是O(M+N)，是最快的排序，它也是最简单的排序。

C语言代码：

#include <stdio.h>

int main(){

    int i, j, num, score, rank[100];

    for(i=0; i<101; i++){

        rank[i] = 0;

    }

    //需要录入多少个数据

    printf("How many?\n");

    scanf("%d", &num);

    for(i=0; i<num; i++){

        printf("Enter Score:\n");

        scanf("%d", &score);

        //我们的试卷是0-100分的哦

        if(score<0 || score > 100){

            printf("Error");

            return 1;

        }

        //进桶

        rank[score]++;

        score = 0;

    }

    printf("Rank:\n");

    //打印

    for(i=0; i<101; i++){

        for(j=0; j<rank[i]; j++){

            printf("%d,", i);

        }

    }

}

哈希表hashTable：哈希表hashTable是一种通过哈希函数，将特定的键映射到特定值的一种数据结构，它维护键和值之间一一对应关系。

    对于高级语言内核来讲，哈希表hashTable绝对是数据结构中的关键，很多高级语言是显示的支持哈希表hashTable的，哈希表hashTable的实践应用也非常广泛，编译器会维护一个符号表来保存标记，提供增删改查等操作。

    设计合理的哈希表hashTable的时间复杂度是O(1)，而最最糟糕的哈希表hashTable时间复杂度为O(n)，通常，它总是O(1)。而O(n)是因为，哈希表hashTable变成了一个链表。

    名词解释：

    1、键：操作数据的标识，例如PHP数组中的索引。

    2、槽：用于保存数据的坑。

    3、哈希映射函数：将键映射到数据应该存放的槽所在位置的函数。

    4、哈希冲突：哈希函数将两个不同的键映射到同一个索引的情况。

    哈希表hashTable可以理解为关联数组，数组使用键来寻址，如果键的范围较小且是数字的话， 我们可以直接使用数组来完成哈希表hashTable，而如果关键字范围太大，如果直接使用数组我们需要为所有可能的键申请空间。 很多情况下这是不现实的。即使空间足够，空间利用率也会很低，这并不理想。同时键也可能并不是数字， 在PHP中尤为如此，所以人们使用一种映射函数(哈希函数)来将键映射到特定的域中。

    通过合理设计的哈希函数，我们就能将键映射到合适的范围，因为我们的键空间可以很大(例如字符串键)， 在映射到一个较小的空间中时可能会出现两个不同的键映射被到同一个index上的情况， 这就是我们所说的出现了冲突。 目前解决哈希表hashTable冲突的方法主要有两种：链接法和开放寻址法。目前PHP中哈希冲突解决方法就是链接法。

    冲突解决 - 连接法：

    链接法通过使用一个链表来保存槽值的方式来解决冲突，也就是当不同的键映射到一个槽中的时候使用链表来保存这些值。 所以使用链接法是在最坏的情况下，也就是所有的键都映射到同一个槽中了，这样哈希表hashTable就退化成了一个链表， 这样的话操作链表的时间复杂度则成了O(n)，这样哈希表hashTable的性能优势就没有了， 所以选择一个合适的哈希函数是最为关键的。由于目前大部分的编程语言的哈希表hashTable实现都是开源的，大部分语言的哈希算法都是公开的算法， 虽然目前的哈希算法都能良好的将键进行比较均匀的分布，而这个假使的前提是键是随机的，正是由于算法的确定性， 这就导致了别有用心的黑客能利用已知算法的可确定性来构造一些特殊的键，让这些键都映射到 同一个槽位导致哈希表hashTable退化成单链表，导致程序的性能急剧下降，从而造成一些应用的吞吐能力急剧下降， 尤其是对于高并发的应用影响很大，通过大量类似的请求可以让服务器遭受DoS(服务拒绝攻击)， 这个问题一直就存在着，只是最近才被各个语言重视起来。哈希冲突攻击利用的哈希表hashTable最根本的弱点是：开源算法和哈希实现的确定性以及可预测性， 这样攻击者才可以利用特殊构造的键来进行攻击。要解决这个问题的方法则是让攻击者无法轻易构造 能够进行攻击的键序列。PHP采用的是一种治标不治本的做法: 限制用户提交数据字段数量。这样可以避免大部分的攻击，不过应用程序通常会有很多的数据输入方式，比如，SOAP，REST等等， 比如很多应用都会接受用户传入的JSON字符串，在执行json_decode()的时候也可能会遭受攻击。 所以最根本的解决方法是让哈希表hashTable的碰撞键序列无法轻易的构造，目前PHP中还没有引入不增加额外的复杂性情况下的完美解决方案。

    冲突解决 - 开放寻址法：

    通常还有另外一种解决冲突的方法：开放寻址法。使用开放寻址法是槽本身直接存放数据， 在插入数据时如果键所映射到的索引已经有数据了，这说明发生了冲突，这是会寻找下一个槽， 如果该槽也被占用了则继续寻找下一个槽，直到寻找到没有被占用的槽，在查找时也使用同样的策略来进行。由于开放寻址法处理冲突的时候占用的是其他槽位的空间,这可能会导致后续的键在插入的时候更加容易出现 哈希冲突，所以采用开放寻址法的哈希表hashTable的装载因子不能太高，否则容易出现性能下降。

相关内容：用PHP的实现一个高效的数据库（文件存储，NOSQL）  使用哈希表来构建自己的数据库 

一、我是新手我怕谁

    新手程序猿通常会直接存储明文密码在数据库中，好一点的会使用MD5来加密密码后存储md5(password)，再好一点的会sha1加密密码后存储sha1(password)。将常用的组合哈希后存入数据库，用来爆库，这个就是所谓的彩虹表。

二、加盐salted

    在密码中加入随机数字或字符，然后再进行哈希，看起来叼了很多，但是实际上对于现在计算机来说，即使简单的使用了盐和哈希的加密，短密码仍然会在非常短的情况下就会被破解出来。

三、美国标准

    美国政府的标准，已经用于政府和军方的系统。PBKDF2加密算法，全程是Password-Based Key Derivation Function。

    PBKDF2加密算法就是牺牲了时间来换取安全，一个明文的密码+随机的盐，然后哈希散列加密后存储起来，这是我们前面说的（二、加盐salted）。把这个过程重复100次，得到的结果存储起来。

    请注意，尽管我们说牺牲了时间，又说到了重复100次，那也是很快的，因为我们的普通服务器单次的运算都是在毫秒级。

四、scrypt

    scrypt是由著名的FreeBSD黑客 Colin Percival为他的备份服务 Tarsnap开发的。scrypt不仅计算所需时间长，而且占用的内存也多，使得并行计算多个摘要异常困难，因此利用彩虹表进行暴力攻击更加困难。scrypt没有在生产环境中大规模应用，并且缺乏仔细的审察和广泛的函数库支持。但是，scrypt在算法层面只要没有破绽，它的安全性应该高于PBKDF2。

五、请使用bcrypt！请使用bcrypt！请使用bcrypt！

    bcrypt是跨平台的、专门为密码存储而设计的算法，bcrypt所接受的密码长度必须是8至56个字符，并将在内部被转化为448位的密钥。基于Blowfish加密算法变形而来。

    bcrypt在默认情况下，在删除数据之前将使用随机数据三次覆盖原始输入文件，以阻挠可能会获得数据的人恢复数据的尝试。如果您不想使用此功能，可设定禁用此功能

　 　bcrypt最大的好处是有一个参数，可用于调整计算强度，而且该参数是包括在输出的摘要中的。随着计算能力的提高，应该可以逐步增大这个参数，增大这个参数后并不会影响原来的用户。

 　　bcrypt经过了很多安全专家的仔细分析，使用在以安全著称的OpenBSD中，一般认为它比PBKDF2更能承受随着计算能力加强而带来的风险。

    CoreSeek安装比较麻烦，官方手册对此的支持并不算很好。CoreSeek是基于Sphinx的中文的分词和全文检索软件。本文是在MAC OS X系统下安装和调试CoreSeek。

    安装过程中报错如果是警告warning则忽略，如果是错误error，则必须要处理。

    CoreSeek是支持三种数据来源的，一种是众所周知的Mysql，一种是XML文件，另一种是Python。而Python则是万能数据类型。在本CoreSeek安装测试教程中只示例数据源是XML文件和MYSQL。

    官方手册地址：http://www.coreseek.cn/products-install/install_on_macosx

    一、设置环境变量

$ export PATH=/usr/local/bin:$PATH

$ export LC_ALL=zh_CN.UTF-8

$ export.UTF-8

    二、安装依赖库：m4、autoconf、automake、libtool。

注意：不要brew install 来安装，因为对安装的库的版本有要求。

$ curl -O -L http://mirrors.kernel.org/gnu/m4/m4-1.4.13.tar.gz

$ tar -xzvf m4-1.4.13.tar.gz

$ cd m4-1.4.13

$ sudo ./configure --prefix=/usr/local/opt

$ sudo make

$ sudo make install

$ cd ..

$ curl -O -L http://mirrors.kernel.org/gnu/autoconf/autoconf-2.65.tar.gz

$ tar -xzvf autoconf-2.65.tar.gz

$ cd autoconf-2.65

$ sudo ./configure --prefix=/usr/local/opt

$ sudo make

$ sudo make install

$ cd ..

$ curl -O -L http://mirrors.kernel.org/gnu/automake/automake-1.11.tar.gz

$ tar xzvf automake-1.11.tar.gz

$ cd automake-1.11

$ ./configure --prefix=/usr/local/opt

$ sudo make

$ sudo make install

$ cd ..

$ curl -O -L http://mirrors.kernel.org/gnu/libtool/libtool-2.2.6b.tar.gz

$ tar xzvf libtool-2.2.6b.tar.gz

$ cd libtool-2.2.6b

$ sudo ./configure --prefix=/usr/local/opt

$ sudo make

$ sudo make install

$ cd ..

    三、安装Mysql。

1、mysql 的安装自行安装

2、查找mysql头文件地址和库文件地址。我用

brew install mysql

安装的Mysql，头文件地址和库文件地址分别是/usr/local/Cellar/mysql/5.6.17_1/include/mysql 和 /usr/local/Cellar/mysql/5.6.17_1/lib。

头文件地址就是mysql.h所在的目录，库文件地址就是libmysqlclient.a所在的目录。

    四、下载Coreseek。

$ curl -O -L http://www.coreseek.cn/uploads/csft/3.2/coreseek-3.2.14.tar.gz

$ tar xzvf coreseek-3.2.14.tar.gz

$ cd coreseek-3.2.14

在coreseek-3.2.14文件夹下有mmseg和csft和testpack。mmseg是分词服务，csft是CoreSeek的核心服务，testpack是测试用例。

    五、安装mmseg

$ cd mmseg-3.2.14

$ sudo ./bootstrap

$ sudo ./configure --prefix=/usr/local/opt/mmseg3

$ sudo make

$ sudo make install

$ cd ..

在make的时候，可能会报错，如下

file included from css/ThesaurusDict.cpp:6:

../src/css/ThesaurusDict.h:12:17: error: expected namespace name

using namespace __gnu_cxx;

^

css/ThesaurusDict.cpp:79:15: warning: result of comparison against a string

literal is unspecified (use strncmp instead) [-Wstring-compare]

if (filename == "-") {

    ^ ~~~

    css/ThesaurusDict.cpp:116:15: warning: result of comparison against a string

literal is unspecified (use strncmp instead) [-Wstring-compare]

if (filename != "-") {

    ^ ~~~

    2 warnings and 1 error generated.

    make[2] : *** [ThesaurusDict.lo] Error 1

make[1]: *** [install-recursive] Error 1

这个时候make进程已经终止。原因是因为编译器版本太高导致的，修改方法：1是降低编译器版本，反正我打死也不愿意。方法2如下：

vim src/css/ThesaurusDict.h

###在头部找到：#include <string>

###再其下加入一行代码：

#include <ext/hash_map>

修改完后保存退出，继续重新sudo make一下，就没有error级错误了，然后sudo make install即可。

    六、安装coreseek

$ cd csft-3.2.14

$ sudo sh buildconf.sh

$ sudo ./configure --prefix=/usr/local/opt/coreseek  --without-unixodbc --with-mmseg --with-mmseg-includes=/usr/local/opt/mmseg3/include/mmseg/ --with-mmseg-libs=/usr/local/opt/mmseg3/lib/ --with-mysql --with-mysql-includes=/usr/local/Cellar/mysql/5.6.17_1/include/mysql --with-mysql-libs=/usr/local/Cellar/mysql/5.6.17_1/lib

$ sudo make

$ sudo make install

$ cd ..

在./configure时，参数--with-mysql-includes是mysql头文件位置，--with-mysql-libs是mysql库文件位置，请在本CoreSeek安装教程第三步所记录的mysql头文件地址和库文件地址，替换。

在make时，可能又会出现error级的错误，如果出现make程序是停止运行的，必须要修改。错误提示如下：

phinxexpr.cpp:1047:11: error: use of undeclared identifier 'ExprEval'

T val = ExprEval ( this->m_pArg, tMatch ); // 'this' fixes gcc ...

解决方法：修改源代码。

vim src/sphinxexpr.cpp

将T val = ExprEval( this->m_pArg, tMatch )替换为T val = this->ExprEval ( this->m_pArg, tMatch )。

就是加了个“this->”，是把这个文件中所有的ExprEval()函数都修改了，有三四个吧。

修改后保存退出，重新sudo make，然后sudo make install即可。

    七、测试XML数据

$ cd testpack

#测试编码是否正确显示中文，如果不是中文则请看本CoreSeek安装测试教程第一步

$ cat var/test/test.xml

# 测试mmseg分词的效果

$ /usr/local/opt/mmseg3/bin/mmseg -d /usr/local/opt/mmseg3/etc var/test/test.xml 

# 建立检索的索引。

$ /usr/local/opt/coreseek/bin/indexer -c etc/csft.conf --all

#全文搜索“网络搜索”

$ /usr/local/opt/coreseek/bin/search -c etc/csft.conf 网络搜索

如果在建立检索的索引出错，FATAL: failed to lock var/data/xml.spl: Resource temporarily unavailable, will not index. Try --rotate option.

则修改为

$ /usr/local/opt/coreseek/bin/indexer -c etc/csft.conf --all --rotate

    八、测试MYSQL数据源

cd testpack

1、修改配置文件，文件位于testpack/etc/csft_mysql.conf

vim etc/csft_mysql.conf

我的csft_mysql.conf文件如下：记得把mysql 的sql_host，sql_user，sql_pass，sql_db，sql_port修改为自己的，并且把路劲都修改为你自己的路径。

#MySQL数据源配置，详情请查看：http://www.coreseek.cn/products-install/mysql/

#请先将var/test/documents.sql导入数据库，并配置好以下的MySQL用户密码数据库

#源定义

source mysql

{

    type                    = mysql

    sql_host                = localhost

    sql_user                = root

    sql_pass                = 8823150

    sql_db                    = test

    sql_port                = 3306

    sql_query_pre            = SET NAMES utf8

    sql_query                = SELECT id, group_id, UNIX_TIMESTAMP(date_added) AS date_added, title, content FROM documents

                                                              #sql_query第一列id需为整数

                                                              #title、content作为字符串/文本字段，被全文索引

    sql_attr_uint            = group_id           #从SQL读取到的值必须为整数

    sql_attr_timestamp        = date_added #从SQL读取到的值必须为整数，作为时间属性

    sql_query_info_pre      = SET NAMES utf8                                        #命令行查询时，设置正确的字符集

    sql_query_info            = SELECT * FROM documents WHERE id=$id #命令行查询时，从数据库读取原始数据信息

}

#index定义

index mysql

{

    source            = mysql             #对应的source名称

    path            = /Users/lane/coreseek-3.2.14/testpack/var/data/mysql #请修改为实际使用的绝对路径，例如：/usr/local/coreseek/var/...

    docinfo            = extern

    mlock            = 0

    morphology        = none

    min_word_len        = 1

    html_strip                = 0

    #中文分词配置，详情请查看：http://www.coreseek.cn/products-install/coreseek_mmseg/

    charset_dictpath = /usr/local/opt/mmseg3/etc/ #BSD、Linux环境下设置，/符号结尾

    #charset_dictpath = etc/                             #Windows环境下设置，/符号结尾，最好给出绝对路径，例如：C:/usr/local/coreseek/etc/...

    charset_type        = zh_cn.utf-8

}

#全局index定义

indexer

{

    mem_limit            = 128M

}

#searchd服务定义

searchd

{

    listen                  =   9312

    read_timeout        = 5

    max_children        = 30

    max_matches            = 1000

    seamless_rotate        = 0

    preopen_indexes        = 0

    unlink_old            = 1

    pid_file = /Users/lane/coreseek-3.2.14/testpack/var/log/searchd_mysql.pid  #请修改为实际使用的绝对路径，例如：/usr/local/coreseek/var/...

    log = /Users/lane/coreseek-3.2.14/testpack/var/log/searchd_mysql.log        #请修改为实际使用的绝对路径，例如：/usr/local/coreseek/var/...

    query_log = /Users/lane/coreseek-3.2.14/testpack/var/log/query_mysql.log #请修改为实际使用的绝对路径，例如：/usr/local/coreseek/var/...

}

2、给mysql导入测试数据

    mysql的测试数据我们用的是test数据库，documents数据表。请自行确保test数据库存在，我们一起来建documents表，这个表的结构和数据都是由CoreSeek提供的，在testpack/var/test/documents.sql

mysql -u root -p

#输入密码

#看看，数据库test在不在

mysql > show databases; 

#如果test库不在请创建

mysql > create database test;

use test;

#导入数据

source /Users/lane/coreseek-3.2.14/testpack/var/test/documents.sql

3、测试：

$ cd testpack

# 建立检索的索引

$ /usr/local/opt/coreseek/bin/indexer -c etc/csft_mysql.conf --all

#全文搜索“网络搜索”

$ /usr/local/opt/coreseek/bin/search -c etc/csft_mysql.conf 网络搜索

如果提示有错误，请检查csft_mysql.conf的路径、mysql的配置等信息是否正确。

    九、测试PHP+MYSQL

1、先启动服务

/usr/local/opt/coreseek/bin/searchd -c etc/csft.conf

2、PHP文件

<?php

require ( "/Users/lane/coreseek-3.2.14/testpack/api/sphinxapi.php" );

$cl = new SphinxClient ();

$cl->SetServer ( '127.0.0.1', 9312);

$cl->SetConnectTimeout ( 3 );

$cl->SetArrayResult ( true );

$cl->SetMatchMode ( SPH_MATCH_ANY);

$res = $cl->Query ( '网络搜索', "*" );

print_r($cl);

print_r($res);

我在Linux折腾了一天没有搞定，在MAC搞了半天搞定了。等搞定Linux后再发Linux的。