-
歸併排序
鎖定
- 中文名
- 歸併排序
- 外文名
- Merge Sort
- 穩定性
- 穩定
- 時間複雜度
- O(n log n)
- 空間複雜度
- T（n)
- 發明者
- 約翰·馮·諾伊曼
歸併排序歸併操作
歸併操作，也叫歸併算法，指的是將兩個順序序列合併成一個順序序列的方法。
如 設有數列{6，202，100，301，38，8，1}
初始狀態：6,202,100,301,38,8,1
第一次歸併後：{6,202},{100,301},{8,38},{1}，比較次數：3；
第二次歸併後：{6,100,202,301}，{1,8,38}，比較次數：4；
第三次歸併後：{1,6,8,38,100,202,301},比較次數：4；
總的比較次數為：3+4+4=11；
逆序數為14；
歸併排序算法描述
歸併操作的工作原理如下：
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置
重複步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接複製到合併序列尾
歸併排序比較
歸併排序是穩定的排序.即相等的元素的順序不會改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括號中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息儘量按輸入的順序排列時很重要。歸併排序的比較次數小於快速排序的比較次數，移動次數一般多於快速排序的移動次數。
歸併排序用途
歸併排序排序
歸併排序求逆序對數
scala代碼：
objectMainextendsApp{
varreverse_pairs = 0//逆序數
defmsort[T](cmp:(T, T) => Boolean)(l:List[T]):List[T] = {
defmerge(l1:List[T], l2:List[T]):List[T]=(l1, l2)match{
case(Nil, _) => l2
case(_, Nil) => l1
case(x::left1, y::left2) =>
if(cmp(x, y))
x::merge(left1, l2)
else{
reverse_pairs += l1.length
y::merge(l1, left2)
}
}
valn = l.length / 2
if(n == 0)
return l
else{
val(l1, l2) = l.splitAt(n)
merge(msort(cmp)(l1), msort(cmp)(l2))
}
}
println(msort((x:Int, y:Int) => x<y)(List(5, 4, 3, 2, 7,6 )))
println(reverse_pairs)
}
//採用自上而下的遞歸方法
public class MergeSort {
private int[] Sort(int[]arr){
//若待排序數組長度<2，則直接返回
if (arr.length<2)
return arr;
int mid=arr.length/2;
return process(Sort(Arrays.copyOfRange(arr,0,mid)),Sort(Arrays.copyOfRange(arr,mid,arr.length)));
}
//合併兩個有序數組
private int[] process(int []arr1,int[]arr2){
int[] re=new int[arr1.length+arr2.length];
//i為arr1的index,j為arr2的index,k為re的index
int i=0,j=0,k=0;
//獲取兩個數組較小元素，填入re內
while (i<arr1.length&&j<arr2.length)
re[k++]=(arr1[i]<arr2[j])?arr1[i++]:arr2[j++];
//若arr1有元素剩餘，全部填入re內
if(i!=arr1.length)
for(int p=i;p<arr1.length;p++)
re[k++]=arr1[p];
//若arr2內有元素剩餘，全部填入re內
if(j!=arr2.length)
for(int p=j;p<arr2.length;p++)
re[k++]=arr2[p];
return re;
}歸併排序示例代碼
歸併排序原理
歸併排序具體工作原理如下（假設序列共有n個元素）：
將上述序列再次歸併，形成floor(n/4)個序列，每個序列包含四個元素
重複步驟2，直到所有元素排序完畢
示例代碼
//歸併排序
func mergeSort(_ arr: inout [Int]) {
var gap = 1;
while gap < arr.count {
mergePass(&arr, gap: gap);
gap *= 2;
}
}
//分解合併序列，gap表示子序列的元素個數
func mergePass(_ arr: inout [Int], gap: Int) {
var i = 0;
let count = arr.count;
while i + 2 * gap - 1 < count {
mergeArray(&arr, low: i, mid: i + gap - 1, high: i + 2 * gap - 1);
i += 2 * gap;
}
//合併剩餘的序列
if i + gap - 1 < count {
mergeArray(&arr, low: i, mid: i + gap - 1, high: count - 1);
}
}
//合併兩個序列
func mergeArray(_ arr: inout [Int], low: Int, mid: Int, high: Int) {
var i = low;
var j = mid + 1;
var k = 0;
var array = Array<Int>(repeating: 0, count: high - low + 1);
while i <= mid && j <= high {
if arr[i] < arr[j] {
array[k] = arr[i];
i += 1;
k += 1;
} else {
array[k] = arr[j];
j += 1;
k += 1;
}
}
while i <= mid {
array[k] = arr[i];
i += 1;
k += 1;
}
while j <= high {
array[k] = arr[j];
j += 1;
k += 1;
}
//將排序好的序列複製回原數組
k = 0;
for i in low...high {
arr[i] = array[k];
k += 1;
}
}
var array = [2, 5, 8, 9, 10, 4, 3, 16, 1, 7, 8];
mergeSort(&array);
print(array);
func mergeSort(r []int) []int {
length := len(r)
if length <= 1 {
return r
}
num := length / 2
left := mergeSort(r[:num])
right := mergeSort(r[num:])
return merge(left, right)
}
func merge(left, right []int) (result []int) {
l, r := 0, 0
for l < len(left) && r < len(right) {
if left[l] < right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
}
result = append(result, left[l:]...)
result = append(result, right[r:]...)
return
}
Java語言
package MergeSort;
public class MergeSort {
public static int[] mergeSort(int[] nums, int l, int h) {
if (l == h)
return new int[] { nums[l] };
int mid = l + (h - l) / 2;
int[] leftArr = mergeSort(nums, l, mid); //左有序數組
int[] rightArr = mergeSort(nums, mid + 1, h); //右有序數組
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序數組
int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length)
newNum[m++] = leftArr[i++];
while (j < rightArr.length)
newNum[m++] = rightArr[j++];
return newNum;
}
public static void main(String[] args) {
int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
int[] newNums = mergeSort(nums, 0, nums.length - 1);
for (int x : newNums) {
System.out.println(x);
}
}
}
C#語言
public static void Sort(int[] a, int f, int e)
{
if (f < e)
{
int mid = (f + e) / 2;
Sort(a, f, mid);
Sort(a, mid + 1, e);
MergeMethid(a, f, mid, e);
}
}
private static void MergeMethid(int[] a, int f, int mid, int e)
{
int[] t = new int[e - f + 1];
int m = f, n = mid + 1, k = 0;
while(n <= e && m <= mid)
{
if (a[m] > a[n]) t[k++] = a[n++];
else t[k++] = a[m++];
}
while (n < e + 1) t[k++] = a[n++];
while (m < mid + 1) t[k++] = a[m++];
for (k = 0, m = f; m < e + 1; k++, m++) a[m] = t[k];
}
def MergeSort(lists): if len(lists) <= 1: return lists num = int( len(lists) / 2 ) left = MergeSort(lists[:num]) right = MergeSort(lists[num:]) return Merge(left, right) def Merge(left,right): r, l=0, 0 result=[] while l<len(left) and r<len(right): if left[l] <= right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += list(left[l:]) result += list(right[r:]) return result print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])
#include <stdlib.h>
#include <stdio.h>
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
int i = startIndex, j=midIndex+1, k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sourceArr[i] > sourceArr[j])
tempArr[k++] = sourceArr[j++];
else
tempArr[k++] = sourceArr[i++];
}
while(i != midIndex+1)
tempArr[k++] = sourceArr[i++];
while(j != endIndex+1)
tempArr[k++] = sourceArr[j++];
for(i=startIndex; i<=endIndex; i++)
sourceArr[i] = tempArr[i];
}
//內部使用遞歸
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
int midIndex;
if(startIndex < endIndex)
{
midIndex = startIndex + (endIndex-startIndex) / 2;//避免溢出int
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}
int main(int argc, char * argv[])
{
int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
int i, b[8];
MergeSort(a, b, 0, 7);
for(i=0; i<8; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
PHP語言
function msort(array &$arr, $low, $high){
if($low>=$high)
return;
$mid = floor(($low+$high)/2);
msort($arr, $low, $mid);
msort($arr, $mid+1, $high);
mmerge($arr, $low, $mid, $high);
}
function mmerge(array &$arr, $low, $mid, $high){
//複製數據備用
$aa = [];
for($k=$low; $k<=$high; $k++){
$aa[$k] = $arr[$k];
}
//合併數組
$i = $low;//左邊起點
$j = $mid+1;//右邊起點
for($k=$low; $k<=$high; $k++){
if($i>$mid){//左邊處理完成，使用右邊
$arr[$k] = $aa[$j++];
}elseif($j>$high){//右邊處理完成，使用左邊
$arr[$k] = $aa[$i++];
}elseif($aa[$i]>$aa[$j]){//左邊比右邊大，用右邊
$arr[$k] = $aa[$j++];
}else{
$arr[$k] = $aa[$i++];
}
}
}
$a = [4,3,6,7,5,1,9,0,2];
msort($a, 0, count($a)-1);
print_r($a);Pascal語言
program mergesort_1;
const maxn=7;
type
arr=array[1..maxn] of integer;
var
a,b,c:arr;
i:integer;
procedure merge(r:arr; l,m,n:integer; var r2:arr);
var
i,j,k,p:integer;
begin
i:=l;
j:=m+1;
k:=l-1;
while (i<=m) and (j<=n) do begin
k:=k+1;
if r[i]<=r[j] then begin
r2[k]:=r[i];
i:=i+1
end
else begin
r2[k]:=r[j];
j:=j+1;
end
end;
if i<=m then for p:=i to m do begin
k:=k+1;
r2[k]:=r[p];
end;
if j<=n then for p:=j to n do begin
k:=k+1;
r2[k]:=r[p];
end;
end;
procedure mergesort(var r,r1:arr; s,t:integer);
var
k:integer; c:arr;
begin
if s=t then r1[s]:=r[s]
else begin
k:=(s+t)div2;
mergesort(r,c,s,k);
mergesort(r,c,k+1,t);
merge(c,s,k,t,r1)
end;
end;
begin
write('Enterdata:');
for i:=1 to maxn do read(a[i]);
mergesort(a,b,1,maxn);
for i:=1 to maxn do write(b[i]:9);
writeln;
end.
//============================================
program mergesort_2;
const max=100000;
var
a,r:array[1..max] of longint;
n,i:longint;
procedure msort(s,t:longint);
var
m,i,j,k:longint;
begin
if s=t then exit;
m:=(s+t) div 2;
msort(s,m);
msort(m+1,t);
i:=s;
j:=m+1;
k:=s;
while (i<=m) and (j<=t) do begin
if a[i]<a[j] then begin
r[k]:=a[i];
inc(i);
inc(k);
end
else begin
r[k]:=a[j];
inc(j);
inc(k);
end;
end;
while i<=m do begin
r[k]:=a[i];
inc(i);
inc(k);
end;
while j<=t do begin
r[k]:=a[j];
inc(j);
inc(k);
end;
for i:=s to t do a[i]:=r[i];
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
msort(1,n);
for i:=1 to n do writeln(a[i]);
end.
Sub MergeSort(Array() As Integer, First As Integer, Last As Integer)
Dim mid As Integer = 0
If first<last Then
mid = (first+last)\ 2
MergeSort(Array, first, mid);
MergeSort(Array, mid+1, last);
Merge(Array, first, mid, last);
End If
End Sub
/*
以下示例代碼實現了歸併操作。array[]是元素序列，其中從索引p開始到q位置，按照升序排列，同時，從(q+1)到r也已經按照升序排列，merge()函數將把這兩個已經排序好的子序列合併成一個排序序列。結果放到array中。
*/
/**
* 0 <= p <= q < r, subarray array[p..q] and array[q+1..r] are already sorted.
* the merge() function merges the two sub-arrays into one sorted array.
*/
void Merge(int array[], int p, int q, int r)
{
int i,k;
int begin1,end1,begin2,end2;
int* temp = (int*)malloc((r-p+1)*sizeof(int));
begin1 = p;
end1 = q;
begin2 = q+1;
end2 = r;
k = 0;
while((begin1 <= end1)&&( begin2 <= end2))
{
if(array[begin1] <= array[begin2]){
temp[k] = array[begin1];
begin1++;
}
else
{
temp[k] = array[begin2];
begin2++;
}
k++;
}
while(begin1<=end1 || begin2<=end2)
{
if(begin1<=end1)
{
temp[k++] = array[begin1++];
}
if(begin2<=end2)
{
temp[k++] = array[begin2++];
}
}
for (i = 0; i < =(r - p); i++)
array[p+i] = temp[i];
free(temp);
}
使用遞歸的代碼如下。優點是描述算法過程思路清晰，缺點是使用遞歸，mergeSort()函數頻繁地自我調用。長度為n的數組最終會調用mergeSort()函數 2n-1次，這意味着一個長度超過1500的數組會在Firefox上發生棧溢出錯誤。可以考慮使用迭代來實現同樣的功能。
function merge(left, right){
var result=[];
while(left.length>0 && right.length>0){
if(left[0]<right[0]){
/*shift()方法用於把數組的第一個元素從其中刪除，並返回第一個元素的值。*/
result.push(left.shift());
}else{
result.push(right.shift());
}
}
return result.concat(left).concat(right);
}
function mergeSort(items){
if(items.length == 1){
return items;
}
var middle = Math.floor(items.length/2),
left = items.slice(0, middle),
right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
非遞歸算法 （javaScript）
function mergePass(arr = [], temp = new Array(arr.length), N = arr.length, length = 1){ // 將每個元素看作是相鄰的數組長度為1。
let t; // 迭代深度。
for (t = 0; Math.pow(2,t) < N; t++, length *= 2) { // 每次跳過的長度翻倍。
const even = t%2 === 0; // 複用 arr 和 temp 來回賦值。
for (let left = 0; left < N; left += 2 * length) { // 左邊數組起始位置 left 從0開始。
const middle = left + length < N ? left + length : left; // 右邊數組起始位置 middle 就是left + 一個數組長度length 但是不要超過 N 。
const right = left + (2 * length) < N ? left + (2 * length) : N; // 右邊界 right 就是 left + 兩個數組長度。
merge(even ? arr : temp, even ? temp : arr, left, middle, right); // 合併每兩個相鄰的數組。
}
}
if(t % 2 === 0){
return arr;//返回arr
}
return temp; // 返回 temp 。
}
function merge(arr, temp, left, middle, right){
const leftEnd = middle - 1; // 通過右邊數組的起始位置得到左邊數組的結束位置。
while (left <= leftEnd && middle < right) { // 如果‘指針’沒有越界。
if (arr[left] > arr[middle]) { // 如果左邊數組第一個元素比右邊數組第一個元素大。
temp[left + middle - leftEnd -1] = arr[middle++]; // 將右邊數組最小的放入有序數組 temp（初始值為空)。
} else {
temp[left + middle - leftEnd -1] = arr[left++]; // 將左邊數組最小的放入有序數組 temp（初始值為空)。
}
}
while(left > leftEnd && middle < right){ // 如果左邊數組放完了，右邊數組還有元素。
temp[left + middle - leftEnd -1] = arr[middle++]; // 那麼依次將右邊數組剩餘的元素放入 temp 。
}
while(left <= leftEnd && middle >= right){ // 如果右邊數組放完了，左邊數組還有元素
temp[left + middle - leftEnd -1] = arr[left++]; // 那麼依次將左邊數組剩餘的元素放入 temp 。
}
}
非遞歸算法（C++）
#include<iostream>
#include<ctime>
#include<cstring>
#include<cstdlib>
using namespace std;
/**將a開頭的長為length的數組和b開頭長為right的數組合並n為數組長度，用於最後一組*/
void Merge(int* data,int a,int b,int length,int n){
int right;
if(b+length-1 >= n-1) right = n-b;
else right = length;
int* temp = new int[length+right];
int i=0, j=0;
while(i<=length-1 && j<=right-1){
if(data[a+i] <= data[b+j]){
temp[i+j] = data[a+i];i++;
}
else{
temp[i+j] = data[b+j];
j++;
}
}
if(j == right){//a中還有元素，且全都比b中的大,a[i]還未使用
memcpy(temp + i + j, data + a + i, (length - i) * sizeof(int));
}
else if(i == length){
memcpy(temp + i + j, data + b + j, (right - j)*sizeof(int));
}
memcpy(data+a, temp, (right + length) * sizeof(int));
delete [] temp;
}
void MergeSort(int* data, int n){
int step = 1;
while(step < n){
for(int i=0; i<=n-step-1; i+=2*step)
Merge(data, i, i+step, step, n);
//將i和i+step這兩個有序序列進行合併
//序列長度為step
//當i以後的長度小於或者等於step時，退出
step*=2;//在按某一步長歸併序列之後，步長加倍
}
}
int main(){
int n;
cin>>n;
int* data = new int[n];
if(!data) exit(1);
int k = n;
while(k--){
cin>>data[n-k-1];
}
clock_t s = clock();
MergeSort(data, n);
clock_t e = clock();
k=n;
while(k--){
cout<<data[n-k-1]<<' ';
}
cout<<endl;
cout<<"the algorithm used"<<e-s<<"miliseconds."<<endl;
delete data;
return 0;
}
遞歸算法：
#include<iostream>
using namespace std;
void merge(int *data, int start, int mid, int end, int *result)
{
int i, j, k;
i = start;
j = mid + 1; //避免重複比較data[mid]
k = 0;
while (i <= mid && j <= end) //數組data[start,mid]與數組(mid,end]均沒有全部歸入數組result中去
{
if (data[i] <= data[j]) //如果data[i]小於等於data[j]
result[k++] = data[i++]; //則將data[i]的值賦給result[k]，之後i,k各加一，表示後移一位
else
result[k++] = data[j++]; //否則，將data[j]的值賦給result[k]，j,k各加一
}
while (i <= mid) //表示數組data(mid,end]已經全部歸入result數組中去了，而數組data[start,mid]還有剩餘
result[k++] = data[i++]; //將數組data[start,mid]剩下的值，逐一歸入數組result
while (j <= end) //表示數組data[start,mid]已經全部歸入到result數組中去了，而數組(mid,high]還有剩餘
result[k++] = data[j++]; //將數組a[mid,high]剩下的值，逐一歸入數組result
for (i = 0; i < k; i++) //將歸併後的數組的值逐一賦給數組data[start,end]
data[start + i] = result[i]; //注意，應從data[start+i]開始賦值
}
void merge_sort(int *data, int start, int end, int *result)
{
if (start < end)
{
int mid = start + (end-start) / 2;//避免溢出int
merge_sort(data, start, mid, result); //對左邊進行排序
merge_sort(data, mid + 1, end, result); //對右邊進行排序
merge(data, start, mid, end, result); //把排序好的數據合併
}
}
void amalgamation(int *data1, int *data2, int *result)
{
for (int i = 0; i < 10; i++)
result[i] = data1[i];
for (int i = 0; i < 10; i++)
result[i + 10] = data2[i];
}
int main()
{
int data1[10] = { 1,7,6,4,9,14,19,100,55,10 };
int data2[10] = { 2,6,8,99,45,63,102,556,10,41 };
int *result = new int[20];
int *result1 = new int[20];
amalgamation(data1, data2, result);
for (int i = 0; i < 20; ++i)
cout << result[i] << " ";
cout << endl;
merge_sort(result, 0, 19, result1);
for (int i = 0; i < 20; ++i)
cout << result[i] << " ";
delete[]result;
delete[]result1;
return 0;
}
Const FI='in.txt'; FO='out.txt'; MaxN=10000; Type TIndex=Longint; TDat=Array[0..MaxN]OfTIndex; Var N:TIndex; Dat:TDat; Tmp:TDat; ProcedureMerge(L,Mid,R:TIndex); Var P1,P2:TIndex; E1,E2:TIndex; P:TIndex; I:TIndex; Begin P1:=L; P2:=Mid+1; P:=L; Repeat If(Dat[P1]<=Dat[P2])Then Begin Tmp[P]:=Dat[P1]; Inc(P1); Inc(P); End Else Begin Tmp[P]:=Dat[P2]; Inc(P2); Inc(P); End; Until(P1=Mid+1)Or(P2=R+1); If(P1=Mid+1)Then Begin E1:=P2; E2:=R; End Else Begin E1:=P1; E2:=Mid; End; ForI:=E1ToE2Do Begin Tmp[P]:=Dat[I]; Inc(P); End; End; ProcedureSort(L,R:TIndex); Var Mid:TIndex=0; Begin Mid:=(L+R)Shr1; If(L<Mid)Then Sort(L,Mid); If(Mid+1<R)Then Sort(Mid+1,R); Merge(L,Mid,R); ForMid:=LToRDo Dat[Mid]:=Tmp[Mid]; End; ProcedureInit; Var I:TIndex; Begin FillChar(Dat,SizeOf(Dat),0); Readln(N); ForI:=1ToNDo Read(Dat[I]); End; ProcedureMain; Begin Sort(1,N); End; ProcedureFinal; Var I:TIndex; Begin ForI:=1ToNDo Write(Dat[I],''); Writeln; End; Begin Assign(Input,FI); Assign(Output,FO); Reset(Input); Rewrite(Output); Init; Main; Final; Close(Input); Close(Output); End.
Delphi
歸併排序完整源代碼例子：
//合併子函數
procedureTForm1.MergePass(vardatas:arrayofInteger;left,mid,
right:Integer);
var
tmpArr:arrayofInteger;
arrLen:Integer;
i,k:Integer;
begin1,begin2,end1,end2:Integer;
begin
arrLen:=right-left+1;
SetLength(tmpArr,arrLen);
begin1:=left;
end1:=mid;
begin2:=mid+1;
end2:=right;
k:=0;
while((begin1<=end1)and(begin2<=end2))do
begin
if(datas[begin1]<datas[begin2])then
begin
tmpArr[k]:=datas[begin1];
Inc(begin1);
end
else
begin
tmpArr[k]:=datas[begin2];
Inc(begin2);
end;
inc(k);
end;
while(begin1<=end1)do
begin
tmpArr[k]:=datas[begin1];
Inc(begin1);
Inc(k);
end;
while(begin2<=end2)do
begin
tmpArr[k]:=datas[begin2];
Inc(begin2);
Inc(k);
end;
fori:=0to(right-left)do
begin
datas[left+i]:=tmpArr[i];
end;
end;
//排序主函數，left是數組左下標，0開始。right是數組右下標。
procedureTForm1.MergeSort(vardatas:arrayofInteger;left,right:Integer);
var
mid:Integer;
i:Integer;
begin
mid:=0;
if(left<right)then
begin
mid:=(right+left)div2;
showLog('中間索引：'+inttostr(mid));
MergeSort(datas,left,mid);
MergeSort(datas,mid+1,right);
MergePass(datas,left,mid,right);
showLog('--->'+getArrayString(datas));//顯示數組中間狀態
end;
end;
//調用方法：procedureTForm1.btn1Click(Sender:TObject);
var
inArr:array[0..9]ofInteger;
begin
CopyMemory(@inArr[0],@CTabls[0],SizeOf(Integer)*10);
showLog('輸入數據：'+getArrayString(inArr));
MergeSort(inArr,0,High(inArr));
showLog('輸出數據：'+getArrayString(inArr));
end;
歸併排序複雜度
歸併排序比較佔用內存，但卻是一種效率高且穩定的算法。
改進歸併排序在歸併時先判斷前段序列的最大值與後段序列最小值的關係再確定是否進行復制比較。如果前段序列的最大值小於等於後段序列最小值，則説明序列可以直接形成一段有序序列不需要再歸併，反之則需要。所以在序列本身有序的情況下時間複雜度可以降至O(n)
TimSort可以説是歸併排序的終極優化版本，主要思想就是檢測序列中的天然有序子段（若檢測到嚴格降序子段則翻轉序列為升序子段）。在最好情況下無論升序還是降序都可以使時間複雜度降至為O(n)，具有很強的自適應性。
- | 最好時間複雜度 | 最壞時間複雜度 | 平均時間複雜度 | 空間複雜度 | 穩定性 |
傳統歸併排序 | O(nlogn) | O(nlogn) | O(nlogn) | T(n) | 穩定 |
O(n) | O(nlogn) | O(nlogn) | T(n) | 穩定 | |
TimSort | O(n) | O(nlogn) | O(nlogn) | T(n) | 穩定 |
歸併排序歸併算法
定義
所謂歸併排序是指將兩個或兩個以上有序的數列（或有序表），合併成一個仍然有序的數列（或有序表）。這樣的排序方法經常用於多個有序的數據文件歸併成一個有序的數據文件。歸併排序的算法比較簡單。
基本思想方法：
（1）假設已經有兩個有序數列，分別存放在兩個數組s，r中；並設i，j分別為指向數組的第一個單元的下標；s有n個元素，r有m個元素。
（2）再另設一個數組a，k指向該數組的第一個單元下標。
（3）算法分析（過程）：
proceduremerge(s,r,a,i,j,k); begin i1:=i; j1:=j; k1:=k; while(i1<n)and(j1<m)do ifs[i1]<=r[j1]then begin a[k]:=s[i1]; i1:=i1+1; k:=k+1; end else begin a[k]:=r[j1]; j1:=j1+1; k:=k+1; end; whilei1<=ndo begin a[k]:=s[i1]; i1:=i1+1; k:=k+1; end; whilej1<=mdo begin a[k]:=r[j1]; j1:=j1+1; k:=k+1; end; end;
完整的C++源代碼
#include <iostream>
void Merge(int r[], int r1[], int s, int m, int t)
{
int i = s;
int j = m + 1;
int k = s;
while (i <= m && j <= t)
{
if (r[i] <= r[j])
r1[k++] = r[i++];
else
r1[k++] = r[j++];
}
if (i <= m)
while (i <= m)
r1[k++] = r[i++];
else
while (j <= t)
r1[k++] = r[j++];
for (int n = s; n <= t; n++)
r[n] = r1[n];
}
void MergeSort(int r[], int r1[], int s, int t)
{
if (s < t)
{
int m = (s + t) / 2;
MergeSort(r, r1, s, m);
MergeSort(r, r1, m + 1, t);
Merge(r, r1, s, m, t);
}
}
int main()
{
int r[8] = {10, 3, 5, 1, 9, 34, 54, 565}, r1[8];
MergeSort(r, r1, 0, 7);
for (int q = 0; q < 8; q++)
std::cout << r[q] << std::ends;
return 0;
}
歸併排序的實現方法：
1.自底向上算法
#include<stdio.h>
#include<time.h>
void Merge(int*a,int low,int mid,int high)
{
int i=low,j=mid+1,k=0;
int *temp=(int*)malloc((high-low+1)*sizeof(int));
while(i<=mid&&j<=high)
a[i]<=a[j]?(temp[k++]=a[i++]):(temp[k++]=a[j++]);
while(i<=mid)
temp[k++]=a[i++];
while(j<=high)
temp[k++]=a[j++];
memcpy(a+low,temp,(high-low+1)*sizeof(int));
free(temp);
}
void MergeSort(int*a,int n){
int length;
for(length=1;length<n;length*=2){
int i;
for(i=0;i+2*length-1<=n-1;i+=2*length)
Merge(a,i,i+length-1,i+2*length-1);
if(i+length<=n-1)//尚有兩個子文件，其中後一個長度小於length
Merge(a,i,i+length-1,n-1);
}
}
int main(){
int n;
cin>>n;
int*data=new
int[n];
if(!data)
exit(1);
int k=n;
while(k--){
cin>>data[n-k-1];
}
clock_ts=clock();
MergeSort(data,n);
clock_te=clock();
k=n;
while(k--){
cout<<data[n-k-1]<<'';
}
cout<<endl;
cout<<"thealgrothemused"<<e-s<<"miliseconds."<<endl;
delete data;
return 0;
}2.自頂向下
void Merge(int r[],int r1[],int s,int m,int t){
int i=s;
int j=m+1;
int k=s;
while(i<=m&&j<=t){
if(r[i]<=r[j])
r1[k++]=r[i++];
else
r1[k++]=r[j++];
}
while(i<=m)
r1[k++]=r[i++];
while(j<=t)
r1[k++]=r[j++];
for(int l=0;l<8;l++)
r[l]=r1[l];
}
void MergeSort(int r[],int r1[],int s,int t){
if(s==t)
;
else{
int m=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r,r1,s,m,t);
}
}
歸併排序應用實例
NOIP2013 提高組火柴排隊
#include<bits/stdc++.h>
using namespace std;
int c[1000005],t[1000005],mod=99999997;
long long cnt=0;
struct edge{
int num,i;
}a[1000005],b[1000005];
void merge(int l,int r)
{
if(l==r)
return;
int mid=(l+r)/2;
merge(l,mid);
merge(mid+1,r);
int x=l,y=mid+1,tot=l;
while(x<=mid&&y<=r)
if(c[x]<=c[y])
t[tot++]=c[x++];
else
{
cnt+=(mid-x+1)%mod;
cnt%=mod;
t[tot++]=c[y++];
}
while(x<=mid)
t[tot++]=c[x++];
while(y<=r)
t[tot++]=c[y++];
for(int i=l;i<= r;++i)
c[i]=t[i];
}
bool cmp(edge a,edge b)
{
return a.num<b.num;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i].num;
a[i].i=i;
}
for(int i=1;i<=n;++i)
{
cin>>b[i].num;
b[i].i=i;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;++i)
c[a[i].i]=b[i].i;
merge(1,n);
cout<<cnt<<endl;
return 0;
}
