Linear线性级排序算法
线性级排序算法
需求：需要找到前 m 个大数，这 m 个数必须有序。现在有 n 个数（ n>>m ）。可以使用大空间但是空间远小于 n
。这里的含义是连同这 n 个数都不要占用 n 的空间。因为数据量太大了。 N 个数是一个一个生成的。
思考：
1. 这 m 个数有序，这当然不是一个排序问题，或者是一个部分排序问题。已知的排序是冒泡，插入，选择，归并，快速和基数排序。
2. 冒泡效率低。选择排序的要求是这 n 个数已经存在，并且需要的空间（包括这 n 个数的存储空间）肯定大于 n 。快排，虽然在找第 k
的数是 klogk 的复杂度也就是线性级 O(n) 。但是它还是需要 O(n) 的空间。归并排序，基数排序也是同样如此。
3. 插入排序要求，元素是要移动的。所以插入的移动数据复杂度是 O(n 2 ) 。所以这里要改进下插入排序。要将插入变为 O(1)
。那么就要使用链表。而且数据是一个一个生成的，那么小的数据插入在大的数据后面。这样就完成了排序任务。
4. 另外设置固定长度为 l, 可以认为即使是大数据量 n ，也有 cl=n/l, 其中 cl 为较小常数。
部分伪代码：
public static void Sort (LinkedList lsort ,double num)
{
if(lsort.size() == 0 )
{
lsort.add(0, num);
return;
}
for(int i = 0; i < m && i< lsort.size(); i++)
{
if(num > lsort.get(i))
{
lsort.add(i,num);
break;
}
}
// remove no used sort object
if(lsort.size() == maxSize)
{
int startIndex = maxSize - fileSetNum;
while(startIndex – != 0)
{
lsort.removeLast();
}
}
}
我们下面对上面的这段代码进行分析 , 因为使用链表，所以插入删除的复杂度为 O(1), 查找的复杂度为 O(m) 但是会包含在第二段代码中：
if(lsort.size() == 0 )
{
lsort.add(0, num);
return;
}
这段代码的时间复杂度明显是 O(1)
for(int i = 0; i < m && i< lsort.size(); i++)
{
if(num > lsort.get(i))
{
lsort.add(i,num);
break;
}
}
这段代码中 m 个数为常数。所以这个进行比较的时间复杂度最差为 O(m) ，即只与前 m 个数进行比较。
// remove no used sort object
if(lsort.size() == l)
{
int startIndex = l – m;
while(startIndex – != 0)
{
lsort.removeLast();
}
}
这段代码是为了减少存储空间。当空间达到 l 时，将会释放 l-m 个空间。使得存储空间不会到达 n 。这段代码的时间复杂度为 O(l-m)
。 但是因为这段代码不是经常执行 , 要在链表长度到达 l 时才会执行，所以分摊到各个执行上其复杂度为 O((l-m)*l/n).
当此段代码需要访问 n 次。
所以总复杂度为各个复杂度加和再乘 n 为： n*(O(1)+ O(m)+O((1-m)*l/n)) = O(n+mn+(1-m)*l)=O(mn),
因为 m 为常数，所以故为 O(n)
总结：
根据已有的算法知识，做出符合需求的算法。并且这个算法的时间复杂度也很理想。在实际运行过程中达到了很好的效果。使用 java 测试。在 290000
条待排序的数据中，时间消耗在 700ms 左右。