<acronym id="xonnx"></acronym>
      <td id="xonnx"></td>
    1. <pre id="xonnx"></pre>

      1. 專注電子技術學習與研究
        當前位置:單片機教程網 >> MCU設計實例 >> 瀏覽文章

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

        作者:龔平   來源:本站原創   點擊數:  更新時間:2014年03月14日   【字體:

           一個星期沒有寫了,今天還是留點時間寫一寫自己的博客,周六去考試了趨勢科技,感受到了自己在軟件設計方面還存在的知識缺陷,測試、網絡安全等方面都是空白,其他的相對來說要好一點,今天還沒有收到面試通知應該是打了一次醬油了,不夠收獲還是蠻多的,記得第一題是關于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;   
            }

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

        關閉窗口

        相關文章

        欧美性色欧美精品视频,99热这里只有精品mp4,日韩高清亚洲日韩精品一区二区,2020国自产拍精品高潮