Map階段(MapTask)： 切片(Split)-----讀取數據(Read)-------交給Mapper處理(Map)------分區和排序(sort)
Reduce階段(ReduceTask): 拷貝數據(copy)------排序(sort)-----合并(reduce)-----寫出(write)
1、Map task讀取：
框架調用InputFormat類的子類讀取HDFS中文件數據，把文件轉換為InputSplit。
默認，文件的一個block對應一個InputSplit，一個InputSplit對應一個map task。
一個InputSplit中的數據會被RecordReader解析成<k1,v1>。
默認，InputSplit中的一行解析成一個<k1,v1>。
默認，v1表示一行的內容，k1表示偏移量。
map：
框架調用mapper 類中的map方法，接收<k1,v1>輸出<k2,v2>，有多少個<k1,v1>，就執行多少次map分區： 框架對mapp的輸出進行分區，分區的目的是確定哪些<k2,v2>進入哪個reduce task。默認只有一個分區。
排序分組：框架對不同分區中的<k2,v2>進行排序分組.排序是按照k2進行排序。分組指的是相同k2的v2分到一個組中。分組不會減少<k2,v2>的數量。（快速排序）
combiner:可以在map task中對<k2,{v2}>執行reduce歸約。
寫入本地：框架對map的輸出寫入到Linux本地磁盤
2、reduce taskshuffle：
框架根據map不同分區中的數據，通過網絡copy到不同的reduce節點合并
排序分組：每個reduce會把多個map傳來的<k2,{v2}>進行合并排序分組（歸并排序）
reduce：框架調用reduce<k2,v2s>,有多少個分組就回執行多少回reduce
寫入HDFS:
框架對reduce輸出的數據寫入到hdfs中
快速排序：
個人理解：
就是歸位，分區，遞歸
比如： 4，6，9，2，1，3，8 這個數組，要對它使用快速排序
首先，選第一個 4 對它進行歸位 ，依次和4進行比較得到
左邊： 2，1，3
右邊：6，9，8
這樣我們就的得到了 2，1，3，4，6，9，8
然后在對兩邊進行遞歸的操作。
python 實現
def partition(li, left, right):tmp = li[left]# 當兩邊搜索并沒有重合的時候就進行雙向查找while left < right:# 這一級兩個判斷條件# 因為li[right] >= tmp退出說明在right出找到了小于tmp的值，這樣填到left就行了# 因為left < right退出是因為left右側的所有值都大于tmp，left已經和right重合了while left < right and li[right] >= tmp: # left有空缺，需要right小于tmp的值來填補right = right - 1 # 往前一位接著找li[left] = li[right] # 將右邊的數寫到左邊空缺處# 找到之后，right出現空缺，應從left找比tmp大的數填到rightwhile left < right and li[left] <= tmp:left = left + 1li[right] = li[left]# 當雙向查找兩邊重合時侯，left=right，將值寫入li[left] = tmpreturn lili = [5, 7, 4, 6, 3, 1, 2, 9, 8]
result = partition(li, 0, len(li)-1)
print(result)def quick_sort(li, left, right):if left < right: # 至少兩個元素mid = partition(li, left, right)# 拿到mid之后就能對兩邊的部分進行相同的整理quick_sort(li, left, mid-1)quick_sort(li, mid+1, right)li = [5,7,4,6,3,1,2,9,8]
quick_sort(li, 0, len(li)-1)
歸并排序：
是將數組按 left mid right 劃分成兩個部分，要求每個部分是有序的，然后假設有兩個指針指在，兩個部分的第一個位置，開始比較，較小的被放到一個臨時集合中，指針移動到下一個位置，然后繼續比較，直到一方沒有下一個值 ，另一方剩下的就是最大的一部分直接放在臨時集合最后，整個排序完成。
python 實現
# 實現一次歸并的過程
# 前提是已經拿到兩個有序子的列表
def merge(li, low, mid, high):""":param li:列表:param low:第一段有序子列表起始位:param mid:第一段有序子列表終止位:param high:第二段有序子列表終止位:return:一次歸并操作之后的整個列表"""# i,j開始分別指向兩個有序子序列的起始位i = lowj = mid + 1ltmp = [] # 存儲結果用while i<=mid and j<=high: # 只要兩個有序子序列都有數if li[i] < li[j]:ltmp.append(li[i])i = i + 1else:ltmp.append(li[j])j = j + 1# 兩部分中有一部分拿光了while i <= mid: # 說明后面的拿光了ltmp.append(li[i])i = i + 1while j <= high: # 說明前面的拿光了ltmp.append(li[j])j = j + 1li[low:high+1] = ltmp # 將結果寫回去li = [0,2,4,6,8,1,3,5,7,9]
merge(li, 0, 4, len(li)-1)
)
