稳定排序：归并排序

约定不等于承诺〃 2022-06-17 07:44 119阅读 0赞

归并排序：对于给定的一组长度为n的记录，利用分治和递归的思想，将记录分为一个个长度为1的子序列，最后再用递归方法将排好序的子序列合并成为越来越大的有序序列。此方法称为2-路归并排序

*  归并排序一般会用在外部排序的算法中。

*  该算法是采用**分治法**的一个非常典型的应用。

【时间复杂度】：O(nlogn)

【最优情况】：   O(nlogn)

【最坏情况】:O(nlogn)

(归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是**O(n\*log2n)**。)

【空间复杂度】：O(n)

(算法处理过程中，需要一个大小为**n**的临时存储空间用以保存合并序列。)

实现代码

C++：

#include <stdio.h>
    #define MAXSIZE 10
    
    void MergeSort(int[] a,num){
    //num数组长度
    int *list1=k;
    int list1_size=num/2;
    int *list2=k+num/2;
    int list2_size=num-list1_size;
    //分解数组：原数组分为左数组和右数组，左数组再调用该函数，继续细分下去
    //只要数组的长度大于1，它就会继续分解下去
    if(num>1){
    MergeSort(list1,list1_size);
    MergeSort(list2,list2_size);
    Merging(list1,list1_size,list2,list2_size);
    }
    //排序数组并归并
    
    void Merging(*list1,list1_size,*list2,list2_size){
    
    int i,j,k;//i是list1的下标，j是list2的下标，k是临时数组的下标
    i=j=k=0;
    int[]tmp=new int[MAXSIZE];
    while(i<list1_size&&j<list2_size){
    
    if(list1[i]<list2[j]){
    tmp[k++]=list1[i++];
    }else
    tmp[k++]=list2[j++];
    }
    //list1数组中还有未扫描的元素
    while(i<list1_size){
    tmp[k++]=list1[i++];
    
    }
    
    //list2数组中还有未扫描的元素
     while(j<list2_size){
      tmp[k++]=list2[j++];
    }
    //临时数组覆盖原数组
    for(int n=0;n<(list1_size+list2_size);n++){
      list1[n]=tmp[n];
    
     }
    
    }

java

//java实现
    public class Sort{
    
      //分解 、递归
      public static void MergeSort(int[] a,int left,int right){
       int mid=(left+right)/2;
       if(left<right){
         //left,right是数组的下标
         //完整的数组分成左右两半，左边的数组再调用此方法，再细分下去
          MergeSort(a,left,mid);
          MergeSort(a,mid+1,right);
        //两两数组归并
          Merging(a,left,mid,right);
    
       }
    
     }
      //归并 排序方法
      /*
       将排好序的元素放进临时数组
       因为最后临时数组都是排好序的
       所以就可以覆盖原有数组
    
     */
      public static void Merging(int[]a,int left,int mid,int right){
        int[] tmp=new int[right-left+1];//临时数组存放排好序的元素
        int i=left;//左边数组的下标
        int j=mid+1;//右边数组的下标
        int k=0;//临时数组的下标
       while(i<=mid&&j<=right){
        if(a[i]<a[j]){
         tmp[k]=a[i];
         i++;
         k++;
       }
      //左边数组还有没扫描完的元素
       while(i<=mid){
        //tmp[k++]=a[i++]
         tmp[k]=a[i];
         i++;
         k++;
      }
     //右边数组还有没扫描完的元素
       while(j<=right){
       //tmp[k++]=a[j++]
         tmp[k]=a[j];
         j++;
         k++;
       }
       //将临时数组覆盖到原数组中
       for(int n=0;n<tmp.length;n++){
         num[n+low]=tmp[n];
      }
     }
     public static void main(String[]args){
      int[]a={10,55,13,23,5,22,87,34};
      MergeSort(a);
    
    
     }
    }

心得：因为归并排序是个比较复杂的排序算法，实际操作着将一组记录用归并排序来排序，可以理解，但是用代码实现起来挺不容易的，因为用到了递归和分治思想。自己先后用了C++和java来实现归并排序，发现其实c++可能更好理解，因为c++有指针，而java并没有，所以在java的代码中设置了mid这个变量作为中间索引，两种语言的写法还是不太一样的