一个星期没有写了，今天还是留点时间写一写自己的博客，周六去考试了科技，感受到了自己在软件设计方面还存在的知识缺陷，测试、网络安全等方面都是空白，其他的相对来说要好一点，今天还没有收到面试通知应该是打了一次酱油了，不够收获还是蛮多的，记得第一题是关于unicode方面的选择题，还有很多就是局部分配空间，返回无效指针的题目，总之感觉考得还是蛮基础，但是又设置了不少的陷阱，我很多回来又想了想，还是觉得自己知识面太少了，对于一个非科班出生的人，确实还是需要花一定的时间恶补一下。
总结两个题目吧，其中一个是多玩的题目：给你100万个数据，数据的值在0~65535之间 用最快的速度排序 ？
这样的数据虽然算不上是海量数据，但是我在Windows下面反正是不能跑成功，每次都是栈溢出。换到linux环境下，顺利的完成了数据的处理。首先分析一下自己的思路，很简单，如果采用快速排序算法应该是能够完成排序的，时间复杂度应该是在O(N*logN)，但是问题是题目是要求最快的速度排序，我认为应该是考虑一些时间排序算法，首先我就想到了桶排序，计数排序之类的，最后我选择了计数排序，实际上由于数据的值在0~65535之间，所以肯定存在大量的数据是重复的，这个值实际上就满足了计数排序的一些限制条件，采用hashmap的思想，统计相同值的个数，然后采用计数排序的思想，重新赋值数组即可。这时候的算法应该是非常快速的，时间复杂度应该为O(N)，这种方法也存在一定的问题，引入了额外的内存空间，和多玩要求的最快最少的内存空间存在一定的差别，但是时间上应该是比较快啦。
我的实现结合了hashmap的思想、计数排序的思想，实现代码如下所示：
#define BUFSIZE 65536 #define DATASIZE 1000000
void countsort(int *a, int size) { int i = 0 , j = 0; int countbuf[BUFSIZE] = {0};
for(i = 0; i < BUFSIZE; ++ i) countbuf[i] = 0;
for(i = 0; i < size; ++ i) countbuf[a[i]]++;
for(i = 1; i < BUFSIZE; ++ i) { countbuf[i] += countbuf[i - 1]; } for(i = 0; i < countbuf[0]; ++ i) a[i] = 0;
for(i = 1; i < BUFSIZE; ++ i) { for(j = countbuf[i-1]; j < countbuf[i]; ++ j) a[j] = i; } }
另一个就是伴随数组的运用，伴随数组主要是保存了数组中数据的原来下标位置，这样的存在形式可以避免在多次的修改中导致数组原有信息的丢失，特别是在一些保存历史信息的运用中，伴随数组是非常有用的。比如需要查找数组局部区域的第K个最小的值，这时候完全可以采用对局部区域进行排序，找出第k个值，但是这也存在一个问题，排序以后原有信息的丢失，如果重新选择新的局部区域，上面的排序就使得下面的操作毫无意义。当然也可以采用分配K个内存的方法，这种方法就是创建一个大小为K的数据空间，遍历数据，将满足选定区间的数插入到新数组中，遍历完数据以后就实现了数据的查找，这种方法对于少量排序的问题是可以接受的，但是如果新创建的数据区间非常的大，对一个新数组的排序等操作也是非常吓人的。
采用伴随数组可以避免多次的排序操作，只需要一次排序就能完成不同区间的第K个最小值的查找操作，具体的实现如下：
首先创建一个节点数据结构，存在两个成员，分别保存数据值和数值的下标，其中下标就表示了数据的历史信息，可以用来还原数组等操作。遍历数组创建节点数组。
其次，对节点数组进行排序，排序通常采用快速排序的方法实现。
最后，遍历节点数组值，当节点数组值的下标在所选择的区间时就将K减1，当K == 0时，这时候对应的数组值就是我们需要查找的局部区域的第K个最小值。
对于其他区间的实现方法只需要对最后一步进行修改，而不再需要数组的排序等操作，这种实现方法就能加快对其他局部区间数组的查找操作。这种方法的优点就是即保存了数组的原有信息，又避免了多次查找中的多次排序问题，采用一次排序的问题解决了不同区间的数据查找操作。
总结如上，我的代码实现如下，其中需要注意的是struct中的<操作符重载是必须的，且必须将其设置为const成员函数，不然编译不能通过，必须重载是因为排序过程中需要比较对象的大小：
#include<iostream> #include<vector> #include<time.h> #include<assert.h> #include<algorithm>
using namespace std;
template<typename T> struct node { T num; int index;
/*该操作符重载是必须的，因为排序过程需要比较数值大小*/ bool operator<(const node<T> &rhs)const { return num < rhs.num; }
friend ostream & operator<<(ostream &os, const node<T> &_node) { os << _node.num << " " << _node.index; return os; } };
template<typename T> node<T>& zoomsort(vector<node<T> > &array, int left, int right, int k) { int i = 0;
assert((left <= right) && (right - left >= k - 1)); /*基于库函数的排序算法*/ sort(array.begin(), array.end()); /*查找过程*/ for(i = 0; i < array.size(); ++ i) { if(array[i].index >= left && array[i].index <= right) -- k;
if(k == 0) break; } if(k == 0) return array[i]; }
int main() { int i = 0; int num = 0; node<int> anode; vector<node<int> > array; for(i = 0; i < 10; ++ i) { cin >> num; anode.num = num; anode.index = i; array.push_back(anode); }
for(i = 0; i < 10; ++ i) cout << array[i].num << "\t"; cout << endl;
cout << "the 3rd num in 2 to 6: "; cout << zoomsort(array, 2,6,3) << endl; cout << "the 4th num in 1 to 7: "; cout << zoomsort(array, 1,7,4) << endl; cout << "the 4th num in 3 to 9: "; cout << zoomsort(array, 3,9,4) << endl;
return 0; }
虽然，找工作是挺打击自己的，但是我相信会逐渐好起来的。
-电子元器件采购网（www.ruidan.com）是本土元器件目录分销商，采用“小批量、现货、样品”销售模式，致力于满足客户多型号、高质量、快速交付的采购需求。 自建高效智能仓储，拥有自营库存超过50,000种，提供一站式正品现货采购、个性化解决方案、选型替代等多元化服务。