快速排序

快速排序
把左边都是较小的数,右边都是较大的数,再递归排序左右两边的数
时间复杂度O(nlog(n))
空间复杂度O(n)

第一种方法:指针移动过程中,第一个数参与交换

第一步:从右边开始移动后指针和第一个数比较大小,如果比第一个数小那么做交换,后指针停止;
第二步:从左边开始移动前指针和第一个数比较大小(已经交换,所以现在已经不是第一个数了),如果比第一个数大那么做交换,前指针停止;
第三步:重复第一步,第二步,知道前后指针相遇,这时前后指针和第一个数的指针位置重合在一起,此时出现前面的数都比第一个数小,后面的数都比第一个数大(比它小的都交换到前面去了,比它大的都交换到[……]

全文阅读

10G大小的数组只用100M内存进行排序计算

先讲下大致思路:

1、把数组分成n =ceil(arr_size/mem_size) 个小数组,分别对每个小数组排序(只能用冒泡、插入等空间复杂度是O(1)的排序方法)(实际写入n个文件)

2、依次从n个数组(实际应从文件中读取)中取出一个值,把最小的值放入输出的数组中,直到输出的数组增长mem_size长度之后(达到内存上限,写入磁盘),然后进行下一轮循环

function insertSort($arr) {
    $n=count($arr);
    for($i=1;$i<$n;$i++) {
        $tmp=$arr[$i];[......]

全文阅读

算法之杨辉三角

先对杨辉三角有个印象

求 第 h 行 第 r 列的数值

返回的结果:

使用递归1:第 100 行第 4 列值是: 156849 ,共计算 387 次,耗时 0.001 s
不用递归2:第 100 行第 4 列值是: 156849 ,共计算 292 次,耗时 0.001 s
不用递归3:第 100 行第 4 列值是: 156849 ,共计算 389 次,耗时 0.003 s

使用递归1:第 1000 行第 4 列值是: 165668499 ,共计算 3987 次,耗时 0.025 s
不用递归2:第 1000 行第 4 列值是: 165668499 ,共计算[……]

全文阅读