假设一个大小为100亿个数据的数组,该数组是从小到大排好序的,现在该数组分成若干段,每个段的数据长度小于20「也就是说:题目并没有说每段数据的size 相同,只是说每个段的 size < 20 而已」,然后将每段的数据进行乱序(即:段内数据乱序),形成一个新数组。请写一个算法,将所有数据从小到大进行排序,并说明时间复杂度。
涉及大数据处理:需要将数据hash若干小文件中,然后对各文件的数据进行排序,最后再进行堆排序或归并。
#include <iostream> #include <vector> using namespace std; #define N 6 #define M 3 void millionSort(int* myints, int len) { for (int i = 0; i <= len - M; ++i) { /*每次将后面一个元素加入堆中并保持最小堆 * 注意: 可以不用每次都重建最小堆,到最后在重建最小堆即可 * 只需保持最小堆原因:N-M个元素都会成为堆顶,若不是在最小堆则会重建, * 后面M个元素不一定满足最小堆,需重建 * less<int>()为构造最大堆,greater<int>()为构造最小堆(默认大堆) * */ make_heap(myints + i, myints + i + M, greater<int>()); // sort_heap(myints + i, myints + i + M + 1); } //后面M个元素不一定满足最小堆,需重建 /*sort_heap时,必须先是一个堆 *(两个特性:1、最大元素在第一个 2、添加或者删除元素以对数时间), * 因此必须先做一次make_heap*/ make_heap(myints + len - M, myints + len); sort_heap(myints + len - M, myints + len); //升序 }