大数据排序c++
一个二维数组
char[25000000][40];
要求按第二维的数据中的四十个字符进行排序,
怎么排序最快呢?
c++实现
[解决办法]
(1)若n较小(如n≤50),可采用直接插入或直接选择排序。
当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
(3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。若要求排序稳定,则可选用归并排序。
[解决办法]
快速排序吧
[解决办法]
#include <iostream>#include <algorithm>using namespace std;//这个结构的内存布局和char[40]兼容//用于作为sort算法的迭代器struct array_t{ char data[40];};//比较,当然也可以写到array_t里的operator<方法bool arrayless(array_t &a, array_t &b){ return memcmp(a.data,b.data,40) < 0;}int main(int argc, char* argv[]){ //这里演示5组数据,你的25000000好大,不能放在栈里的 char data[5][40]={ "abc", "123", "你好~~", "hello world", "yun" }; //转换成array_t*类型(我说过,是兼容的),把pData作为迭代器 array_t *pData = (array_t *)data; //用sort算法排序,sort使用的就是快速排序算法 std::sort(pData, pData+5, arrayless); //输出,看看是不是排好序了 for(int i=0; i<5; i++) cout << data[i] << endl; return 0;}
[解决办法]
內存放不下時,你可以分段排序。
1、將大文件切割成一個個小文件,保證每個小文件可以全部放入內存排序。
2、分別對 File1......FileN 排序,並索引,File1......FileN的最大值,最小值,數量。找出全部文件的最大最小值。
3、重新分段 File1......FileN ,保持每段最大值最小值不干涉。
4、將數據放入文件中。保證每個文件均可全部放入內存並排序,如果文件超大則修改最大最小值,並放入下一文件中。
5、全部文件重新排序完成,將 File1......FileN 合並成一個大文件。
單文件排序用std::sort就好了。
(如果可以用數據庫,用數據庫一句 order by 就行了。)