随同数组、计数排序的运用

一个星期没有写了，今日仍是留点时刻写一写自己的博客，周六去考试了趋势科技，感触到了自己在软件设计方面还存在的常识缺点，测验、网络安全等方面都是空白，其他的相对来说要好一点，今日还没有收到面试告诉应该是打了一次酱油了，不行收成仍是蛮多的，记住第一题是关于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
#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;
}

尽管，找工作是挺冲击自己的，可是我信任会逐步好起来的。