二路归并排序简介及其并行化

一、归并排序简介

1.算法思想

归并排序属于比较类非线性时间排序,比较类排序中性能最佳,应用较为广泛。

归并排序是分治法(Divide and Conquer)的一个典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

2.二路归并排序过程描述

设有数列{16,23,100,3,38,128,23} 初始状态:16,23,100,3,38,128,23 第一次归并后:{6,23},{3,100},{38,128},{23}; 第二次归并后:{3,6,23,100},{23,38,128}; 第三次归并后:{3,6,23,23,38,100,128}。 完成排序。

3.二路归并复杂度分析

时间复杂度:O(nlogn),是最好、最坏和平均的时间性能,排序性能不受待排序的数据的混乱程度影响,比较稳定,这也是相对于快排的优势所在。 空间复杂度为:O(n)。 稳定性:稳定,从上文排序过程中可以看出,黑体23一直在前面。

二、二路归并实现

1.C/C++串行实现

/************************************************
*函数名称:mergearray
*参数:a:待归并数组;first:开始下标;mid:中间下标;
*     last:结束下标;temp:临时数组
*说明:将有二个有序数列a[first...mid]和a[mid...last]合并 
*************************************************/
void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1,k =0;    
    while (i <= mid && j <= last)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }    
    while (i<= mid)  
        temp[k++] = a[i++];  

    while (j <= last)  
        temp[k++] = a[j++];   
    for (i=0; i < k; i++)  
        a[first+i] = temp[i];  
}  
/************************************************
*函数名称:mergesort
*参数:a:待归并数组;first:开始下标;
*     last:结束下标;temp:临时数组
*说明:实现给定数组区间的二路归并排序 
*************************************************/
void mergesort(int a[], int first, int last, int temp[])  
{  

    if (first < last)  
    {  
        int mid = (first + last) / 2;       
        mergesort(a, first, mid, temp);    //左边有序  
        mergesort(a, mid + 1, last, temp); //右边有序  
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并      
    }  
}

本机测试100 * 1024 * 1024 =100M个32bits整型,串行需要15.536s,以下是本机软硬件参数,为Linux平台。

2.C/C++并行实现

2.1并行思路

将待排序数组通过偏移量进行逻辑切分为多块,将每个块传递给多个线程调用二路归并排序函数进行排序。待各个块内有序后,再合并各个块整合成有序数列。

2.2并行代码

线程函数,供创建出来的线程调用。

/*******************************************
*函数名称:merge_exec
*参数:   para指针,用于接收线程下边,表示第几个线程
*说明:   调用二路归并排序
*******************************************/
void* merge_exec(void *para)
{
  int threadIndex=*(int*)para; 
  int blockLen=DataNum/threadNum;
  int* temp=new int[blockLen];
  int offset=threadIndex*blockLen;
  mergesort(randInt,offset,offset+blockLen-1,temp);
}

合并多个已经排好序的块。代码如下:

/***********************************************
*函数名称:mergeBlocks
*参数:   pDataArray:块内有序的数组 arrayLen:数组长度
*        blockNum:块数 resultArray:存放排序的结果
*说明:   合并有序的块
************************************************/
inline void mergeBlocks(int* const pDataArray,int arrayLen,const int blockNum,int* const resultArray)
{
    int blockLen=arrayLen/blockNum;
    int blockIndex[blockNum];//各个块中元素在数组中的下标,VC可能不支持变量作为数组的长度,解决办法可使用宏定义
    for(int i=0;i<blockNum;++i)//初始化块内元素起始下标
    {
        blockIndex[i]=i*blockLen;
    }
    int smallest=0;
    for(int i=0;i<arrayLen;++i)//扫描所有块内的所有元素
    {  
      for(int j=0;j<blockNum;++j)//以第一个未扫描完的块内元素作为最小数
      {
       if(blockIndex[j]<(j*blockLen+blockLen))
       {
        smallest=pDataArray[blockIndex[j]];
        break;
       }
      }
      for(int j=0;j<blockNum;++j)//扫描各个块,寻找最小数
      {
        if((blockIndex[j]<(j*blockLen+blockLen))&&(pDataArray[blockIndex[j]]<smallest))
        {
          smallest=pDataArray[blockIndex[j]];
        }
      }
      for(int j=0;j<blockNum;++j)//确定哪个块内元素下标进行自增
      {
        if((blockIndex[j]<(j*blockLen+blockLen))&&(pDataArray[blockIndex[j]]==smallest))
        {
          ++blockIndex[j];
          break;
        }
      }
      resultArray[i]=smallest;//本次循环最小数放入结果数组
    }
}

