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%這個比例的話很難得出主要是心理過程構成啊。。
直接排序用佔比最高說明的話，是描述性統計范圍。