【數(shù)據(jù)結(jié)構(gòu)與算法】合并排序

這篇具有很好參考價值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)與算法】合并排序。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

合并排序,鳴人雜記,排序算法,java,算法,c++,數(shù)據(jù)結(jié)構(gòu)

CSDN話題挑戰(zhàn)賽第1期
活動詳情地址：https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f
參賽話題：Java學(xué)習(xí)記錄話題描述：可以記錄一下平時學(xué)習(xí)Java中的一些知識點、心得、例題、常見的問題解決

好文推薦>>>??圖文并茂詳解十大排序算法讓您回味無窮

??合并排序(Sequencing By Merging)

1.百科

合并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。合并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。合并排序也叫歸并排序

2.算法思想

合并排序是采用分治策略實現(xiàn)對n個元素進行排序的算法，是分治法的一個典型應(yīng)用和完美體現(xiàn)。它是一種平衡、簡單的二分分治策略，其計算過程分為三大步：
（1）分解：將待排序元素分成大小大致相同的兩個子序列。
（2）求解子問題：用合并排序法分別對兩個子序列遞歸地進行排序。
（3）合并：將排好序的有序子序列進行合并，得到符合要求的有序序列

有對分治法不太熟悉的可以看看博主這篇文章>>>??分治法剖析

2.1合并過程

合并排序的關(guān)鍵步驟在于如何合并兩個已排好序的有序子序列。為了進行合并，引入一個輔助過程Merge(A,low,middle,high)，該過程將排好序的兩個子序列A[low:middle]和A[middle+1:high]進行合并。其中，low、high表示待排序范圍在數(shù)組中的上界和下界，middle表示兩個序列的分開位置，滿足low≤middle＜high；由于在合并過程中可能會破壞原來的有序序列，因此，合并最好不要就地進行，本算法采用了輔助數(shù)組B[low:high]來存放合并后的有序序列

2.2合并方法

設(shè)置三個工作指針i，j，k。其中，i和j指示兩個待排序序列中當(dāng)前需比較的元素，k指向輔助數(shù)組B中待放置元素的位置。比較A[i]和A[j]的大小關(guān)系，如果A[i]小于等于A[j]，則B[k]=A[i]，同時將指針i和k分別推進一步；反之，B[k]=A[j]，同時將指針j和k分別推進一步。如此反復(fù)，直到其中一個序列為空。最后，將非空序列中的剩余元素按原次序全部放到輔助數(shù)組B的尾部

3.算法描述

語句if((!s[j])&&(dist[j]<temp))對算法的運行時間貢獻最大，也是作為基本語句的原因。當(dāng)外層循環(huán)標號為1時，該語句在內(nèi)層循環(huán)的控制下，共執(zhí)行n次，外層循環(huán)從1~n，因此，該語句的執(zhí)行次數(shù)為n*n=n2，算法的時間復(fù)雜性為O(n2)
實現(xiàn)該算法所需的輔助空間包含為數(shù)組s和變量i、j、t和temp所分配的空間，因此，??Dijkstra算法的空間復(fù)雜性為O(n)

void Merge(int A[]，int low，int middle，int high)
{
int i,j,k; int *B=new int[high-low+1];
i=low; j=middle+1; k=low;
 while(i<=middle&&j<=high)  //兩個子序列非空
 if(A[i]<=A[j])  B[k++]=A[i++];
     else  B[k++]=A[j++];
 while (i<=middle) B[k++]=A[i++];
 while (j<=high) B[k++]=A[j++];
  for(i=low;i<=high;i++) A[i++]=B[i++];
}

還可以用遞歸形式實現(xiàn)

void MergeSort (int A[]，int low，int high)
{    int middle;
        if (low<high) 
           {
              middle=(low+high)/2;   //取中點
              MergeSort(A,low,middle); 
             MergeSort(A,middle+1,high); 
              Merge(A,low,middle,high); //合并
           }
}

4.算法分析

當(dāng)n=1時，T(n)=O(1)
當(dāng)n>1時，將時間T如下分解：

分解：這一步需要常量時間O(1)
解決子問題：遞歸求解兩個規(guī)模為n/2的子問題，所需時間為2T(n/2)
合并：Merge算法可在O(n)時間內(nèi)完成

得到合并排序算法運行時間T(n)的遞歸形式為合并排序,鳴人雜記,排序算法,java,算法,c++,數(shù)據(jù)結(jié)構(gòu)
求得T(n)=nT(1)+nlogn=n+nlogn，即**合并排序算法的時間復(fù)雜性為O(nlogn)**
算法所使用的工作空間取決于Merge算法，每調(diào)用一次Merge算法，便分配一個適當(dāng)大小的緩沖區(qū)，退出Merge便釋放它。在最后一次調(diào)用Merge算法時，所分配的緩沖區(qū)最大，需要O(n)個工作單元。所以，合并排序算法的空間復(fù)雜性為O(n)

5.構(gòu)造實例

下面給大家個圖片更容易理解，合并排序就是三大步驟：分解，然后分別排序再一一合并就ok了合并排序,鳴人雜記,排序算法,java,算法,c++,數(shù)據(jù)結(jié)構(gòu)
再給大家搞個動圖

6.代碼實現(xiàn)

6.1 Java

