1. 分治法：分治模型在每層遞歸的時都有三個步驟：

　　a.分解原問題為若干個子問題，這些子問題是原問題的規(guī)模較小的實例；

　　b. 解決這些子問題，遞歸地求解各子問題的規(guī)模足夠小，則直接求解；

　　c. 合并這些子問題的解 成 原問題的解。

2. 歸并排序算法完全遵循分治模式。

　　a. 分解：分解待排序的n個元素的序列成各具 n/2 個元素的子序列

　　b. 解決：使用歸并排序遞歸地排序子序列

　　c. 合并：合并兩個已經(jīng)排序的子序列以產(chǎn)生已排序的答案。

3.歸并排序算法圖示，實話說我沒看懂第一個圖。。但是第二個圖很好理解

?

?

?

4. 偽代碼

MERGE(A, p, q, r)n1 = q-p+1n2 = r-q//let L[1....n1+1] and R[1....n2+1] be new arraysfor i =1 to n1L[i] = A[p+i-1]for j=1 to n2R[j] = A[q+j]L[n1+1] = ∞L[n2+1] = ∞i=1j=1for k =p to rif L[i]<=R[j]A[k] = L[i]i = i + 1elseA[k]=R[j]j = j+1MERGE-SORT(A,p,r)if p < rq =(p+r)/2 //向下取整，不會打那個符號MERGE-SORT(A, p, q)MERGE-SORT(A, q+1, r)MERGE(A, p, q, r)

?

?5. 算法分析：

　　排序就是比較，比較最終都是兩個數(shù)比較

　　直接看MERGE（A, p, q, r）這個算法,這個算法的前提就是假設(shè) A[p] - A[q]是有序的， A[q+1]到A[r]是有序的，那么歸并后肯定是有序的.

　　怎么做到這個前提，就是最終把所有的數(shù)分到最小粒度， 也就是數(shù)組只有一個數(shù)的時候，它一定是有序的， 然后一層一層向上歸并，得到最終的有序序列

6. 代碼實現(xiàn)

　　java　　

void mergeSort(int[] A, int p, int r) {if (p < r) {int q = (int)Math.floor((p + r)/2);mergeSort(A, p, q);mergeSort(A, q+1, r);merge(A, p, q, r);} }void merge(int[] A, int p, int q, int r){int n1 = q - p + 1;int n2 = r - q ;int[] L = new int[n1 + 1];int[] R = new int[n2 + 1];for (int i = 0; i < n1; i++) {L[i] = A[p+i];}for (int j = 0; j < n2; j++) {R[j] = A[q+j+1];}L[n1] = R[n2] = Integer.MAX_VALUE;int i = 0, j = 0;for (int k = 0; k < r - p + 1; k++) {if (L[i] <= R[j]) {A[p+k] = L[i];i++;} else {A[p+k] = R[j];j++;}} }

python

import math import sysdef merge_sort(arr, p, r):if p < r:q = math.floor((p + r) / 2)merge_sort(arr, p, q)merge_sort(arr, q + 1, r)merge(arr, p, q, r)# 0, 5, 10 def merge(arr, p, q, r):n1 = q - p + 1n2 = r - qm = []n = []for i in range(n1):m.append(arr[p+i])for j in range(n2):n.append(arr[q+j+1])m.append(sys.maxsize)n.append(sys.maxsize)i = j = 0for k in range(r - p + 1):if m[i] <= n[j]:arr[p+k] = m[i]i += 1else:arr[p+k] = n[j]j += 1

c語言

// 0, 10 void merge_sort(int arr[], int p, int r) {if(r > p){int q = (p + r) / 2;merge_sort(arr, p, q);merge_sort(arr, q + 1, r);merge(arr, p, q, r);} }// 0, 5, 10 void merge(int arr[], int p, int q, int r) {int n1 = q - p +1;int n2 = r - q;int L[n1+1], R[n2+1];int i, j, k;for(i = 0; i < n1; i++) L[i] = arr[p+i]; for(j = 0; j < n2; j++)R[j] = arr[q+j+1];L[n1] = R[n2] = (unsigned)(~0) >> 1;i = j =0;for(k = 0; k < r - p +1; k++){if(L[i] <= R[j]){arr[p+k] = L[i];i++;}else{arr[p+k] = R[j];j++;}} }

轉(zhuǎn)載于:https://www.cnblogs.com/yeyeck/p/9538394.html

總結(jié)

以上是生活随笔為你收集整理的【算法导论】归并排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。