归并排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

归并排序

简介: 归并排序

mergeSort

应用分治法思想,有两种实现方法:

  1. 自顶向下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法)
  2. 自底向上的迭代

算法步骤

UpDown

通过二分法达到log(n)这样一个层级,然后再通过O(n)的归并操作,就形成了nlog(n)的归并排序

  1. 二分操作:将n个元素平均分成两部分,再分别将这两部分进行递归二分操作。直到所有分组都只有1个元素(只有一个元素时,数列显然有序)

  2. 归并操作:从最底层开始逐步合并两个排好序的数列
    我这里采用对原数组进行操作,所以先建立一个辅助数组T temp[r-l+1],通过for循环将原数组数据复制到辅助数组
    又因为两个序列都已经有序,因此只需要两个序列的低位轮流进行比较,输的一方为小值,将这个值赋值到原数组,输的一方继续拿出一个值来比较,直到有一方没有元素后,将另一方的所有元素依次赋值到原数组中即可。此时,原数组为两个序列的有序合并。

下面两个子数组分别进行比较,将合适的元素赋值到上面的大数组

BottomUp

自底向上进行归并操作

  1. size是归并子数组的长度,从1开始直到n,归并一次,size扩大一倍
  2. 从下标i开始,对arr[i,i+size-1]和arr[i+size,i+2*size-1]进行合并(两个子数组中对应的坐标相差size),下轮循环开始是从i+2*size

自顶向下的递归实现

#include <iostream>

#include "insertionSort.h"

using namespace std;

//归并操作

template <typename T>

void __merge(T arr[],int left,int mid,int right){

    T temp[right-left+1];//临时数组

    for(int i=left;i<=right;i++)

        temp[i-left]=arr[i];

    //临时数组中的左右指针(左指针是第一个元素,右指针从内部看来也是右部第一个元素,但从全局上看,就是中值+1)

    int curL=left,curR=mid+1;

   //k是要原数组中即将要赋值的坐标

    for(int k=left;k<=right;k++){

        //这里四选一,所以要在一个if-else体系中,否则就会多次赋值

        //越界判断

        if(curL>mid){

            arr[k]=temp[curR-left];

            curR++;

        }

        else if(curR>right){

            arr[k]=temp[curL-left];

            curL++;

        }

        //左右低位轮流PK

        //右值为小值,加入到arr中,右边再拿出一个值来比较

        else if(temp[curL-left]>temp[curR-left]){

            arr[k]=temp[curR-left];

            curR++

        }else { //左值小于等于右值,左值加入arr中,左边再拿出一个值来比较(b)

            arr[k]=temp[curL-left];

            curL++

        }

    }

}

//对数组中arr[left]至arr[right]进行归并排序

template <typename T>

void __mergeSort(T arr[],int left,int right){

    

   //1. 二分操作  

    //递归出口:处理的数据集为空

    if(left>=right)

        return

    int mid=(left+right)/2;

    __mergeSort(arr,left,mid); 

    __mergeSort(arr,mid+1,right);

    

    //2. 归并操作

    __merge(arr,left,mid,right); 

}

//归并排序

template <typename T>

void mergeSort(T arr[],int n){

    //注意这里,数组范围是前闭后闭的

    __mergeSort(arr,0,n-1); 

     

}

int main(){

    int n=100000;

    //生成乱序数组

    int* arr=SortTestHelper::generateRandomArray(n,0,n);

    int* arr2=SortTestHelper::copyIntArray(arr,n);

    //测试耗时

    //SortTestHelper::testSort("insertionSort",insertionSort,arr,n);

    SortTestHelper::testSort("mergeSort",mergeSort,arr2,n);

    

    //释放空间

    delete[] arr;

    delete[] arr2;

    return 0;

}

优化1:归并操作前的判断

当数组是近乎有序时,归并排序是弱于插入排序的时间复杂度的,可以在归并操作之前对数组进行是否有序判断

//归并操作

    //左边的末尾大于右边首元素才会进行归并操作,如果是小于等于,则说明已经有序,不再进行归并操作

    if(arr[mid]>arr[mid+1])

        __merge(arr,left,mid,right); 

当我们要处理的元素中可能出现有序的情况,可以使用上述代码优化

优化2:穿插使用插入排序

对于所有高级排序算法,都可以这么进行优化:

快要递归到底时,可以使用插入排序,当递归到数组数量非常小的时候,可以改为使用插入排序来提高性能

  1. 数组数量较小时,有序的概率较大
  2. 虽然插入排序最差时间复杂度为O(n^2),归并排序时间复杂度为O(nlogn),但是时间复杂度前面是有一个常数的系数的,插入排序的系数比归并排序的系数小,也就是说,当n小到一定程度时,插入排序是要比归并排序要快的

    //二分操作

    //处理数据集为空

//  if(left>=right)

//      return ;

    

    //当数组元素<=15时,更换为插入排序

    if((right-left)<=15){

        insertionSort(arr ,left ,right); 

        return ;

    }

需要在insertionSort.h中重载insertionSort函数

//对arr中[l,r]范围内的元素进行插入排序

template <typename T>

void insertionSort(T arr[],int left,int right){

    for(int i=left+1;i<=right;i++){

        int j;

        T e=arr[i];

        //注意这里是j>left,而不是j>0

        for(j=i;j>left&&arr[j-1]>e;j--)

                arr[j]=arr[j-1];

        arr[j]=e;

    } 

}

test

n = 500000

//原始代码

mergeSort_TopDown : 0.173 s

//使用优化1

mergeSort_TopDown : 0.158 s

//使用优化2

mergeSort_TopDown : 0.144 s

//使用优化1&2

mergeSort_TopDown : 0.119 s

优化效果一目了然

自底向上的递推实现

//自底向上的归并排序

template <typename T>

void mergeSort_BottomUp(T arr[],int n){

    //size表示归并子数组的长度,归并之后的归并子数组长度要变为原来的2倍,因此每次循环结束size=size*2

    for(int size=1;size<=n;size=size*2){

        //两个要进行归并的子数组间隔为size,对arr[i,i+size-1]和arr[i+size,i+2*size-1]进行归并,归并之后下次开始是arr[i+2*size],因此每轮循环结束后i=i+2*size

        //第一轮对[0,size-1]和[size,2*size-1]进行归并,第二轮对[2*size,3*size-1]和[3*size,4*size-1]进行归并

        

        //界限处理:

        //1. 因为只有存在两个子数组才能进行归并,那么要求i+size<n,保证了第二个子数组中arr[i+size]存在的合法性,并且避免了第一个子数组中arr[i+size-1]越界

        //2. 遍历到后面,第二个子数组长度可能小于size,那么(2*size-1)>(n-1)造成越界,将其和(n-1)取最小值即可,min(i+2*size-1,n-1)

        for(int i=0;i+size<n;i=i+2*size){ 

            __merge(arr,i,i+size-1,min(i+2*size-1,n-1));

        }

    }

}

自底向上没有使用数组的重要特性:根据索引获取元素

正因如此,可以非常好的使用O(nlogn)的时间对链表这样的数据结构进行归并排序


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章