A. 数据结构一道排序题怎么排啊我想知道思路 答案已经有请告诉帮我分析一下
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I=J；
例如：待排序的数组A的值分别是：（初始关键数据X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
进行第一次交换后： 27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找
进行第二次交换后： 27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )
进行第三次交换后： 27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后： 27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )
此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：
初始状态 {49 38 65 97 76 13 27}
进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}
分别对前后两部分进行快速排序 {13} 27 {38}
结束 结束 {49 65} 76 {97}
49 {65} 结束
结束
图6 快速排序全过程
1）、设有N（假设N=10）个数，存放在S数组中；
2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；
3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。
如具体数据如下，那么第一躺快速排序的过程是：
数组下标： 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
I J
（1） 36 36 18 53 72 30 48 93 15 45
（2） 36 36 18 45 72 30 48 93 15 53
（3） 36 36 18 15 72 30 48 93 45 53
（4） 36 36 18 15 45 30 48 93 72 53
（5） 36 36 18 15 30 45 48 93 72 53
通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。
一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法，我不知道它是不是现有排序方法中最快的，但它是我见过的最快的。排序同样的数组，它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。
“快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。
我这样讲你们是不是很胡涂，不要紧，我下面给出实现的两个函数：
/*
n就是需要排序的数组，left和right是你需要排序的左界和右界，
如果要排序上面那个数组，那么left和right分别是0和9
*/
void quicksort(int n[], int left,int right)
{
int dp;
if (left<right) {
/*
这就是下面要讲到的函数，按照上面所说的，就是把所有小于53的数放
到它的左边，大的放在右边，然后返回53在整理过的数组中的位置。
*/
dp=partition(n,left,right);
quicksort(n,left,dp-1);
quicksort(n,dp+1,right); //这两个就是递归调用，分别整理53左边的数组和右边的数组
}
}
我们上面提到先定位第一个数，然后整理这个数组，把比这个数小的放到它的左边，大的放右边，然后
返回这中间值的位置，下面这函数就是做这个的。
int partition(int n[],int left,int right)
{
int lo,hi,pivot,t;
pivot=n[left];
lo=left-1;
hi=right+1;
while(lo+1!=hi) {
if(n[lo+1]<=pivot)
lo++;
else if(n[hi-1]>pivot)
hi--;
else {
t=n[lo+1];
n[++lo]=n[hi-1];
n[--hi]=t;
}
}
n[left]=n[lo];
n[lo]=pivot;
return lo;
}
这段程序并不难，应该很好看懂，我把过程大致讲一下，首先你的脑子里先浮现一个数组和三个指针，第一个指针称为p指针，在整个过程结束之前它牢牢的指向第一个数，第二个指针和第三个指针分别为lo指针和hi指针，分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近，在逼近的过程中不停的与p指针的值比较，如果lo指针的值比p指针的值小，lo++，还小还++，再小再++，直到碰到一个大于p指针的值，这时视线转移到hi指针，如果 hi指针的值比p指针的值大，hi--，还大还--，再大再--，直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面，这时把p指针的值和碰面的值做一个调换，然后返回p指针新的位置。
B. 海量数据分析处理方法
海量数据分析处理方法
一、Bloom filter
适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集
基本原理及要点：
对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。
还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。
注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
扩展：
Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。
二、Hashing
适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存
基本原理及要点：
hash函数选择，针对字符串，整数，排列，具体相应的hash方法。
碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。
扩展：
d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。
问题实例：
1).海量日志数据，提取出某日访问网络次数最多的那个IP。
IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。
三、bit-map
适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下
基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码
扩展：bloom filter可以看做是对bit-map的扩展
问题实例：
1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。
2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。
四、堆
适用范围：海量数据前n大，并且n比较小，堆可以放入内存
基本原理及要点：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。
扩展：双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。
问题实例：
1)100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。
五、双层桶划分-—其实本质上就是【分而治之】的思想，重在分的技巧上！
适用范围：第k大，中位数，不重复或重复的数字
基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。
扩展：
问题实例：
1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。
2).5亿个int找它们的中位数。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。
六、数据库索引
适用范围：大数据量的增删改查
基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。
七、倒排索引(Inverted index)
适用范围：搜索引擎，关键字查询
基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
以英文为例，下面是要被索引的文本： T0 = “it is what it is” T1 = “what is it” T2 = “it is a banana”
我们就能得到下面的反向文件索引：
“a”: {2} “banana”: {2} “is”: {0, 1, 2} “it”: {0, 1, 2} “what”: {0, 1}
检索的条件”what”,”is”和”it”将对应集合的交集。
正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。
扩展：
问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。
八、外排序
适用范围：大数据的排序，去重
基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
扩展：
问题实例：
1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。
这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。
九、trie树
适用范围：数据量大，重复多，但是数据种类小可以放入内存
基本原理及要点：实现方式，节点孩子的表示方式
扩展：压缩实现。
问题实例：
1).有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。
2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？
3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。
十、分布式处理 maprece
适用范围：数据量大，但是数据种类小可以放入内存
基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。
扩展：
问题实例：
1).The canonical example application of MapRece is a process to count the appearances ofeach different word in a set of documents:
2).海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
3).一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？
C. 数据分析的几种常用方法21-10-27
几种常见的数据分析分析方法：
1.周期性分析（基础分析）
What ：主要是从日常杂乱的数据中，发现周期性出现的现象，而从避免或改善问题的发生。常见的两种周期：自然周期和生命周期。
需要注意的点：虽然周期性分析主要针对时间序列，但不全是，例如公众号的文章阅读走势不仅和日期（工作日或周末）相关，也和文章类型相关。
例如：销售中3,6,9,12月，由于绩效考核出现的峰值
重点节假日对和交付的影响
产品销售的季节性影响（例如北方下半年的采暖产品，入夏空调的销售旺季等）
How： 自然后期的时间维度，根据分析的需求，可从年（同环比，业绩达成、和行业趋势对比），月（淡旺季、销售进度、生产预测），周（一般较少），日（工作日，非工作日的差异分析），时（时间分布，工作时段，上下班高峰，晚上，主要和大众消费行为分析相关）进行展开
生命周期一种常见的分析就“商品生命周期”，商品销量随上市时间的变化，通过时间轴+指标走势组合出来的。这种分析对快消品或者产品迭代速度很快的商品（典型如手机）是比较重要的，可以用于监控产品的市场表现，对照市场活动可以量化活动效果以及产品线的经营情况，如持续跟进，则可针对性的提出产品上市的建议。
2.矩阵分析（重要分析方法）
矩阵分析是数据分析中非常重要的分析方法。主要解决分析领域的一个非常致命的核心问题：“到底指标是多少，才算好”。
平均数是一个非常常用的数据维度，但是单一维度，并不能充分评价好坏。例如考核销售，如果只考核业务销售业绩，那么业务人员一定会倾向卖利润低的引流产品。那种利润高，价格高，不容易卖的利润型产品就没人卖了，最后销售越多，公司的利润反而下降了。这个时候通过两个维度：销售规模和销售利润，构建交叉矩阵，就能将业务业绩进行更有效的区分。
举个简单的例子，一个销售团队，10名销售一个月内开发的客户数量，产生的总业绩用矩阵分析法进行分析（具体数据略）：
第一步：先对客户数量、业绩求平均值
第二步：利用平均值，对每个销售人员的客户数量、业绩进行分类
第三步：区分出多客户+高业绩，少客户+高业绩，多客户+低业绩，少客户+低业绩四类
矩阵分析把关键业务目标拆分为两个维度，每个维度进行高低分类，进而可以对目标进行更加立体的描述。维度高低分类多采用 平均值作为参考 值。
注意：有两个场景，是不适合用矩阵分析法：
一：有极大/极小值影响了平均值的时候，一般出现极大/极小值的时候，可以用： 分层分析法 。
二：两个指标高度相关的时候，例如用户消费金额与消费频次，两个指标天生高度相关，此时数据分布会集中在某一个或两个区域，矩阵分析法的业务解读能力接近0，可采用 相关分析法
3.结构分析
What： 结构分析是将分析的目标，向下分解，主要用于发现问题。
例如销售分析，可以按照区域—省—市 一级级的分解，分解之后可以更好的看出影响销售业绩的影响因素在哪个位置。
结构分析可以有多个维度，取决于我们需要分析的方向。例如还是销售分析，可以从产品构成进行拆解，也可用从业务形态拆解
How：如何进行结构分析？
第一步：定出要分析的关键指标（一般是业绩、用户量、DAU、利润等等）
第二步：了解关键指标的构成方式（比如业绩，由哪些用户、哪些商品、哪些渠道组成）
第三步：跟踪关键指标的走势，了解指标结构变化情况
第四步：在关键指标出现明显上升/下降的时候，找到变化最大的结构分类，分析问题
注意：结构分析的不足
结构分析法是一种：知其然，不知其所以然的方法。只适用于发现问题，不能解答问题
4.分层分析
What： 分层分析，是为了应对 平均值失效 的场景。典型的平均值失效例如平均工资，很多人都被“代表”。这个时候需要把收入群体分成几类，例如土豪，普通百姓，穷光蛋等，后面进行分析时就比较清楚了。业内也有一些不同的叫法，比如应用于商品的，叫ABC分类，应用于用户的，叫用户分层，应用于业务的，叫二八法则。本质都是一回事。
How：如何进行分层分析
1.明确分层对象和分层指标
例如：想区分用户消费力，分层对象就是：用户，分层指标就是：消费金额
想区分商品销售额，分层对象就是：商品，分层指标就是：销售金额
想区分部销售额，分层对象就是：分部，分层指标就是：销售收入
2.查看数据，确认是否需要分层。分层是应对平均值失效的情况的，存在极值影响的情况，则适合分层。
3.设定分层的层级。最好的解决办法是老板拍板，其次可以用“二八原则”，以上述销售业绩分层为例，可以先从高到低排序，然后把累积业绩占80%的人选出来，作为“第1层级（优等）”，其他的归为“第2层级（次等）”。有时如果颗粒度不够，也可以用“二四六八十”法则”。
如何应用分层
分层的最大作用是帮我们看清楚：到底谁是主力 ，谁是吊车尾。从而指导业务，从人海战术向精兵简政思考。
根据分层的结果找出差距，进而提出（假设）差异背后可能的原因，通过其它方式进行
应用 ：客户分析，目前系统中客户超5000个，为了更好的了解客户结构，可以通过分层分析的方法对这5000个客户进行分层，分层的方式通过年销售规模，可以按照累计规模排序，一般采用4-6个层级，每个层级可以给一个标签。例如王者客户，腰部客户，mini客户等。分层后，便可以针对性的进行分析，例如客户层级的销售占比，变动，各层级客户的销售构成，结合其它方法就可以有较全面的分析
5.漏斗分析（待补充）
6.指标拆解（待补充）
7.相关性分析（待补充）
What ：两个（或多个）因素之间的关系。例如员工人数与销售额，市场推广与销售业绩，天气和销售表现等
很多因素我们直观的感觉到之间有联系，相互影响，但具体的关系是什么，如何产品影响的，可以通相关性分析来量化。
例如，客户开拓中拜访客户的次数和客户成交是否有关系？
拜访次数多，表明客户也感兴趣，所以成功几率大
拜访这么多，客户还不成交，成功几率不大
客户成交和拜访关系不太大，主要看你是否能打动他
How ：两种联系：直接关系，间接关系
直接关系 ：整体指标与部分指标的关系——结构分析，例如销售业绩与各中心的业绩
主指标与子指标的关系——拆解分析，例如总销售规模和客户数量与客户销售规模
前后步骤间的关系——漏斗分析：例如销售目标和项目覆盖率，储备率，签约等因素间的关系
联系中，指标之间出现一致性的变化，基本是正常，如果出现相反的变动，则需要关注，这可能是问题所在
间接关系 ：要素之间没有直接的联系，但存在逻辑上的连接。例如推广多了，知名度上市，进而销售额上升。
由于关系非显性，需要通过处理进行评价，常用的就是散点图和excel中的相关系数法
在明确相关性后，就可以通过改变其中一个变量来影响和控制另一个变量的发展。
注意：相关性分析也存在很大的局限。主要体现在相关性并不等同因果性。例如十年前你在院子里种了一颗树，你发现树每天的高度和中国近十年GDP的增速高度相关，然后这两者间并没有什么实质性的联系。此次相关性分析过程中一定注意要找到关联的逻辑自洽。
8.标签分析（待补充）
9.
D. 关于数据排序的统计方法
卡方分析是检验差异性的，32.81%这个比例的话很难得出主要是心理过程构成啊。。
直接排序用占比最高说明的话，是描述性统计范围。