Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1751048
  • 博文数量: 152
  • 博客积分: 3730
  • 博客等级: 上尉
  • 技术积分: 3710
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-02 14:36
个人简介

减肥,运动,学习,进步...

文章分类

全部博文(152)

文章存档

2016年(14)

2015年(17)

2014年(16)

2013年(4)

2012年(66)

2011年(35)

分类: C/C++

2012-09-25 20:13:07

    一个星期没有写了,今天还是留点时间写一写自己的博客,周六去考试了趋势科技,感受到了自己在软件设计方面还存在的知识缺陷,测试、网络安全等方面都是空白,其他的相对来说要好一点,今天还没有收到面试通知应该是打了一次酱油了,不够收获还是蛮多的,记得第一题是关于unicode方面的选择题,还有很多就是局部分配空间,返回无效指针的题目,总之感觉考得还是蛮基础,但是又设置了不少的陷阱,我很多回来又想了想,还是觉得自己知识面太少了,对于一个非科班出生的人,确实还是需要花一定的时间恶补一下。

    总结两个题目吧,其中一个是多玩的题目:给你100万个数据,数据的值在0~65535之间 用最快的速度排序 ?

    这样的数据虽然算不上是海量数据,但是我在Windows下面反正是不能跑成功,每次都是栈溢出。换到linux环境下,顺利的完成了数据的处理。首先分析一下自己的思路,很简单,如果采用快速排序算法应该是能够完成排序的,时间复杂度应该是在O(N*logN),但是问题是题目是要求最快的速度排序,我认为应该是考虑一些时间排序算法,首先我就想到了桶排序,计数排序之类的,最后我选择了计数排序,实际上由于数据的值在0~65535之间,所以肯定存在大量的数据是重复的,这个值实际上就满足了计数排序的一些限制条件,采用hashmap的思想,统计相同值的个数,然后采用计数排序的思想,重新赋值数组即可。这时候的算法应该是非常快速的,时间复杂度应该为O(N),这种方法也存在一定的问题,引入了额外的内存空间,和多玩要求的最快最少的内存空间存在一定的差别,但是时间上应该是比较快啦。

    我的实现结合了hashmap的思想、计数排序的思想,实现代码如下所示:

点击(此处)折叠或打开

  1. #define BUFSIZE        65536
  2. #define DATASIZE    1000000

  3. void countsort(int *a, int size)
  4. {
  5.     int i = 0 , j = 0;
  6.     int countbuf[BUFSIZE] = {0};

  7.     for(i = 0; i < BUFSIZE; ++ i)
  8.         countbuf[i] = 0;

  9.     for(i = 0; i < size; ++ i)
  10.         countbuf[a[i]]++;

  11.     for(i = 1; i < BUFSIZE; ++ i)
  12.     {
  13.         countbuf[i] += countbuf[i - 1];
  14.     }
  15.     
  16.     for(i = 0; i < countbuf[0]; ++ i)
  17.         a[i] = 0;

  18.     for(i = 1; i < BUFSIZE; ++ i)
  19.     {
  20.         for(j = countbuf[i-1]; j < countbuf[i]; ++ j)
  21.             a[j] = i;
  22.     }
  23. }

    另一个就是伴随数组的运用,伴随数组主要是保存了数组中数据的原来下标位置,这样的存在形式可以避免在多次的修改中导致数组原有信息的丢失,特别是在一些保存历史信息的运用中,伴随数组是非常有用的。比如需要查找数组局部区域的第K个最小的值,这时候完全可以采用对局部区域进行排序,找出第k个值,但是这也存在一个问题,排序以后原有信息的丢失,如果重新选择新的局部区域,上面的排序就使得下面的操作毫无意义。当然也可以采用分配K个内存的方法,这种方法就是创建一个大小为K的数据空间,遍历数据,将满足选定区间的数插入到新数组中,遍历完数据以后就实现了数据的查找,这种方法对于少量排序的问题是可以接受的,但是如果新创建的数据区间非常的大,对一个新数组的排序等操作也是非常吓人的。

    采用伴随数组可以避免多次的排序操作,只需要一次排序就能完成不同区间的第K个最小值的查找操作,具体的实现如下:

    首先创建一个节点数据结构,存在两个成员,分别保存数据值和数值的下标,其中下标就表示了数据的历史信息,可以用来还原数组等操作。遍历数组创建节点数组。

    其次,对节点数组进行排序,排序通常采用快速排序的方法实现。

    最后,遍历节点数组值,当节点数组值的下标在所选择的区间时就将K减1,当K == 0时,这时候对应的数组值就是我们需要查找的局部区域的第K个最小值。

    对于其他区间的实现方法只需要对最后一步进行修改,而不再需要数组的排序等操作,这种实现方法就能加快对其他局部区间数组的查找操作。这种方法的优点就是即保存了数组的原有信息,又避免了多次查找中的多次排序问题,采用一次排序的问题解决了不同区间的数据查找操作。

    总结如上,我的代码实现如下,其中需要注意的是struct中的<操作符重载是必须的,且必须将其设置为const成员函数,不然编译不能通过,必须重载是因为排序过程中需要比较对象的大小:

点击(此处)折叠或打开

  1. #include<iostream>
  2. #include<vector>
  3. #include<time.h>
  4. #include<assert.h>
  5. #include<algorithm>

  6. using namespace std;

  7. template<typename T>
  8. struct node
  9. {
  10.     T num;
  11.     int index;

  12.     /*该操作符重载是必须的,因为排序过程需要比较数值大小*/
  13.     bool operator<(const node<T> &rhs)const
  14.     {
  15.         return num < rhs.num;
  16.     }

  17.     friend ostream &
  18.     operator<<(ostream &os, const node<T> &_node)
  19.     {
  20.         os << _node.num << " " << _node.index;
  21.         return os;
  22.     }
  23. };

  24. template<typename T>
  25. node<T>& zoomsort(vector<node<T> > &array,
  26.             int left, int right, int k)
  27. {
  28.     int i = 0;

  29.     assert((left <= right)
  30.         && (right - left >= k - 1));
  31.         
  32.    /*基于库函数的排序算法*/
  33.     sort(array.begin(), array.end());
  34.     
  35.     /*查找过程*/
  36.     for(i = 0; i < array.size(); ++ i)
  37.     {
  38.         if(array[i].index >= left
  39.             && array[i].index <= right)
  40.             -- k;

  41.         if(k == 0)
  42.             break;
  43.     }
  44.     if(k == 0)
  45.         return array[i];
  46. }

  47. int main()
  48. {
  49.     int i = 0;
  50.     int num = 0;
  51.     node<int> anode;
  52.     vector<node<int> > array;
  53.     
  54.     for(i = 0; i < 10; ++ i)
  55.     {
  56.         cin >> num;
  57.         anode.num = num;
  58.         anode.index = i;
  59.         
  60.         array.push_back(anode);
  61.     }

  62.     for(i = 0; i < 10; ++ i)
  63.         cout << array[i].num << "\t";
  64.     cout << endl;

  65.     cout << "the 3rd num in 2 to 6: ";
  66.     cout << zoomsort(array, 2,6,3) << endl;
  67.     cout << "the 4th num in 1 to 7: ";
  68.     cout << zoomsort(array, 1,7,4) << endl;
  69.     cout << "the 4th num in 3 to 9: ";
  70.     cout << zoomsort(array, 3,9,4) << endl;

  71.     return 0;    
  72. }

    虽然,找工作是挺打击自己的,但是我相信会逐渐好起来的。

 

阅读(4038) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~