main函数中创建多线程完成并行排序,代码如下:

int main(int argc,char* argv[])
{
    int threadBum=8;
    int blockNum=threadNum;
    struct timeval ts,te;
    srand(time(NULL));
    for(int i=0;i<DataNum;++i)
    {
      randInt[i]=rand();
    }
    pthread_t tid[blockNum],ret[blockNum],threadIndex[blockNum];

    //--------Two-way Merge Sort-------
    gettimeofday(&ts,NULL);
    for(int i = 0; i < threadNum; ++i)
    {
        threadIndex[i]=i;
        ret[i] = pthread_create(&tid[i], NULL,merge_exec,(void *)(threadIndex+i));
        if(ret[i] != 0){
             cout<<"thread "<<i<<" create error!"<<endl;
             break;
         }
    }
    for(int i = 0; i <threadNum; ++i)
    {
         pthread_join(tid[i], NULL);
    }
    mergeBlocks(randInt,DataNum,threadNum,resultInt);
    gettimeofday(&te,NULL);
    cout<<"MergeSort time: "<<(te.tv_sec-ts.tv_sec)*1000+(te.tv_usec-ts.tv_usec)/1000<<"ms"<<endl;
    }

8线程情况下,测试性能为4.223s,加速比3.68。针对机器的缓存大小,通过提高缓存命中率,可继续进行算法优化,提高排序性能。


参考文献

[1]百度百科.归并排序 [2]白话经典算法系列之五 归并排序的实现

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

python中的zip、lambda、map操作

python 中有几个比较酷炫的操作,比如:zip、lambda、map 一、zip操作 zip字面意思:拉链。这么记,把几个东西扔到一个包里,拉上拉链,就算打...

3126
来自专栏Java后端技术

这个坑,是时候填上了~

​  这两天,在网上逛的时候,发现了如下的一道面试题,感觉还有蛮有意思的,要是不仔细看还真容易掉到坑里面。第一眼看起来比较绕,所以比较难理解。最终我跳出了这个坑...

681
来自专栏日常学python

爬虫必学知识之正则表达式下篇

这是日常学python的第13篇原创文章 继上篇文章说了正则表达式的简单用法,那今天我们就继续说一下正则表达式的复杂的用法。好了,废话不多说,直接进入正题。 正...

5657
来自专栏轮子工厂

3. C语言 -- 叫你一声你敢答应嘛

\(@^0^@)/ 嗨!大家好,我是呆博~前两天的文章还满意嘛,如果有不满意的地方尽管提,我一定……嗯……能做到的我一定做。今天准备给大家分享第三篇文章,变量与...

1155
来自专栏Java架构师学习

为Java程序员金三银四精心挑选的五十道面试题与答案

1、面向对象的特征有哪些方面? 【基础】 答:面向对象的特征主要有以下几个方面: 1)抽象:抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地...

3566
来自专栏数据科学与人工智能

【Python环境】Python函数式编程指南(2):函数

2. 从函数开始 2.1. 定义一个函数 如下定义了一个求和函数: def add(x, y): return x + y 关于参数和返回值的语法细节可以参考...

2175
来自专栏和蔼的张星的图像处理专栏

174. 删除链表中倒数第n个节点双指针

给定一个链表,删除链表中倒数第n个节点,返回链表的头节点。 样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数第二个节点之后,...

622
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第3章 Python的数据结构、函数和文件3.1 数据结构和序列3.2 函数3.3 文件和操作系统3.4 结论

本章讨论Python的内置功能,这些功能本书会用到很多。虽然扩展库,比如pandas和Numpy,使处理大数据集很方便,但它们是和Python的内置数据处理工具...

4606
来自专栏python学习指南

python字典

本篇将介绍Python里面的字典,更多内容请参考:Python学习指南 Python是什么? Python内置了字典dict的支持,dict全称dicti...

2778
来自专栏Angular&服务

angular2关于内置通道的使用

minIntegerDigits是要使用的最小数字的整数数字。 默认为1 minFractionDigits是分数后的最小位数。 默认为0 maxFra...

802

扫码关注云+社区