一個(gè)星期沒(méi)有寫(xiě)了，今天還是留點(diǎn)時(shí)間寫(xiě)一寫(xiě)自己的博客，周六去考試了趨勢(shì)科技，感受到了自己在軟件設(shè)計(jì)方面還存在的知識(shí)缺陷，測(cè)試、網(wǎng)絡(luò)安全等方面都是空白，其他的相對(duì)來(lái)說(shuō)要好一點(diǎn)，今天還沒(méi)有收到面試通知應(yīng)該是打了一次醬油了，不夠收獲還是蠻多的，記得第一題是關(guān)于unicode方面的選擇題，還有很多就是局部分配空間，返回?zé)o效指針的題目，總之感覺(jué)考得還是蠻基礎(chǔ)，但是又設(shè)置了不少的陷阱，我很多回來(lái)又想了想，還是覺(jué)得自己知識(shí)面太少了，對(duì)于一個(gè)非科班出生的人，確實(shí)還是需要花一定的時(shí)間惡補(bǔ)一下。
總結(jié)兩個(gè)題目吧，其中一個(gè)是多玩的題目：給你100萬(wàn)個(gè)數(shù)據(jù)，數(shù)據(jù)的值在0~65535之間 用最快的速度排序 ？
這樣的數(shù)據(jù)雖然算不上是海量數(shù)據(jù)，但是我在Windows下面反正是不能跑成功，每次都是棧溢出。換到linux環(huán)境下，順利的完成了數(shù)據(jù)的處理。首先分析一下自己的思路，很簡(jiǎn)單，如果采用快速排序算法應(yīng)該是能夠完成排序的，時(shí)間復(fù)雜度應(yīng)該是在O(N*logN)，但是問(wèn)題是題目是要求最快的速度排序，我認(rèn)為應(yīng)該是考慮一些時(shí)間排序算法，首先我就想到了桶排序，計(jì)數(shù)排序之類的，最后我選擇了計(jì)數(shù)排序，實(shí)際上由于數(shù)據(jù)的值在0~65535之間，所以肯定存在大量的數(shù)據(jù)是重復(fù)的，這個(gè)值實(shí)際上就滿足了計(jì)數(shù)排序的一些限制條件，采用hashmap的思想，統(tǒng)計(jì)相同值的個(gè)數(shù)，然后采用計(jì)數(shù)排序的思想，重新賦值數(shù)組即可。這時(shí)候的算法應(yīng)該是非常快速的，時(shí)間復(fù)雜度應(yīng)該為O(N)，這種方法也存在一定的問(wèn)題，引入了額外的內(nèi)存空間，和多玩要求的最快最少的內(nèi)存空間存在一定的差別，但是時(shí)間上應(yīng)該是比較快啦。
我的實(shí)現(xiàn)結(jié)合了hashmap的思想、計(jì)數(shù)排序的思想，實(shí)現(xiàn)代碼如下所示：
#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;
}
}
另一個(gè)就是伴隨數(shù)組的運(yùn)用，伴隨數(shù)組主要是保存了數(shù)組中數(shù)據(jù)的原來(lái)下標(biāo)位置，這樣的存在形式可以避免在多次的修改中導(dǎo)致數(shù)組原有信息的丟失，特別是在一些保存歷史信息的運(yùn)用中，伴隨數(shù)組是非常有用的。比如需要查找數(shù)組局部區(qū)域的第K個(gè)最小的值，這時(shí)候完全可以采用對(duì)局部區(qū)域進(jìn)行排序，找出第k個(gè)值，但是這也存在一個(gè)問(wèn)題，排序以后原有信息的丟失，如果重新選擇新的局部區(qū)域，上面的排序就使得下面的操作毫無(wú)意義。當(dāng)然也可以采用分配K個(gè)內(nèi)存的方法，這種方法就是創(chuàng)建一個(gè)大小為K的數(shù)據(jù)空間，遍歷數(shù)據(jù)，將滿足選定區(qū)間的數(shù)插入到新數(shù)組中，遍歷完數(shù)據(jù)以后就實(shí)現(xiàn)了數(shù)據(jù)的查找，這種方法對(duì)于少量排序的問(wèn)題是可以接受的，但是如果新創(chuàng)建的數(shù)據(jù)區(qū)間非常的大，對(duì)一個(gè)新數(shù)組的排序等操作也是非常嚇人的。
采用伴隨數(shù)組可以避免多次的排序操作，只需要一次排序就能完成不同區(qū)間的第K個(gè)最小值的查找操作，具體的實(shí)現(xiàn)如下：
首先創(chuàng)建一個(gè)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，存在兩個(gè)成員，分別保存數(shù)據(jù)值和數(shù)值的下標(biāo)，其中下標(biāo)就表示了數(shù)據(jù)的歷史信息，可以用來(lái)還原數(shù)組等操作。遍歷數(shù)組創(chuàng)建節(jié)點(diǎn)數(shù)組。
其次，對(duì)節(jié)點(diǎn)數(shù)組進(jìn)行排序，排序通常采用快速排序的方法實(shí)現(xiàn)。
最后，遍歷節(jié)點(diǎn)數(shù)組值，當(dāng)節(jié)點(diǎn)數(shù)組值的下標(biāo)在所選擇的區(qū)間時(shí)就將K減1，當(dāng)K == 0時(shí)，這時(shí)候?qū)?yīng)的數(shù)組值就是我們需要查找的局部區(qū)域的第K個(gè)最小值。
對(duì)于其他區(qū)間的實(shí)現(xiàn)方法只需要對(duì)最后一步進(jìn)行修改，而不再需要數(shù)組的排序等操作，這種實(shí)現(xiàn)方法就能加快對(duì)其他局部區(qū)間數(shù)組的查找操作。這種方法的優(yōu)點(diǎn)就是即保存了數(shù)組的原有信息，又避免了多次查找中的多次排序問(wèn)題，采用一次排序的問(wèn)題解決了不同區(qū)間的數(shù)據(jù)查找操作。
總結(jié)如上，我的代碼實(shí)現(xiàn)如下，其中需要注意的是struct中的<操作符重載是必須的，且必須將其設(shè)置為const成員函數(shù)，不然編譯不能通過(guò)，必須重載是因?yàn)榕判蜻^(guò)程中需要比較對(duì)象的大小：
#include<iostream>
#include<vector>
#include<time.h>
#include<assert.h>
#include<algorithm>
using namespace std;
template<typename T>
struct node
{
T num;
int index;
/*該操作符重載是必須的，因?yàn)榕判蜻^(guò)程需要比較數(shù)值大小*/
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));
/*基于庫(kù)函數(shù)的排序算法*/
sort(array.begin(), array.end());
/*查找過(guò)程*/
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;
}
雖然，找工作是挺打擊自己的，但是我相信會(huì)逐漸好起來(lái)的。