C语言 奇偶排序算法详解及实例代码_C 语言

C语言奇偶排序算法

奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换。下一步重复该操作,但针对所有的(偶-奇)位置数字对。如此交替进行下去。

使用奇偶排序法对一列随机数字进行排序的过程

处理器数组的排序

在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交换操作,交替以奇-偶、偶-奇的顺序。该算法由Habermann在1972年最初发表并展现了在并行处理上的效率。

该算法可以有效地延伸到每个处理器拥有多个值的情况。在Baudet–Stevenson奇偶合并分区算法中,每个处理器在每一步对自己所拥有的子数组进行排序,然后与邻居执行合并分区或换位合并。

Batcher奇偶归并排序

Batcher奇偶归并排序是一种相关但更有效率的排序算法,采用比较-交换和完美-洗牌操作。

Batcher的方法在拥有广泛互连的并行计算处理器上效率不错。

算法

举例:待排数组[6 2 4 1 5 9]

第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比

[6 2 4 1 5 9]

交换后变成

[2 6 1 4 5 9]

第二次比较偶数列,即6和1比,5和5比

[2 6 1 4 5 9]

交换后变成

[2 1 6 4 5 9]

第三趟又是奇数列,选择的是2,6,5分别与它们的邻居列比较

[2 1 6 4 5 9]

交换后

[1 2 4 6 5 9]

第四趟偶数列

[1 2 4 6 5 9]

一次交换

[1 2 4 5 6 9]

以下表现其单处理器算法,类似冒泡排序,较为简单但效率并不特别高。

// Completed on 2014.10.8 12:05
// Language: C99
//
// 版权所有(C)codingwu  (mail: [email protected])
// 博客地址:http://www.cnblogs.com/archimedes/

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
void swap(int *a, int *b)
{
  int t;
  t = *a;
  *a = *b;
  *b = t;
}
void printArray(int a[], int count)
{
  int i;
  for(i = 0; i < count; i++)
    printf("%d ",a[i]);
  printf("\n");
}
void Odd_even_sort(int a[], int size)
{
  bool sorted = false;
  while(!sorted)
  {
    sorted = true;
    for(int i = 1; i < size - 1; i += 2)
    {
      if(a[i] > a[i + 1])
      {
        swap(&a[i], &a[i + 1]);
        sorted = false;
      }
    }
    for(int i = 0; i < size - 1; i += 2)
    {
      if(a[i] > a[i + 1])
      {
        swap(&a[i], &a[i+1]);
        sorted = false;
      }
    }
  }
}
int main(void)
{
  int a[] = {3, 5, 1, 6, 9, 7, 8, 0, 11};
  int n = sizeof(a) / sizeof(*a);
  Odd_even_sort(a, n);
  printArray(a, n);
  return 0;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索c语言
, 奇偶排序算法
奇偶排序
c语言归并排序详解、c语言堆排序代码详解、冒泡排序c语言详解、c语言奇偶校验程序、c语言判断奇偶性,以便于您获取更多的相关知识。

时间: 2016-11-10

C语言 奇偶排序算法详解及实例代码_C 语言的相关文章

C语言 选择排序算法详解及实现代码_C 语言

选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

C语言之单向链表详解及实例代码_C 语言

1,单向链简洁. 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始:链表是使用指针进行构造的列表:又称为结点列表,因为链表是由一个个结点组装起来的:其中每个结点都有指针成员变量指列表中的下一个结点:列表是由结点构成,由head指针指向第一个成为表头的结点而终止于最后一个指向nuLL的指针: 2,例子要求: 根据示例代码中的例子,完成单向链表(single linked list)中的以字符串为数据的链表的插入.删除以及查找,并支持单向链表的反转

C语言 文件操作解析详解及实例代码_C 语言

C语言文件操作解析         在文件操作中除了打开操作以及读写操作,还有几种比较常见的操作.下面介绍一下这些操作中涉及到的函数. 一.移动位置指针的函数    rewind函数和fseek函数,这两个函数的原型是:    void rewind(FILE *fp);     将位置指针移动到文件首   int fseek(FILE *fp,long int offset,int origin);   将位置指针移动到距离origin的offset字节数的位置   其中对于fseek函数中的

C++函数重载详解及实例代码_C 语言

C++函数的重载 定义 在同一个作用域中,函数名相同,函数的参数列表不同的函数之间构成重载关系,在不同作用域中的同名函数遵循标识符隐藏的原则 ATTENTION:重载与函数的返回值类型无关,因为声明一个函数不需要返回类型,所以无法用来区分哪个函数 常函数和普通成员函数之间构成重载,重载时常对象调用常成员函数,一般对象调用一般成员函数 class A{ - public: void getVal()const{-} void getVal(){-} }; int main(){ const A a

C++ 继承详解及实例代码_C 语言

C++继承可以是单一继承或多重继承,每一个继承连接可以是public,protected,private也可以是virtual或non-virtual.然后是各个成员函数选项可以是virtual或non-virtual或pure virtual.本文仅仅作出一些关键点的验证. public继承,例如下: 1 class base 2 {...} 3 class derived:public base 4 {...} 如果这样写,编译器会理解成类型为derived的对象同时也是类型为base的对象

C语言 结构体数组详解及示例代码_C 语言

所谓结构体数组,是指数组中的每个元素都是一个结构体.在实际应用中,结构体数组常被用来表示一个拥有相同数据结构的群体,比如一个班的学生.一个车间的职工等. 定义结构体数组和定义结构体变量的方式类似,请看下面的例子: struct stu{ char *name; //姓名 int num; //学号 int age; //年龄 char group; //所在小组 float score; //成绩 }class[5]; 表示一个班级有5个学生. 结构体数组在定义的同时也可以初始化,例如: str

C语言之双向链表详解及实例代码_C 语言

1,双向链表简介. 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 2,例子要求: 完成双向链表的插入.删除以及查找,将学生管理系统使用的数组,以双向链表的方式实现,能够支持无限制的学生人数的增删改查以及保存. 3,代码实现. #include <stdio.h> #include <string.h> #include <

C++ 初始化列表详解及实例代码_C 语言

C++ 初始化列表 何谓初始化列表 与其他函数不同,构造函数除了有名字,参数列表和函数体之外,还可以有初始化列表,初始化列表以冒号开头,后跟一系列以逗号分隔的初始化字段.在C++中,struct和class的唯一区别是默认的访问性不同,而这里我们不考虑访问性的问题,所以下面的代码都以struct来演示. struct foo { string name ; int id ; foo(string s, int i):name(s), id(i){} ; // 初始化列表 }; 构造函数的两个执行

C++ boost::asio编程-异步TCP详解及实例代码_C 语言

C++ boost::asio编程-异步TCP 大家好,我是异步方式 和同步方式不同,我从来不花时间去等那些龟速的IO操作,我只是向系统说一声要做什么,然后就可以做其它事去了.如果系统完成了操作, 系统就会通过我之前给它的回调对象来通知我. 在ASIO库中,异步方式的函数或方法名称前面都有"async_ " 前缀,函数参数里会要求放一个回调函数(或仿函数).异步操作执行 后不管有没有完成都会立即返回,这时可以做一些其它事,直到回调函数(或仿函数)被调用,说明异步操作已经完成. 在ASI