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²)。所以这里要改进下插入排序。要将插入变为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左右。