public static void mergeSort(int[]array){
   
  int length=array.length;
  int middle=length/2;
 
  if(length>1){
    int[]left=Arrays.copyOfRange(array,0,middle);//拷貝數(shù)組array的左半部分
    int[]right=Arrays.copyOfRange(array,middle,length);//拷貝數(shù)組array的右半部分
    mergeSort(left);//遞歸array的左半部分
    mergeSort(right);//遞歸array的右半部分
    merge(array,left,right);//數(shù)組左半部分、右半部分合并到Array
  }
}
 
//合并數(shù)組，升序
private static void merge(int[]result,int[]left,int[]right){
 
  int i=0,l=0,r=0;
 
  while(l<left.length&&r<right.length){
    if(left[l]<right[r]){
      result[i]=left[l];
      i++;
      l++;
    }else{
      result[i]=right[r];
      i++;
      r++;
   }
  }
 
  while(r<right.length){//如果右邊剩下合并右邊的
    result[i]=right[r];
    r++;
    i++;
  }
 
  while(l<left.length){
    result[i]=left[l];
    l++;
    i++;
  }
}

6.2 C/C++

#include <malloc.h>
#include <stdlib.h>
void mergesort(int*a,int length){
    int step;
    int*p,*q,*t;
    int i,j,k,len1,len2;
    int *temp;
        step=1;
    p=a;
    q=(int*)malloc(sizeof(int)*length);
    temp=q;
    while(step<length){
        i=0;
        j=i+step;
        k=i;
        len1=i+step<length?i+step:length;
        len2=j+step<length?j+step:length;
        while(i<length){
            while(i<len1&&j<len2){
                q[k++]=p[i]<p[j]?p[i++]:p[j++];
            }
            while(i<len1){
                q[k++]=p[i++];
            }
            while(j<len2){
                q[k++]=p[j++];
            }
            i=j;
            j=i+step;
            k=i;
            len1=i+step<length?i+step:length;
            len2=j+step<length?j+step:length;
        }
        step*=2;
        t=p;
        p=q;
        q=t;
    }
 
    if(a!=p){
        memcpy(a,p,sizeof(int)*length);
    }
    free(temp);
}
void main(void){
int arrary[]={9,6,1,3,8,4,2,0,5,7};
mergesort(arrary,10);
}

sort(int *begin,int *end)

void sort(int *begin,int *end)
{
int size=end-begin;
int*p,*p1,*p2,*mid=begin+size/2;
if(size<=1)return;//邊界條件
sort(begin,mid);//遞歸求解
sort(mid,end);
p=(int*)malloc(size*sizeof(int));//申請臨時空間
for(p1=begin,p2=mid;p1!=mid||p2!=end;)//合并有序表
*p++=(p2==end||p1!=mid&&*p1<*p2)?(*p1++):(*p2++);
for(p-=size;begin!=end;)//回填
*begin++=*p++;
free(p-size);//釋放臨時空間

//C++
#include<string>
#include<iostream>
using namespace std;//合并排序
//合并兩部分有序數(shù)組time:O(n)
template<typename T>
void Merge(T  *arry,int start,int p,int end)
{
    int lsize=p-start,rsize=end-p;//兩個數(shù)組的大小
    T * l=new T[lsize],*r=new T[rsize];//要合并的兩個數(shù)組
    memcpy(l,arry + start,sizeof(T)*lsize);
    memcpy(r,arry + p,sizeof(T)*rsize);//將要合并的數(shù)組復(fù)制
    int lnow=0,rnow=0,i;//未合并的數(shù)字的位置
    for(i=0;lnow<lsize&&rnow<rsize;i++)
    {
        if(l[lnow]>r[rnow])//取較大的數(shù)
        {
            arry[start+i]=l[lnow];
            lnow++;
        }
        else
        {
            arry[start+i]=r[rnow];
            rnow++;
        }
    }
    if(lnow==lsize&&rnow!=rsize)//其中一個數(shù)組合并完以后，復(fù)制剩下的數(shù)據(jù)
    {
        memcpy(arry+start+i,r+rnow,sizeof(T)*(rsize-rnow));
    }
    else if(rnow==rsize&&lnow!=lsize)
    {
        memcpy(arry+start+i,l+lnow,sizeof(T)*(lsize-lnow));
    }
    delete l;
    delete r;//清理內(nèi)存
    //return ;
}//排序函數(shù)time:O(nlgn)
template<typename T>
void MergeSort(T *arry,int start,int end)
{
    if(end-start > 1)//當(dāng)元素個數(shù)為1時直接返回
    {
        int p=(start + end)/2;//切割數(shù)組
        MergeSort(arry,start,p);
        MergeSort(arry,p,end);//分別排序
        Merge(arry,start,p,end);//合并數(shù)組
    }
}
int main()
{
      
    int arr[10]={7,3,4,7,10,9,1,5,3,7};
     
    MergeSort(arr,0,10);
    for(int i=0;i<10;i++)
    {
        cout<<arr[i]<<" "<<endl;
    }
    return 0;
}

CSDN話題挑戰(zhàn)賽第1期
活動詳情地址：https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f
參賽話題：Java學(xué)習(xí)記錄話題描述：可以記錄一下平時學(xué)習(xí)Java中的一些知識點、心得、例題、常見的問題解決文章來源地址http://www.zghlxwxcb.cn/news/detail-785109.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】合并排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！