“可食用”通过精心收集，向本站投稿了6篇C语言二路归并排序算法，这次小编在这里给大家整理后的C语言二路归并排序算法，供大家阅读参考。
篇1：C语言二路归并排序算法
写了个二路归并的归并排序小代码，直接贴上来
/*
file:quick.cpp
author:www.5dkx.com
*/
#include
using namespace std;
void Merge(int a[],int low,int mid,int high,int b[]);
void MSort(int a[],int low,int high,int b[]);
void main
{
int a[]={4,5,9,10,51,6,46,36,6,56,67,45,36};
int b[13];
MSort(a,0,12,b);
for(int i=0;i<13;i++)
cout<
cout<
for(int j=0;j<13;j++)
cout<
cout<
}
void Merge(int a[],int low,int mid,int high,int b[])
{
int i=low,j=mid+1,k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<=a[j])
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
while(i<=mid)
{
a[k]=a[i];
k++;
i++;
}
while(j<=high)
{
a[k]=a[j];
k++;j++;
}
}
void MSort(int a[],int low,int high,int b[])
{
if(low==high)
b[low]=a[low];
else
{
int mid=(low+high)/2;
MSort(a,low,mid,b);
MSort(a,mid+1,high,b);
Merge(a,low,mid,high,b);
}
}
篇2：归并排序算法的JAVA实现Java
package Utils.Sort; /** * MI LY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'“>归并排序，要求待排序的数组必须实现 Comparable 接口 */ public class MergeSort implements SortStrategy { private Compa
package Utils.Sort;
/**
*MILY: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'”>归并排序，要求待排序的数组必须实现Comparable接口
*/
public class MergeSort implements SortStrategy
{private Comparable[] bridge;
/**
*利用归并排序算法对数组obj进行排序
*/
public void sort(Comparable[] obj)
{if (obj == null)
{throw new NullPointerException(“The param can not be null!”);
}
bridge = new Comparable[obj.length];//初始化中间数组mergeSort(obj, 0, obj.length - 1);//归并排序
bridge = null;
}
/***将下标从left到right的数组进行归并排序
*@param obj要排序的数组的句柄
*@param left要排序的数组的第一个元素下标
*@param right要排序的数组的最后一个元素的下标
*/
private void mergeSort(Comparable[] obj, int left, int right)
{if (left < right)
{int center = (left + right)/2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}
/**
*将两个对象数组进行归并，并使归并后为升序，
归并排序算法的JAVA实现Java
，
归并前两个数组分别有序
*@param obj对象数组的句柄
*@param left左数组的第一个元素的下标
*@param center左数组的最后一个元素的下标
*@param right右数组的最后一个元素的下标
*/
private void merge(Comparable[] obj, int left, int center, int right)
{int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right)
{//从两个数组中取出小的放入中间数组
if (obj[left].compareTo(obj[mid]) <= 0)
{bridge[third++] = obj[left++];
}else
bridge[third++] = obj[mid++];
}
//剩余部分依次置入中间数组while (mid <= right)
{bridge[third++] = obj[mid++];
}
while (left <= center){bridge[third++] = obj[left++];
}
//将中间数组的内容拷贝回原数组copy(obj, tmp, right);
}
/***将中间数组bridge中的内容拷贝到原数组中
*@param obj原数组的句柄
*@param left要拷贝的第一个元素的下标
*@param right要拷贝的最后一个元素的下标
*/
private void copy(Comparable[] obj, int left, int right)
{while (left <= right)
{obj[left] = bridge[left];
left++;
}}
}
原文转自：www.ltesting.net
篇3：疯狂的Java算法――插入排序，归并排序以及并行归并排序
从古至今的难题
在IT届有一道百算不厌其烦的题，俗称排序，不管是你参加BAT等高端笔试，亦或是藏匿于街头小巷的草根笔试，都会经常见到这样一道百年难得一解的问题。
今天LZ有幸与各位分享一下算法届的草根明星，排序届的领衔大神——插入排序以及归并排序。最后，在头脑风暴下，LZ又有幸认识了一位新朋友，名叫并行归并排序。接下来，咱们就一一认识一下，并且在最后来一次“算林大会”吧。
插入排序简介
插入排序，算林称最亲民的排序算法，插入排序采用最简单的插入方式对一个整数数组进行排序。它循环数组中从第二个开始的所有元素，并且将每一个循环到的元素插入到相应的位置，从而实现排序的目的。
插入排序的代码展示
使用Java代码描述插入排序，可以用以下的代码。
package algorithm;
/**
* @author zuoxiaolong
*
*/
public abstract class InsertSort {
public static void sort(int[] numbers){
for (int i = 1; i < numbers.length; i++) {
int currentNumber = numbers[i];
int j = i - 1;
while (j >= 0 && numbers[j] >currentNumber) {
numbers[j + 1] = numbers[j];
j--;
}
numbers[j + 1] = currentNumber;
}
}
}
复制代码
这个算法从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。
插入排序理解起来比较简单，因此LZ就不过多的解释它的实现原理了，尚未理解的猿友可以自行研究。
插入排序的性能分析
接下来，咱们来简单分析一下插入排序的性能。首先，插入排序当中有两个循环，假设数组的大小为n，则第一个循环是n－1次，第二个while循环在最坏的情况下是1到n－1次。因此插入排序的时间复杂度大约为如下形式。
1+2+3+4+...＋n－1 ＝ n（n－1）/ 2 ＝ O（n2）
时间复杂度为输入规模的2次函数，可见插入排序的时间复杂度是比较高的。这是原理上的简单分析，最后在“算林大会”中，各位可以清楚的看到插入排序随着输入规模的增长，时间会指数倍的上升。
归并排序简介
归并排序，算林届的新秀，引领着分治法的潮流。归并排序将排序问题拆分，比如分成两个较小的数组，然后对拆分后的数组分别进行排序，最后再将排序后的较小数组进行合并。
这种思想是一种算法设计的思想，很多问题都可以采用这种方式解决。映射到编程领域，其实就是递归的思想。因此在归并排序的算法中，将会出现递归调用。
归并排序的代码展示
归并排序主要由两个方法组成，一个是用于合并两个已经排序的数组的方法，一个则是递归方法，用于将问题无限拆分。接下来咱们一起看看归并排序的Java代码展示，如下所示。
package algorithm;
/**
* @author zuoxiaolong
*
*/
public abstract class MergeSort {
public static void sort(int[] numbers){
sort(numbers, 0, numbers.length);
}
public static void sort(int[] numbers,int pos,int end){
if ((end - pos) >1) {
int ffset = (end + pos) / 2;
sort(numbers, pos, offset);
sort(numbers, offset, end);
merge(numbers, pos, offset, end);
}
}
public static void merge(int[] numbers,int pos,int offset,int end){
int[] array1 = new int[offset - pos];
int[] array2 = new int[end - offset];
System.arraycopy(numbers, pos, array1, 0, array1.length);
System.arraycopy(numbers, offset, array2, 0, array2.length);
for (int i = pos,j=0,k=0; i < end ; i++) {
if (j == array1.length) {
System.arraycopy(array2, k, numbers, i, array2.length - k);
break;
}
if (k == array2.length) {
System.arraycopy(array1, j, numbers, i, array1.length - j);
break;
}
if (array1[j] <= array2[k]) {
numbers[i] = array1[j++];
} else {
numbers[i] = array2[k++];
}
}
}
}
可以看到，归并排序将一个长度为n的数组平均分为两个n/2的数组分别进行处理，因此，在sort方法中又调用了两次sort方法自身。当数组大小为1时，则认为该数组为已经为排好序的数组。因此在sort方法中，需要end与pos相差大于2时，才需要进一步拆分，这也是递归的终止条件。
此外，在代码中，使用了Java提供的arraycory函数进行数组复制，这种直接复制内存区域的方式，将会比循环赋值的方式速度更快。有些算法实现会给merge方法中的两个临时数组设置哨兵，目的是为了防止merge中for循环的前两个if判断。为了方便理解，LZ这里没有设置哨兵，当某一个数组的元素消耗完时，将直接使用arraycopy方法把另外一个数组copy到numbers当中。
归并排序的性能分析
与插入排序一样，咱们来简单分析一下归并排序的时间复杂度。咱们假设数组的大小为n，sort方法的时间复杂度为f（end－pos）。简单的分析merge方法的复杂度，不难发现为（end－pos）＊2，这个结果的前提是咱们认为arraycopy方法的复杂度为length参数。
基于以上的假设，由于end－pos的初始值为n，因此归并排序的复杂度大约为如下形式。
2＊f（n/2） ＋ 2＊n ＝ 2＊（2＊f（n/4）＋2＊（n/2）） ＋ 2＊n＝4＊f（n/4） ＋ 2＊n ＋ 2＊n ＝ n ＊f（1） ＋ 2＊n ＋...＋2＊n
其中f（1）的时间复杂度为常量，假设f（1）＝c，而2＊n将有log2n个。因此咱们得到归并排序的最终时间复杂度为如下形式。
cn ＋ 2n＊log2n ＝ O（n＊log2n）
归并排序的时间复杂度与插入排序相比，已经降低了很多，这一点在数组的输入规模较大时将会非常明显，因为log函数的增加速度将远远低于n的增加速度。
并行归并排序简介
并行归并排序是LZ在学习归并排序时意淫出来的，最近LZ正在研究Java的并发编程，恰好归并排序的子问题有一定的并行度与独立性，因此LZ版的并发归并排序就这样诞生了。事后，LZ也人肉过并行归并排序这个家伙，发现早已众所周知，不过在不知道的情况下自己能够想到是不是也应该窃喜一下呢。
并行归并排序与普通的归并排序没有多大区别，只是利用现在计算机多核的优势，在有可能的情况下，让两个或多个子问题的处理一起进行。这样一来，在效率上，并行归并排序将会比归并排序更胜一筹。
并行归并排序的代码展示
并行归并排序主要对sort方法进行了修改，基础的merge方法与普通的归并排序是一样的。因此在进行并行归并排序时，引用了归并排序的一些方法，具体的代码如下所示。
package algorithm;
import java.util.concurrent.CountDownLatch;
/**
* @author zuoxiaolong
*
*/
public abstract class MergeParallelSort {
private static final int maxAsynDepth = (int)(Math.log(Runtime.getRuntime.availableProcessors())/Math.log(2));
public static void sort(int[] numbers) {
sort(numbers, maxAsynDepth);
}
public static void sort(int[] numbers,Integer asynDepth) {
sortParallel(numbers, 0, numbers.length, asynDepth >maxAsynDepth ? maxAsynDepth : asynDepth, 1);
}
public static void sortParallel(final int[] numbers,final int pos,final int end,final int asynDepth,final int depth){
if ((end - pos) >1) {
final CountDownLatch mergeSignal = new CountDownLatch(2);
final int ffset = (end + pos) / 2;
Thread thread1 = new SortThread(depth, asynDepth, numbers, mergeSignal, pos, offset);
Thread thread2 = new SortThread(depth, asynDepth, numbers, mergeSignal, offset, end);
thread1.start();
thread2.start();
try {
mergeSignal.await();
} catch (InterruptedException e) {}
MergeSort.merge(numbers, pos, offset, end);
}
}
static class SortThread extends Thread {
private int depth;
private int asynDepth;
private int[] numbers;
private CountDownLatch mergeSignal;
private int pos;
private int end;
/**
* @param depth
* @param asynDepth
* @param numbers
* @param mergeSignal
* @param pos
* @param end
*/
public SortThread(int depth, int asynDepth, int[] numbers, CountDownLatch mergeSignal, int pos, int end) {
super();
this.depth = depth;
this.asynDepth = asynDepth;
this.numbers = numbers;
this.mergeSignal = mergeSignal;
this.pos = pos;
this.end = end;
}
@Override
public void run() {
if (depth < asynDepth) {
sortParallel(numbers,pos,end,asynDepth,(depth + 1));
} else {
MergeSort.sort(numbers, pos, end);
}
mergeSignal.countDown();
}
}
}
在这段代码中，有几点是比较特殊的，LZ简单的说明一下，
1，分解后的问题采用了并行的方式处理，并且咱们设定了一个参数asynDepth去控制并行的深度，通常情况下，深度为(log2CPU核数)即可。
2，当子问题不进行并行处理时，并行归并排序调用了普通归并排序的方法，比如MergeSort.sort和MergeSort.merge。
3，因为合并操作依赖于两个子问题的完成，因此咱们设定了一个合并信号（mergeSignal），当信号发出时，才进行合并操作。
并行归并排序在原理上与普通的归并排序是一样的，只是对于子问题的处理采用了一定程度上的并行，因此如果猿友们理解归并排序，那么并行归并排序并不难理解。
并行归并排序的性能分析
并行归并排序只是将普通归并排序中一些可并行的操作进行了并行处理，因此在总体的时间复杂度上并没有质的变化，都是O（n＊log2n）。
由于并行归并排序将某些排序操作并行操作，因此在性能上一定是快于普通归并排序算法的。不过这也不是一定的，当数组规模太小时，并行带来的性能提高可能会小于线程创建和销毁的开销，此时并行归并排序的性能可能会低于普通归并排序。
算林大会
接下来，就是一周一度的算林大会了，本次算林大会主要由以上三种算法参加，胜者将会成为本周度最受欢迎算法。接下来是算林大会的代码，请各位猿友过目。
package algorithm;
import java.io.File;
import java.lang.reflect.Method;
import java.util.Random;
/**
* @author zuoxiaolong
*
*/
public class SortTests {
public static void main(String[] args) {
testAllSortIsCorrect();
testComputeTime(“MergeParallelSort”, 40000, 5);
testComputeTime(“MergeSort”, 40000, 5);
testComputeTime(“InsertSort”, 400, 5);
}
public static void testAllSortIsCorrect() {
File classpath = new File(SortTests.class.getResource(“”).getFile());
File[] classesFiles = classpath.listFiles();
for (int i = 0; i < classesFiles.length; i++) {
if (classesFiles[i].getName().endsWith(“Sort.class”)) {
System.out.println(“---测试” + classesFiles[i].getName() + “是否有效---”);
testSortIsCorrect(classesFiles[i].getName().split(“\\.”)[0]);
}
}
}
public static void testSortIsCorrect(String className){
for (int i = 1; i < 50; i++) {
int[] numbers = getRandomIntegerArray(1000 * i);
invoke(numbers, className);
for (int j = 1; j < numbers.length; j++) {
if (numbers[j] < numbers[j-1]) {
throw new RuntimeException(className + “ sort is error because ” + numbers[j] + “<” + numbers[j-1]);
}
}
}
System.out.println(“---” + className + “经测试有效---”);
}
public static void testComputeTime(String className,int initNumber,int times,Object... arguments) {
long[] timeArray = new long[times];
for (int i = initNumber,j = 0; j < times; i = i * 10,j++) {
timeArray[j] = computeTime(i, className, arguments);
}
System.out.print(className + “时间增加比例：”);
for (int i = 1; i < timeArray.length ; i++) {
System.out.print((float)timeArray[i]/timeArray[i - 1]);
if (i < timeArray.length - 1) {
System.out.print(“,”);
}
}
System.out.println();
}
public static long computeTime(int length,String className,Object... arguments){
int[] numbers = getRandomIntegerArray(length);
long start = System.currentTimeMillis();
System.out.print(“开始计算长度为”+numbers.length+“方法为”+className+“参数为[”);
for (int i = 0; i < arguments.length; i++) {
System.out.print(arguments[i]);
if (i < arguments.length - 1) {
System.out.print(“,”);
}
}
System.out.print(“]，时间为”);
invoke(numbers, className, arguments);
long time = System.currentTimeMillis()-start;
System.out.println(time + “ms”);
return time;
}
public static int[] getRandomIntegerArray(int length){
int[] numbers = new int[length];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = new Random().nextInt(length);
}
return numbers;
}
public static void invoke(int[] numbers,String className,Object... arguments){
try {
Class
Class
parameterTypes[0] = int[].class;
for (int i = 0; i < arguments.length; i++) {
parameterTypes[i + 1] = arguments[i].getClass();
}
Method method = clazz.getDeclaredMethod(“sort”, parameterTypes);
Object[] parameters = new Object[parameterTypes.length];
parameters[0] = numbers;
for (int i = 0; i < arguments.length; i++) {
parameters[i + 1] = arguments[i];
}
method.invoke(null, parameters);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}
以上代码testAllSortIsCorrect方法首先验证了三种算法的正确性，也就是说经过sort方法后，数组是否已经升序排列。需要一提的是，由于插入排序的性能太低，因此插入排序测试的最大规模为400万，而归并排序测试的最大规模为4亿。
接下来，大家就一起看看运行结果吧。以下是在LZ的mac pro上的运行结果，硬件配置为16G内存，4核i7。这种配置下，异步深度（asynDepth）默认为log24=2。
---测试InsertSort.class是否有效---
---InsertSort经测试有效---
---测试MergeParallelSort.class是否有效---
---MergeParallelSort经测试有效---
---测试MergeSort.class是否有效---
---MergeSort经测试有效---
开始计算长度为40000方法为MergeParallelSort参数为[]，时间为6ms
开始计算长度为400000方法为MergeParallelSort参数为[]，时间为44ms
开始计算长度为4000000方法为MergeParallelSort参数为[]，时间为390ms
开始计算长度为40000000方法为MergeParallelSort参数为[]，时间为3872ms
开始计算长度为400000000方法为MergeParallelSort参数为[]，时间为47168ms
MergeParallelSort时间增加比例：7.3333335,8.863636,9.9282055,12.181818
开始计算长度为40000方法为MergeSort参数为[]，时间为7ms
开始计算长度为400000方法为MergeSort参数为[]，时间为81ms
开始计算长度为4000000方法为MergeSort参数为[]，时间为839ms
开始计算长度为40000000方法为MergeSort参数为[]，时间为9517ms
开始计算长度为400000000方法为MergeSort参数为[]，时间为104760ms
MergeSort时间增加比例：11.571428,10.358025,11.343266,11.00767
开始计算长度为400方法为InsertSort参数为[]，时间为0ms
开始计算长度为4000方法为InsertSort参数为[]，时间为3ms
开始计算长度为40000方法为InsertSort参数为[]，时间为245ms
开始计算长度为400000方法为InsertSort参数为[]，时间为23509ms
开始计算长度为4000000方法为InsertSort参数为[]，时间为3309180ms
InsertSort时间增加比例：Infinity,81.666664,95.9551,140.76227
复制代码
首先可以看到，三种算法都是运行正确的。接下来，咱们可以对比一下三种算法的性能。
根据输出结果，规模为400万时的区别是最明显与直观的。并行归并排序仅需要390ms就完成了400万规模的排序，而普通的归并排序则需要839ms才可以，至于插入排序，简直是不可理喻，竟然需要300多万ms，大约50分钟。
咱们再来看三者的时间增长趋势。两种归并排序基本上与规模的增长趋势相似，每当规模增加10倍时，时间也基本上增加10倍，而插入排序则几乎是以100倍的速度在增加，刚好是数组规模增长速度的平方。其中的Infinity是因为当数组规模为400时，毫秒级别的计时为0ms，因此当除数为0时，结果就为Infinity。
当然了，这一次结果具有一定的随机性，猿友们可以在自己的电脑上多实验几次观察一下，不过插入排序的时间实在让人等的 。
篇4：go语言睡眠排序算法实例分析
这篇文章主要介绍了go语言睡眠排序算法,实例分析了睡眠排序算法的原理与实现技巧,需要的朋友可以参考下
本文实例讲述了go语言睡眠排序算法，分享给大家供大家参考。具体分析如下：
睡眠排序算法是一个天才程序员发明的，想法很简单，就是针对数组里的不同的数开多个线程，每个线程根据数的大小睡眠，自然睡的时间越长的，数越大，哈哈，搞笑吧，这种算法看起来很荒唐，但实际上很天才，它可以充分利用多核cpu进行计算。
代码如下:
package main
import (
“fmt”
“time”
)
func main() {
tab := []int{1, 3, 0, 5}
ch := make(chan int)
for _, value := range tab {
go func(val int){
time.Sleep( int64(val)*10000000 )
fmt.Println(val)
ch <-val
}(value)
}
for _ = range tab {
<-ch
}
}
希望本文所述对大家的Go语言程序设计有所帮助，
篇5：C语言五子棋胜负判定算法及源代码
五子棋胜负的判定，一般有一下两种算法：
1.扫描整个棋盘，分别扫描四个方向是否有5个连子，网上找了很多五子棋源码都是用此算法，这意味着每下一个棋子都要扫描一遍19×19的棋盘，复杂而且低效，代码略。
2.每下一字，从该子开始扫描其四个方向(例如：从该子的(x-4，y)坐标开始扫描横向)是否存在5个连子。此算法较为常用，而且不涉及更为复杂的数据结构。
另外，为解决扫描越界的问题，在声明棋盘棋子位置时，可声明一个(4+19+4)×(4+19+4)的棋盘，而让棋子偏移(4，4)个坐标。
算法2源代码如下：
static void IfWin(int x,int y,int color)
{
TCHAR win[20];
int a,b;
if(stone[x][y]==1)
wcscpy_s(win,_T(“黑棋胜利!”));
else
wcscpy_s(win,_T(“白棋胜利!”));
for(a=x-4;a<=x+4;a++)//判断横
if(stone[a][y]==color&&stone[a+1][y]==color&&stone[a+2][y]==color&&stone[a+3][y]==color&&stone[a+4][y]==color)
{MessageBoxW(Xqwl.hWnd,win,TEXT(“”),MB_OK);return;}
for(b=y-4;b<=y+4;b++)//判断竖
if(stone[x][b]==color&&stone[x][b+1]==color&&stone[x][b+2]==color&&stone[x][b+3]==color&&stone[x][b+4]==color)
{MessageBoxW(Xqwl.hWnd,win,TEXT(“”),MB_OK);return;}
for(a=x-4,b=y-4;a<=x+4;a++,b++)//判断右斜
if(stone[a][b]==color&&stone[a+1][b+1]==color&&stone[a+2][b+2]==color&&stone[a+3][b+3]==color&&stone[a+4][b+4]==color)
{MessageBoxW(Xqwl.hWnd,win,TEXT(“”),MB_OK);return;}
for(a=x-4,b=y+4;a<=x+4;a++,b--)//判断左斜
if(stone[a][b]==color&&stone[a+1][b-1]==color&&stone[a+2][b-2]==color&&stone[a+3][b-3]==color&&stone[a+4][b-4]==color)
{MessageBoxW(Xqwl.hWnd,win,TEXT(“”),MB_OK);return;}
}
以上源码编译器为VS，
篇6：C语言猴子吃桃问题算法
有前面几道题的基础，这道题还是比较简单的，我们来看问题：
猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个，以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。
1.分析，我们先来看看这个问题的数学模型：
设n为第一天摘的桃子数。那么根据已知条件有：
s1=n/2-1;
s2=s1/2-1;
…
s10=s9/2-1=1;
那么很显然有：
s9=（s10+1）*2;
s8=（s9+1）*2;
…
s1=（s2+1）*2;
s0=（s1+1）*2=n;
那么利用10趟循环就可以解决问题，
2.我们来看源代码：
#include
#include
//猴子吃桃问题
int main（）
{
int n=1;
int day=10;
while（day>0）
{
n=2*（n+1）； //昨天的桃子数等与今天桃子数加1的二倍
day--;
}
printf（“Totally %d peaches!\n”,n）；
}
这里为了方便理解是从10到1循环，其实怎么循环都行，只要保证循环次数是10即可。
