本文主要介绍如何使用多线程的方式实现Sample-sort（据说是Google搜索使用的排序算法），使用的是C语言，但是其中用到了部分的C++ 标准输入输出库，接下来从下面几个步骤来进行展示：
1）sample-sort的主要思想；
2）sample-sort的多线程实现步骤详解；
3）sample-sort程序的测试；
一、sample-sort的主要思想
sample-sort其实是一种变种的桶排序[bucket sort]算法，如果你对桶排序不是清楚，可以查看此链接的博文进行了解：桶排序
input ： array to be sorted（length = n）
output: sorted array
1. 确定sample-sort中bucket的个数 k；
2. “smartly”选择出k-1 个splitters（将整个数组分成k个bucket的分类器）
2.1 将被排序的数据均分为k个block，每个block中有（n/k）个元素，并且给每一个block进行排序；
2.2 从每个block中选出k-1 个相距间隔一样的元素，作为备选的splitter；
2.3 对这个k*(k-1)个元素进行排序，然后在这些元素当中选择（k-1）个相距间隔一样；
的元素；
3. 使用第二个步骤中确定的(k-1)个splitters进行桶排序
具体实例可以看下图1 ：
图 1 sample sort 实例详细过程
二、sample-sort的多线程实现步骤详解
步骤详解图：
图 2 步骤详解图
1）step1: 读取用户的数据 k（thread的个数，也就是bucket的个数），filename（保存原始数据的文本文件）；其代码如下图3所示：
图 3 读取用户的参数代码
2）step2: 将file中的数据全部读取到 array_raw中，然后新建一个长度和array_raw长度一样的数组array_sorted；函数功能实现如下图4：
图 4 从文件中读取数据
3）step3: 根据上面描述的“智能”选择splitters的算法，将array_raw中的k-1 个splitter给找出来，其功能函数实现如下图：
图 5 找到相应的splitters
对于数据为DATA1.txt 并且 k=5 的情况下，找出的splitter如下图所示：
图 6 对应k＝5时的splitters
4）Step 4： 确定每个bucket中处理数据的值的范围，确定bucket中处理好的数据放回array_sorted中的上下界
4.1．确定每个bucket中处理的数据的值的范围，例如，根据上面的splitter 280648543，知道bucket1中处理的数据的值的范围为 （-inf，280648543］；
4.2．确定每个bucket中处理好的数据放回到array_sorted的上下界，以免后面thread回写数据时发生冲突；例如第一个bucket－1处理的数据时100个，那么bucket-1中处理完数据之后回写到array_sorted的［0, 100］的位置当中，紧接着如果bucket-2中需要处理的数据时200个，那么其回写到array_sorted的上下界为［100，300］；
其实现代码如下图7：
图 7 查找bucket处理的值的范围和边界范围
对于数据为DATA1.txt 并且 k=5 的情况下，输出的每个bucket中处理的值的范围 和 处理好的数据放回到array_sorted数组中的上下界的结果如下图8，由该结果，我们可以知道：第一个bucket处理的数据的值的范围从（－1，280648543］，然后放回到array_sorted中的上下界为[0, 2804 ）；
图 8 查找bucket处理的值的范围和边界范围实例
5）Step 5：将step4中得到的结果以参数的方式，传送给代表该bucket的thread中，该参数中包括的具体参数如下图9所示：
图 9 传给thread的参数结构体的内容
然后这一步骤5 主要完成的工作如下：
5.1. 准备好传送给k个thread的paras，新建k个threa运行，并且等待k个thread运行完成。代码如下图10 所示；
图 10 创建thread 并且等待其执行完
5.2. thread中执行的函数的主要操作是，将array_raw(原始数组)中符合其值范围的数据挑选出来，然后将这些数据进行排序，然后写回到array_sorted数组当中，其代码如下图11；
图 11 thread 执行函数代码
5.3. 所有thread执行完之后，将排好序的数据写入到DATA_SORTED1.txt和文件中，其代码如下图12；
图 12 写结果到文本文件中
DATA_SORTED1.txt的结果如下图13所示，这个时候咱们已经得到了最终的结果：
图 13 DATA1 排序之后的结果
三、sample-sort程序的测试
为了测试这个程序的正确性，对测试数据DATA1.txt，分别设置 k 为2，4，8，10进行测试，对于上面的情况，最后输出的文件当中排序都没有问题，和图12中内容是一样的，下面主要是将k=2,4,6,8,10 输出的计算过程中的结果展示出来；
1. k= 2 时，其输出的结果如下图14所示：
图 14 k=2 时的输出
2. k= 4 时，其输出的结果如下图15所示：
图 15 k=4 时的输出
3. k= 8 时，其输出的结果如下图16所示：
图 16 k=8 时的输出
4. k= 10 时，其输出的结果如下图17所示：
图 17 k=10 时的输出
声明：
1. 联系作者，你可以私信新浪微博：@谷谷_z
2.如果在文章当中发现有描述错误的地方，还请您不吝指出，万分感谢！
3.此文章系本人原创作品，转发请注明出处！
源文件资源：
链接: https://pan.baidu.com/s/1eSHWjZ0 密码: y56s
网友评论