歸并排序法 ：
說(shuō)明：
歸并排序比較占用內(nèi)存鼠锈，但卻是一種效率高而且穩(wěn)定的算法寒砖。
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用佛嬉。將已有序的子序列合并蛉迹，得到完全有序的序列稠诲；即先使每個(gè)子序列有序舵匾，再使子序列段間有序诬乞。若將兩個(gè)有序表合并成一個(gè)有序表册赛，稱為二路歸并。
歸并過(guò)程為：比較a[i]和a[j]的大小震嫉，若a[i]≤a[j]森瘪，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1票堵；否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中扼睬，并令j和k分別加上1，如此循環(huán)下去悴势，直到其中一個(gè)有序表取完窗宇，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)特纤，先把待排序區(qū)間[s,t]以中點(diǎn)二分军俊，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序捧存，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]粪躬。
操作：
歸并操作(merge)担败，也叫歸并算法，指的是將兩個(gè)順序序列合并成一個(gè)順序序列的方法镰官。
如 設(shè)有數(shù)列{6提前，202，100泳唠，301狈网，38，8笨腥，1}
初始狀態(tài)：6,202,100,301,38,8孙援，1
第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數(shù)：3扇雕；
第二次歸并后：{6,100,202,301}，{1,8,38}窥摄，比較次數(shù)：4镶奉；
第三次歸并后：{1,6,8,38,100,202,301},比較次數(shù)：4；
總的比較次數(shù)為：3+4+4=11,崭放；
逆序數(shù)為14哨苛；
描述：
歸并操作的工作原理如下：
- 第一步：申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和币砂，該空間用來(lái)存放合并后的序列
- 第二步：設(shè)定兩個(gè)指針建峭，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
- 第三步：比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間决摧，并移動(dòng)指針到下一位置
- 重復(fù)步驟3直到某一指針超出序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
Java語(yǔ)言
package algorithm;
public class MergeSort {
// private static long sum = 0;
/**
* <pre>
* 二路歸并
* 原理：將兩個(gè)有序表合并和一個(gè)有序表
* </pre>
*
* @param a
* @param s
* 第一個(gè)有序表的起始下標(biāo)
* @param m
* 第二個(gè)有序表的起始下標(biāo)
* @param t
* 第二個(gè)有序表的結(jié)束小標(biāo)
*
*/
private static void merge(int[] a, int s, int m, int t) {
int[] tmp = new int[t - s + 1];
int i = s, j = m, k = 0;
while (i < m && j <= t) {
if (a[i] <= a[j]) {
tmp[k] = a[i];
k++;
i++;
} else {
tmp[k] = a[j];
j++;
k++;
}
}
while (i < m) {
tmp[k] = a[i];
i++;
k++;
}
while (j <= t) {
tmp[k] = a[j];
j++;
k++;
}
System.arraycopy(tmp, 0, a, s, tmp.length);
}
/**
*
* @param a
* @param s
* @param len
* 每次歸并的有序集合的長(zhǎng)度
*/
public static void mergeSort(int[] a, int s, int len) {
int size = a.length;
int mid = size / (len << 1);
int c = size & ((len << 1) - 1);
// -------歸并到只剩一個(gè)有序集合的時(shí)候結(jié)束算法-------//
if (mid == 0)
return;
// ------進(jìn)行一趟歸并排序-------//
for (int i = 0; i < mid; ++i) {
s = i * 2 * len;
merge(a, s, s + len, (len << 1) + s - 1);
}
// -------將剩下的數(shù)和倒數(shù)一個(gè)有序集合歸并-------//
if (c != 0)
merge(a, size - c - 2 * len, size - c, size - 1);
// -------遞歸執(zhí)行下一趟歸并排序------//
mergeSort(a, 0, 2 * len);
}
public static void main(String[] args) {
int[] a = new int[] { 4, 3, 6, 1, 2, 5 };
mergeSort(a, 0, 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
}
}
歸并算法
定義
所謂歸并排序是指將兩個(gè)或兩個(gè)以上有序的數(shù)列（或有序表）亿蒸，合并成一個(gè)仍然有序的數(shù)列（或有序表）。這樣的排序方法經(jīng)常用于多個(gè)有序的數(shù)據(jù)文件歸并成一個(gè)有序的數(shù)據(jù)文件掌桩。歸并排序的算法比較簡(jiǎn)單边锁。
基本思想方法：
（1）假設(shè)已經(jīng)有兩個(gè)有序數(shù)列，分別存放在兩個(gè)數(shù)組s波岛，r中茅坛；并設(shè)i，j分別為指向數(shù)組的第一個(gè)單元的下標(biāo)则拷；s有n個(gè)元素贡蓖，r有m個(gè)元素。
（2）再另設(shè)一個(gè)數(shù)組a煌茬，k指向該數(shù)組的第一個(gè)單元下標(biāo)斥铺。
（3）算法分析（過(guò)程）：
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.h>
voidMerge(intr[],intr1[],ints,intm,intt){
inti=s;
intj=m+1;
intk=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(intn=s;n<=t;n++)
r[n]=r1[n];
}
voidMergeSort(intr[],intr1[],ints,intt){
if(s<t){
intm=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r,r1,s,m,t);
}
}
voidmain(){
intr[8]={10,3,5,1,9,34,54,565},r1[8];
MergeSort(r,r1,0,7);
for(intq=0;q<8;q++)
cout<<""<<r[q];
return0；
}
歸并排序的實(shí)現(xiàn)方法：
1.自底向上算法
#include<stdio.h>
#include<time.h>
voidMerge(int*a,intlow,intmid,inthigh){
inti=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);
}
voidMergeSort(int*a,intn){
intlength;
for(length=1;length<n;length*=2){
inti;
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)//尚有兩個(gè)子文件宣旱，其中后一個(gè)長(zhǎng)度小于length
Merge(a,i,i+length-1,n-1);
}
}
intmain(){
intn;
cin>>n;
int*data=new
int[n];
if(!data)
exit(1);
intk=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;
deletedata;
return0;
}
2.自頂向下
voidMerge(intr[],intr1[],ints,intm,intt){
inti=s;
intj=m+1;
intk=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(intl=0;l<8;l++)
r[l]=r1[l];
}
voidMergeSort(intr[],intr1[],ints,intt){
if(s==t)
;
else{
intm=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r,r1,s,m,t);
}
}
