歸並排序
一、歸並排序的效率是僅次於快速排序的穩定的排序算法，其時間復雜度為O(nlog2n)。我們對n 個元素進行一次歸並排序時，歸並的次數約為log2n，每一次的兩路歸並排序元素的比較次數約為n-1。
二、歸並排序的基本思想：
歸並排序是通過將一列數組序列中的元素看成一個一個的小序列來進行歸並，直到所有的元素都被歸並完成後，排序即完成，便是成功的完成了排序操作。
三、原理：
如：我們對n 為9吧，這樣更加好，如，a[9] = {1,2,5,4,3,8,6,7,9}這樣的一個數組：
原數組：
1 2 5 4 3 8 6 7 9
第一次歸並：
[1 2] [4 5] [3 8] [6 7] [9]
第二次歸並：
[1 2 4 5] [3 6 7 8] [9]
第三次歸並：
[1 2 3 4 5 6 7 8] [9]
第四次歸並：
[1 2 3 4 5 6 7 8 9]
實現歸並的操作代碼：
for(i = L1,j = L2;i<=u1&&j <= u2;){
if(a[i] <= a[j]){
A->swap[pos] = a[i];
i++;
pos++;
}else{
A->swap[pos] = a[j];
j++;
pos++;
}
}
//此時我們要做的已經歸並完成了
//此時我們要對在數組序列沒有歸並的進行歸並
while(i <= u1 ){
A->swap[pos]=a[i];
i++;
pos++;
}
while(j <= u2 ){
A->swap[pos] = a[j];
j++;
pos++;
}
//此時對兩個數組序列已經徹底歸並完成了，而且此時是有序序列
//此時的L1 = u2+1了
L1 = u2 +1;
//這裡我們把只有一組的也存放到swap中
for(int i = L1;iswap[i] = a[i];
} 實現一次執行歸並的核心代碼：
/**
*歸並排序的一次執行
*@param int a[] 為接收的數組
*@param int lenghth1 為此接收數組的長度
*@param int swap[], 為保存執行完畢一次歸並排序後的數組
*@param int length2 為此歸並好了的數組序列的長度
*@return 無
*/
void Merge(int a[],int length1 ,Array *A,int length2){
//接收了數組我們需要對其進行歸並和一次排序這時我們定義兩個有指向的“指針”
int u1,u2;//此為這兩個便於掃描的指針
//此時又需要定義兩個數組序列的下界
int L1,L2;
//我們可以知道第一個數組序列的下界為0
L1 = 0;
//此時設置swap中的下標值pos來保存歸並成功的數,因為pos是針對這整個循環的所以只能放在循環外面
int pos = 0;
while(L1+length2swap[pos] = a[i];
* i++;
* pos++;
* }else{
* A->swap[pos] = a[j];
* j++;
* pos++;
* }
* }
*/
for(;;){
if(i<=u1&&j <= u2){
if(a[i] <= a[j]){
A->swap[pos] = a[i];
i++;
pos++;
}else{
A->swap[pos] = a[j];
j++;
pos++;
}
}else{
break;
}
}
//此時我們要做的已經歸並完成了
//此時我們要對在數組序列沒有歸並的進行歸並
while(i <= u1 ){
A->swap[pos]=a[i];
i++;
pos++;
}
while(j <= u2 ){
A->swap[pos] = a[j];
j++;
pos++;
}
//此時對兩個數組序列已經徹底歸並完成了，而且此時是有序序列
//此時的L1 = u2+1了
L1 = u2 +1;
}
//cout<<"L1"<swap[i]......i="<swap[i] = a[i];
}
//這樣一次歸並操作徹底完成了
/*for(int i = 0;i swap[i]......i="<實現歸並排序的代碼段：
/**
*歸並排序
*@param int a[]帶歸並的數組序列
*@param int length1 為帶歸並的數組序列的長度
*@return 無
*/
void Merge_sort(int a[],int length1){
//我們知道我們以數組長度為1開始歸並
int length2 = 1;
//這裡我們需要申請一個swap空間來作為交換的空間
Array *A =NULL;
if(A != NULL){
free(A);
}
A = (Array *)malloc(sizeof(Array )*length1);
if(A != NULL){
cout<<"申請空間成功！"<swap[i];//這裡把歸並後的數組序列再次保存回a[i]中
}
//這裡需要更改歸並後的新數組序列的長度
length2 = 2*length2;
}
//記住最後一定要對空間進行釋放
free(A);
}
全部代碼：
/**
*歸並排序就是將一個數組分成若干個數組然後兩兩合並直到合並完成最後一個數組
*@author 菜鳥
*@version 2014.6.15
*/
#include
#include
#include
#define maxSize 100
using namespace std;
typedef int DataType;
typedef struct{
DataType swap[maxSize];
}Array;
/**
*歸並排序的一次執行
*@param int a[] 為接收的數組
*@param int lenghth1 為此接收數組的長度
*@param int swap[], 為保存執行完畢一次歸並排序後的數組
*@param int length2 為此歸並好了的數組序列的長度
*@return 無
*/
void Merge(int a[],int length1 ,Array *A,int length2){
//接收了數組我們需要對其進行歸並和一次排序這時我們定義兩個有指向的“指針”
int u1,u2;//此為這兩個便於掃描的指針
//此時又需要定義兩個數組序列的下界
int L1,L2;
//我們可以知道第一個數組序列的下界為0
L1 = 0;
//此時設置swap中的下標值pos來保存歸並成功的數,因為pos是針對這整個循環的所以只能放在循環外面
int pos = 0;
while(L1+length2swap[pos] = a[i];
* i++;
* pos++;
* }else{
* A->swap[pos] = a[j];
* j++;
* pos++;
* }
* }
*/
for(;;){
if(i<=u1&&j <= u2){
if(a[i] <= a[j]){
A->swap[pos] = a[i];
i++;
pos++;
}else{
A->swap[pos] = a[j];
j++;
pos++;
}
}else{
break;
}
}
//此時我們要做的已經歸並完成了
//此時我們要對在數組序列沒有歸並的進行歸並
while(i <= u1 ){
A->swap[pos]=a[i];
i++;
pos++;
}
while(j <= u2 ){
A->swap[pos] = a[j];
j++;
pos++;
}
//此時對兩個數組序列已經徹底歸並完成了，而且此時是有序序列
//此時的L1 = u2+1了
L1 = u2 +1;
}
//cout<<"L1"<swap[i]......i="<swap[i] = a[i];
}
//這樣一次歸並操作徹底完成了
/*for(int i = 0;i swap[i]......i="<swap[i];//這裡把歸並後的數組序列再次保存回a[i]中
}
//這裡需要更改歸並後的新數組序列的長度
length2 = 2*length2;
}
//記住最後一定要對空間進行釋放
free(A);
}
/**
*這裡需要一個輸出函數，對數組序列進行輸出out_put()
*@param int a[] 表示接受此數組的地址
*@param int length 表示此數組的長度
*@return 無
*/
void out_put(int a[],int length){
for(int i = 0; i< length ;i++){
cout<<"第"<
