先讲下大致思路:
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];
$j=$i-1;
while($arr[$j]>$tmp) {
$arr[$j+1]=$arr[$j];
$arr[$j]=$tmp;
$j--;
if($j<0)
break;
}
}
return $arr;
}
function sorts($from_file_arr,$mem_size,$method = 'insert'){
#$method = 'insert';
$fun = $method.'Sort';
$arr_size = count($from_file_arr);
$to_file_arr = [];
if($mem_size < $arr_size){
$arr_num = ceil($arr_size/$mem_size);
//模拟分段读取文件
for($i = 0; $i<$arr_num; $i++){
$tmp_arr = [];
$start = $i*$mem_size;
$end = ($i+1)*$mem_size;
if(($i+1) == $arr_num) $end = $arr_size;
for ($j = $start; $j < $end; $j++){
array_push($tmp_arr,$from_file_arr[$j]);
}
$piece_file_arr[$i] = $fun($tmp_arr);//这里模拟写入文件piece_file_$i.txt
}
//模拟输出到文件
$pointer = array_fill(0,$arr_num,0);
$white_list = [];
for($i = 0; $i < $arr_num; $i++){
array_push($white_list,$i);
}
$finished_list = [];
for($i = 0; $i < $arr_num; $i++){
$start = $i*$mem_size;
$end = ($i+1)*$mem_size;
if(($i+1) == $arr_num) $end = $arr_size;
for($j = $start; $j < $end; $j++){
$left_list = array_diff($white_list,$finished_list);
$line = reset($left_list);
$tmp_val = $piece_file_arr[$line][$pointer[$line]];
for($k = 0; $k < $arr_num; $k++){
if(in_array($k,$finished_list)){
continue;
}
if(isset($piece_file_arr[$k][$pointer[$k]])){
if($piece_file_arr[$k][$pointer[$k]] < $tmp_val){
$tmp_val = $piece_file_arr[$k][$pointer[$k]];
$line = $k;
}
}
}
$pointer[$line]++;
if($pointer[$line] == $mem_size){
array_push($finished_list,$line);
}
$to_file_arr[$j] = $tmp_val;//这里模拟写入最终的文件to_file.txt
}
}
return $to_file_arr;
}else{
return $fun($from_file_arr);
}
}
/*
* 数组模拟文件中的数据
* $from_file_arr 未排序的文件
* $piece_file_arr 分成小块的文件
* $to_file_arr 已排序的文件
* $mem_size 约束的内存大小
*/
$from_file_arr = [5,1,0,3,2,4,8,6,9,7,10,18,13,14,12,16,17,19,11,15,20,29,24,28,25,27,23,26,22,21];
$mem_size = 10;
print_r(sorts($from_file_arr,$mem_size));