伴隨數組、計數排序的運用

總結兩個題目吧，其中一個是多玩的題目：給你100萬個數據，數據的值在0~65535之間 用最快的速度排序 ？

這樣的數據雖然算不上是海量數據，但是我在Windows下面反正是不能跑成功，每次都是棧溢出。換到linux環(huán)境下，順利的完成了數據的處理。首先分析一下自己的思路，很簡單，如果采用快速排序算法應該是能夠完成排序的，時間復雜度應該是在O(N*logN)，但是問題是題目是要求最快的速度排序，我認為應該是考慮一些時間排序算法，首先我就想到了桶排序，計數排序之類的，最后我選擇了計數排序，實際上由于數據的值在0~65535之間，所以肯定存在大量的數據是重復的，這個值實際上就滿足了計數排序的一些限制條件，采用hashmap的思想，統(tǒng)計相同值的個數，然后采用計數排序的思想，重新賦值數組即可。這時候的算法應該是非?？焖俚?，時間復雜度應該為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;
}
}

另一個就是伴隨數組的運用，伴隨數組主要是保存了數組中數據的原來下標位置，這樣的存在形式可以避免在多次的修改中導致數組原有信息的丟失，特別是在一些保存歷史信息的運用中，伴隨數組是非常有用的。比如需要查找數組局部區(qū)域的第K個最小的值，這時候完全可以采用對局部區(qū)域進行排序，找出第k個值，但是這也存在一個問題，排序以后原有信息的丟失，如果重新選擇新的局部區(qū)域，上面的排序就使得下面的操作毫無意義。當然也可以采用分配K個內存的方法，這種方法就是創(chuàng)建一個大小為K的數據空間，遍歷數據，將滿足選定區(qū)間的數插入到新數組中，遍歷完數據以后就實現了數據的查找，這種方法對于少量排序的問題是可以接受的，但是如果新創(chuàng)建的數據區(qū)間非常的大，對一個新數組的排序等操作也是非常嚇人的。

采用伴隨數組可以避免多次的排序操作，只需要一次排序就能完成不同區(qū)間的第K個最小值的查找操作，具體的實現如下：

首先創(chuàng)建一個節(jié)點數據結構，存在兩個成員，分別保存數據值和數值的下標，其中下標就表示了數據的歷史信息，可以用來還原數組等操作。遍歷數組創(chuàng)建節(jié)點數組。

其次，對節(jié)點數組進行排序，排序通常采用快速排序的方法實現。

最后，遍歷節(jié)點數組值，當節(jié)點數組值的下標在所選擇的區(qū)間時就將K減1，當K == 0時，這時候對應的數組值就是我們需要查找的局部區(qū)域的第K個最小值。

對于其他區(qū)間的實現方法只需要對最后一步進行修改，而不再需要數組的排序等操作，這種實現方法就能加快對其他局部區(qū)間數組的查找操作。這種方法的優(yōu)點就是即保存了數組的原有信息，又避免了多次查找中的多次排序問題，采用一次排序的問題解決了不同區(qū)間的數據查找操作。

總結如上，我的代碼實現如下，其中需要注意的是struct中的<操作符重載是必須的，且必須將其設置為const成員函數，不然編譯不能通過，必須重載是因為排序過程中需要比較對象的大小：

#include
#include
#include
#include
#include

using namespace std;

template
struct node
{
T num;
int index;

/*該操作符重載是必須的，因為排序過程需要比較數值大小*/
bool operator<(const node &rhs)const
{
return num < rhs.num;
}

friend ostream &
operator<<(ostream &os, const node &_node)
{
os << _node.num << " " << _node.index;
return os;
}
};

template
node& zoomsort(vector > &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 anode;
vector > 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 << " ";
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;
}

雖然，找工作是挺打擊自己的，但是我相信會逐漸好起來的。