2014年10月

快速排序,是最常用的排序算法,就是选择待排序的列表中的其中一个数字,作为基准数,然后把小于基准数的所有数字放到这个数的左边,大于这个数的所有数字放到基准数的右边。这个时候开始分为两部分,左边和右边。第一部分,在左边中选择一个数字作为基准数,把小于这个数字的放到这个数的左边,大于这个数的放到这个数的右边。第二部分,在右边中选择一个数字作为基准数,把小于这个数字的放到这个数的左边,大于这个数的放到这个数的右边。ok,很明显,递归!

快速排序的时间复杂度在最坏的情况下是O(N2),因为和冒泡排序一样,需要两两交换。平均情况下,快速排序的时间复杂度是O(NlogN)。

下面是C语言的代码

#include <stdio.h>

void quickSort(int left, int right, int *rank);

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");

    quickSort(0, num-1, rank);

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

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

    }

    return 0;

}

void quickSort(int left, int right, int *rank){

    if(left > right){

        return;

    }

    int i, j, t, tmp;

    i = left;

    j = right;

    t = rank[left];

    while(i!=j){

        while(rank[j]>=t && i<j)

            j--;

        while(rank[i]<=t && i<j)

            i++;

        if(i < j){

            tmp = rank[j];

            rank[j] = rank[i];

            rank[i] = tmp;

        }

    }

    rank[left] = rank[i];

    rank[i] = t;

    quickSort(left, i-1, rank);

    quickSort(i+1, right, rank);

}


冒泡排序是最被人熟知的排序算法。什么是冒泡排序?冒泡排序的特点是好邻居好说话,核心思想是一个每次比较两个相邻的元素,如果他们的大小顺序反了,就把他们交换过来。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)  使用哈希表来构建自己的数据库