mergesort演算法

A. 歸並排序時間復雜度是什麼

歸並排序(MERGE-SORT)時間復雜度是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。

歸並演算法採用分治法，將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

其實現方式：先把待排序區間以中點二分；接著把左邊子區間排序；再把右邊子區間排序；最後把左區間和右區間用一次歸李廳並操作合並成有序的區間。

合並排序又稱為歸並排序演算法，是比較排序中時間復雜度最低巧磨的演算法（已經理論證明）。也孝擾斗是充分利用了分治思想，分而治之，將復雜重復的工作不斷進行分解至最小單元，而後逐層向上匯總，就像復雜的行政結構。

B. 歸並排序是如何進行的

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}排序演算法是《唯禪數據結構與演算法》中最基本的演算法之一。液山渣排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。以下是歸並排序演算法：
歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
作為一種典型的分而治之思想的演算法應用，鬧悄歸並排序的實現由兩種方法：
自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；自下而上的迭代；在《數據結構與演算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對於遞歸法，作者卻認為：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而，在 JavaScript 中這種方式不太可行，因為這個演算法的遞歸深度對它來講太深了。
說實話，我不太理解這句話。意思是 JavaScript 編譯器內存太小，遞歸太深容易造成內存溢出嗎？還望有大神能夠指教。
和選擇排序一樣，歸並排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是 O(nlogn) 的時間復雜度。代價是需要額外的內存空間。
2. 演算法步驟申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；
重復步驟 3 直到某一指針達到序列尾；
將另一序列剩下的所有元素直接復制到合並序列尾。
3. 動圖演示
代碼實現JavaScript實例 function mergeSort(arr) { // 採用自上而下的遞歸方法var len = arr.length;if(len < 2) { return arr;}var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle);return merge(mergeSort(left), mergeSort(right));}function merge(left, right){var result = [];while (left.length && right.length) { if (left[0] <= right[0]) {result.push(left.shift()); } else {result.push(right.shift()); }}while (left.length) result.push(left.shift());while (right.length) result.push(right.shift());return result;}Python實例 def mergeSort(arr):import mathif(len(arr)<2): return arrmiddle = math.floor(len(arr)/2)left, right = arr[0:middle], arr[middle:]return merge(mergeSort(left), mergeSort(right))def merge(left,right):result = []while left and right: if left[0] <= right[0]:result.append(left.pop(0)) else:result.append(right.pop(0));while left: result.append(left.pop(0))while right: result.append(right.pop(0));return resultGo 實例 func mergeSort(arr []int) []int { length := len(arr) if length < 2 {return arr } middle := length / 2 left := arr[0:middle] right := arr[middle:] return merge(mergeSort(left), mergeSort(right))}func merge(left []int, right []int) []int { var result []int for len(left) != 0 && len(right) != 0 {if left[0] <= right[0] {result = append(result, left[0])left = left[1:]} else {result = append(result, right[0])right = right[1:]} } for len(left) != 0 {result = append(result, left[0])left = left[1:] } for len(right) != 0 {result = append(result, right[0])right = right[1:] } return result}Java實例 public class MergeSort implements IArraySort {@Overridepublic int[] sort(int[] sourceArray) throws Exception { // 對 arr 進行拷貝，不改變參數內容 int[] arr = Arrays.Of(sourceArray, sourceArray.length); if (arr.length < 2) {return arr; } int middle = (int) Math.floor(arr.length / 2); int[] left = Arrays.OfRange(arr, 0, middle); int[] right = Arrays.OfRange(arr, middle, arr.length); return merge(sort(left), sort(right));}protected int[] merge(int[] left, int[] right) { int[] result = new int[left.length + right.length]; int i = 0; while (left.length > 0 && right.length > 0) {if (left[0] <= right[0]) {result[i++] = left[0];left = Arrays.OfRange(left, 1, left.length);} else {result[i++] = right[0];right = Arrays.OfRange(right, 1, right.length);} } while (left.length > 0) {result[i++] = left[0];left = Arrays.OfRange(left, 1, left.length); } while (right.length > 0) {result[i++] = right[0];right = Arrays.OfRange(right, 1, right.length); } return result;}}PHP實例 function mergeSort($arr){$len = count($arr);if ($len < 2) { return $arr;}$middle = floor($len / 2);$left = array_slice($arr, 0, $middle);$right = array_slice($arr, $middle);return merge(mergeSort($left), mergeSort($right));}function merge($left, $right){$result = [];while (count($left) > 0 && count($right) > 0) { if ($left[0] <= $right[0]) {$result[] = array_shift($left); } else {$result[] = array_shift($right); }}while (count($left)) $result[] = array_shift($left);while (count($right)) $result[] = array_shift($right);return $result;}C實例 int min(int x, int y) {return x < y ? x : y;}void merge_sort(int arr[], int len) {int *a = arr;int *b = (int *) malloc(len * sizeof(int));int seg, start;for (seg = 1; seg < len; seg += seg) { for (start = 0; start < len; start += seg * 2) {int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++]; } int *temp = a; a = b; b = temp;}if (a != arr) { int i; for (i = 0; i < len; i++)b[i] = a[i]; b = a;}free(b);}遞歸版：
實例 void merge_sort_recursive(int arr[], int reg[], int start, int end) {if (start >= end) return;int len = end - start, mid = (len >> 1) + start;int start1 = start, end1 = mid;int start2 = mid + 1, end2 = end;merge_sort_recursive(arr, reg, start1, end1);merge_sort_recursive(arr, reg, start2, end2);int k = start;while (start1 <= end1 && start2 <= end2) reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];while (start1 <= end1) reg[k++] = arr[start1++];while (start2 <= end2) reg[k++] = arr[start2++];for (k = start; k <= end; k++) arr[k] = reg[k];}void merge_sort(int arr[], const int len) {int reg[len];merge_sort_recursive(arr, reg, 0, len - 1);}C++迭代版：
實例 template<typename T> // 整_或浮__皆可使用,若要使用物件(class)_必__定"小於"(<)的_運算元功能void merge_sort(T arr[], int len) {T *a = arr;T *b = new T[len];for (int seg = 1; seg < len; seg += seg) { for (int start = 0; start < len; start += seg + seg) {int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);int k = low;int start1 = low, end1 = mid;int start2 = mid, end2 = high;while (start1 < end1 && start2 < end2)b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];while (start1 < end1)b[k++] = a[start1++];while (start2 < end2)b[k++] = a[start2++]; } T *temp = a; a = b; b = temp;}if (a != arr) { for (int i = 0; i < len; i++)b[i] = a[i]; b = a;}delete[] b;}遞歸版：
實例 void Merge(vector<int> &Array, int front, int mid, int end) {// preconditions:// Array[front...mid] is sorted// Array[mid+1 ... end] is sorted// Copy Array[front ... mid] to LeftSubArray// Copy Array[mid+1 ... end] to RightSubArrayvector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);int idxLeft = 0, idxRight = 0;LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());RightSubArray.insert(RightSubArray.end(),

C. 歸並排序

歸並排序 （Merge sort，或mergesort），是創建在歸並操作上的一種有效的排序演算法，效率為 。1945 年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。

這裡面提到了兩個概念，分別是 分治（法） 和 遞歸 ，它們是什麼呢？

分治法（Divide and Conquer）是基於多路分支遞歸求和的一種很重要的演算法範式。字面上的解釋是「分而治之」，就是把一個復雜的問題分成兩個或更多凱宏的相同或相似的子問題，再把子問題分成更小的子問題，直到最後子問題可以簡單的直接求解，原問題的解就是子問題的解的合並。這個技巧是很多高效演算法的基礎，如排序演算法中的快速排序和歸並排序，傅立葉變換中的快速傅立葉變換…

分治模式在每層遞歸時都有三個步驟：

遞歸（英語：Recursion），又譯為遞回， 在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況，如函數的定義中使用函數自身的方法。遞歸一詞還較常用於描述以自相似方法重復事物的過程。 例如，當兩面鏡子相互之間睜叢近似平行時，鏡中嵌套的圖像是以無限遞歸的形式出現的。 也可以理解為自我復制的過程。

歸並排序演算法完全遵循分治模式，直觀上，其操作步驟如下：

當待排序的序列長度為 1 時，遞歸「開始回升」，在這種情況下無須作任何工作，因為長度為 1 的每個序列都已排好序。

MERGE 的詳細工作過程如下：

我們必須證明第 12～17 行 for 循環的第一次迭代之前該循環不變式成立，且在該循環的每次迭代時保持該不變式，當循環終止時，該不變式須提供一種有用的性質來證明演算法的正確性。

前面我們分析了分治演算法的過程，我們可以把 MERGE 作為歸並排序演算法中的一個子程序來用。

上面已經對分治法做悉孫櫻了正確性證明，歸並排序的正確性不言而喻。

分治演算法運行時間的遞歸式來自基本模式的三個步驟，即分解、解決和合並。假設 T(n) 是規模為 n 的一個問題的運行時間。若問題規模足夠小，如對某個常量 c，n≤c，則直接求解需要常量時間，可以將其寫成 O(1)。假設把原問題分解成 a 個子問題，每個子問題的規模是原問題的 1/b。為了求解一個規模為 n/b 的子問題，需要 T(n/b) 的時間，所以需要 aT(n/b) 的時間來求解 a 個子問題。如果分解問題成子問題需要時間 D(n)，合並子問題的解成原問題的解需要時間 C(n)，那麼得到遞歸式：

現在我們來討論歸並排序。假定問題規模是 2 的冪（不是 2 的冪時也能正確地工作），歸並排序一個元素的時間是常量，當有 n>1 個元素時，分解運行的時間如下：

為了分析歸並排序，我們可以將 D(n) 與 C(n) 相加，即把一個 函數與另一個 函數相加，得到的和是一個 n 的線性函數，即 。把它與來自「解決」步驟的項 2T(n/2) 相加，將給出歸並排序的最壞情況的運行時間

將遞歸式重寫，得到

其中，常量 c 代表求解規模為 1 的問題所需要的時間以及在分解步驟與合並步驟處理每個數組元素所需要的時間。(相同的常量一般不可能剛好即代表求解規模為 1 的問題的時間又代表分解步驟與合並步驟處理每個數組元素的時間。通過假設 c 為這兩個時間的較大者並認為我們的遞歸式將給出運行時間的一個上界，或者通過假設 c 為這兩個時間的較小者並認為我們的遞歸式將給出運行時間的下界，我們可以暫時迴避這個問題。兩個界的階都是 ，合在一起將給出運行時間為 )。

求解遞歸式的過程如下圖所示：

可以看出，樹根 cn 通過遞歸分解，直到規模降為 1 後，每個子問題只要代價 c。分解步驟一共經歷了 次，即樹高為 層，每層的代價為 cn，因此總代價為 。

上面我們已經知道了，總代價為 ，忽略低階項和常量 c，歸並排序的時間復雜度為 O(nlogn)。

歸並排序的合並函數，在合並兩個有序數組為一個有序數組時，需要藉助額外的存儲空間，但是這個申請額外的內存空間，會在合並完成之後釋放，因此，在任意時刻，只會有一個臨時的內存空間在使用，臨時內存空間最大也不會超過 n 個數據的大小，所以空間復雜度是 O(n)。

Javascript 遞歸版

Go

迭代版

遞歸版

D. 什麼叫歸並演算法

合並排序（MERGE SORT）是又一類不同的排序方法，合並的含義就是將兩個或兩個以上的有序數據序列合並成一個新的有序數據序列，因此它又叫歸並演算法。它的基本思想就是假設數組A有N個元素，那麼可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然後再兩兩合並，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合並，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法稱為2—路合並排序。
例如數組A有7個數據，分別是： 49 38 65 97 76 13 27，那麼採用歸並排序演算法的操作過程如圖7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由長度為1的7個子序列組成
第一次合並之後 [38 49] [65 97] [13 76] [27]
看成由長度為1或2的4個子序列組成
第二次合並之後 [38 49 65 97] [13 27 76]
看成由長度為4或3的2個子序列組成
第三次合並之後 [13 27 38 49 65 76 97]
合並演算法的核心操作就是將一維數組中前後相鄰的兩個兩個有序序列合並成一個有序序列。合並演算法也可以採用遞歸演算法來實現，形式上較為簡單,但實用性很差。合並演算法的合並次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合並次數是2次,當有5到8個元素時,合並次數是3次,當有9到16個元素時,合並次數是4次，按照這一規律,當有N個子序列時可以推斷出合並的次數是X(2 >=N,符合此條件的最小那個X)。
其時間復雜度為：O(nlogn).所需輔助存儲空間為：O(n)
歸並演算法如下：
long merge(long *A,long p,long q,long r)
{
long n1,n2,i,j,k;
long *L,*R;
n1=q-p+1;
n2=r-q;
L=(long *)malloc((n1+2)*sizeof(long));
R=(long *)malloc((n2+2)*sizeof(long));
for(i=1;i<=n1;i++)
L=A[p+i-1];
for(j=1;j<=n2;j++)
R[j]=A[q+j];
L[n1+1]=R[n2+1]=RAND_MAX;
i=j=1;
for(k=p;k<=r;k++)
{
if(L<=R[j])
{
A[k]=L;
i++;
}
else
{
A[k]=R[j];
j++;
}
}
free(L);
free(R);
return 0;
}
long mergesort(long *A,long p,long r)
{
long q;
if(p<r)
{
q=(p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
return 0;
}

E. 中位數演算法

樓上才是白痴，自己什麼也不懂不要說的別人也是什麼也不懂。
就是因為有了你們這種人，世界多花了巨額的代價來多做不必要的工作。
很明顯樓主不是你這樣的。
實數的排序演算法復雜度是o(nlogn)，這個中位數可以做到o(n)
下面我來說明這個演算法的過程。
演算法是基於歸並排序（merge-sort）的更改。
把中位數更改為等價的敘述。無序的n個數中的第int(n/2)大的元素。(k=int(n/2))
1.隨機化數據，這樣可以保證因為輸出時候的對稱性（可能的順序輸入）而造成的演算法退化。
for
(int
i=number.count;i>=0;i--)
swap(number[i],number[random(0,i-1)]);//swap，交換，random，0，k閉區間的隨機數。
2.歸並排序主過程。
mergesort(a,b,k)//尋找number數組中從下標a到下標b的元素中的第k大的元素。
{
t=number[a];
把這a,b中的元素從排，使a~p-1的元素比t小，p+1~b的元素比t大。number[p]=t;//o(n)，這步你構造吧。不是很困難，偽代碼不寫太多。
//此時比t小元素有p-1-a+1=p-a個,
//分情況，如果k=p-a+1,返回t
//如果k>p-a+1,返回mergesort(p+1,b,k-(p-a+1))
//如果k
評論
0
0
0
載入更多

F. Python實現的幾個常用排序演算法實例

#encoding=utf-8
importrandom
fromimport
defdirectInsertSort(seq):
"""直接插入排序"""
size=len(seq)
foriinrange(1,size):
tmp,j=seq[i],i
whilej>0andtmp<seq[j-1]:
seq[j],j=seq[j-1],j-1
seq[j]=tmp
returnseq
defdirectSelectSort(seq):
"""直接選擇排序"""
size=len(seq)
foriinrange(0,size-1):
k=i;j=i+1
whilej<size:
ifseq[j]<seq[k]:
k=j
j+=1
seq[i],seq[k]=seq[k],seq[i]
returnseq
defbubbleSort(seq):
"""冒泡排序"""
size=len(seq)
foriinrange(1,size):
forjinrange(0,size-i):
ifseq[j+1]<seq[j]:
seq[j+1],seq[j]=seq[j],seq[j+1]
returnseq
def_divide(seq,low,high):
"""快速排序劃分函數"""
tmp=seq[low]
whilelow!=high:
whilelow<highandseq[high]>=tmp:high-=1
iflow<high:
seq[low]=seq[high]
low+=1
whilelow<highandseq[low]<=tmp:low+=1
iflow<high:
seq[high]=seq[low]
high-=1
seq[low]=tmp
returnlow
def_quickSort(seq,low,high):
"""快速排序輔助函數"""
iflow>=high:return
mid=_divide(seq,low,high)
_quickSort(seq,low,mid-1)
_quickSort(seq,mid+1,high)
defquickSort(seq):
"""快速排序包裹函數"""
size=len(seq)
_quickSort(seq,0,size-1)
returnseq
defmerge(seq,left,mid,right):
tmp=[]
i,j=left,mid
whilei<midandj<=right:
ifseq[i]<seq[j]:
tmp.append(seq[i])
i+=1
else:
tmp.append(seq[j])
j+=1
ifi<mid:tmp.extend(seq[i:])
ifj<=right:tmp.extend(seq[j:])
seq[left:right+1]=tmp[0:right-left+1]
def_mergeSort(seq,left,right):
ifleft==right:
return
else:
mid=(left+right)/2
_mergeSort(seq,left,mid)
_mergeSort(seq,mid+1,right)
merge(seq,left,mid+1,right)
#二路並歸排序
defmergeSort(seq):
size=len(seq)
_mergeSort(seq,0,size-1)
returnseq
if__name__=='__main__':
s=[random.randint(0,100)foriinrange(0,20)]
prints
print"
"
printdirectSelectSort((s))
printdirectInsertSort((s))
printbubbleSort((s))
printquickSort((s))
printmergeSort((s))

G. 中位數演算法

此題的中位數演算法應該是將數據從小到大重新排列。n
是樣本數
這里樣本數為30.是偶數
則樣本中位數m=1/2【（x(15)+x(15+1)】
這里就是m=1/2【x(30/2)+x(30/2+1)】
其中x後面小括弧的是下標。我從這上面表示不出來。於是結果就是m=1/2(18+18)=18
明白了么？
中位數的計算主要是排序，然後根據樣本數量是奇數還是偶數，確定公式代入公式找到中位數就可以了

H. 歸並排序中演算法MergeSort（）是怎麼回事

-MergeSort(R,low,mid);和MergeSort(R,mid+1,high);是對R（low...mid）和R（mid+1...high）進行排序嗎？？
不是排序，而是分裂。分別對左右兩邊進行折半分裂，直到只剩下一個元素。歸並排序是Divide and Conquer演算法，分裂+合並。先遞歸調用MergeSort分裂直至只剩一個元素，然後調Merge輔助函數合並兩個有序數組（只有一個元素的數組也是有序數組）。

-我怎麼認為只是把例如R(N)={0,1,3,2}，最終分解為0,1,3,2呢？？
的確先是分成單個元素的，然後{0}與{1}兩個數組通過Merge合並成為{0, 1}；{3}與{2}兩個數組合並成{2, 3}。然後退到遞歸上一層，調Merge合並{0, 1}和{2, 3]兩個有序數組為{0, 1, 2, 3}。

歸並排序的思想就是每次合並兩個有序數組。

再舉個例子：{5, 3, 6, 1}。
MergeSort分裂為{5, 3}和{6, 1}
MergeSort分裂{5, 3}為{5}, {3}；分裂{6, 1}為{6}, {1}
現在遞歸已經到頭，因為繼續分的話low>high
所以運行Merge，合並{5}, {3}為{3, 5}；合並{6}, {1}為{1, 6}
退到上一層遞歸，合並{3, 5}和{1, 6}為{1, 3, 5, 6}。

其實真正的排序步驟是在Merge里：怎樣合並兩個有序數組。

I. 大數據中的歸並排序(Merge Sort)

最近在研究大數據的分治思想，很多場景計算得出的中間結果都是「內部有序，外部無序」，這時候就要用到「歸衫襲並排序」演算法將多個這樣的結果集合歸並為一個有序的集合。於是就復習了一下「歸並排序」。

在大數據場景中或畝兄，數據量遠大於計算機的內存，磁碟和網路的IO又是無法解決的瓶頸，就需要用到分治思想。
比如有1000G的中國2020年某電商平台用戶消費總金額數據。數據格式是用戶名：消費總金額。所有數據都是無序的。現在有1台磁碟5T/內存8G（程序可用內存約為5G多）的計算機。如何將數據按消費總金額從大到小排序輸出？

a. 從有序隊列中取出第一個元素。
b. 將此元素數據寫入輸出的文件中，並從此元素所屬的數組中的下一個元素放入有序耐耐隊列。
c. 重復步驟a，b直到某個數組元素耗盡，從這個數組所屬的5G文件中，繼續載入25M數據到內存中。
d. 重復步驟a，b，c直到所有5G文件的數據全部載入到內存中，並寫入到輸出文件。