计算机科学

首页 > 计算机科学

奇偶排序

2018-08-28 09:41:48     所属分类:排序算法
奇偶排序
Odd even sort animation.gif
使用奇偶排序法对一列随机数字进行排序的过程
分类 排序算法
数据结构 数组
最坏时间复杂度

奇偶排序,或奇偶换位排序,或砖排序[1],是一种相对简单的排序算法,最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。

该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换。下一步重复该操作,但针对所有的(偶-奇)位置数字对。如此交替进行下去。

目录

  • 1 处理器数组的排序
  • 2 Batcher奇偶归并排序
  • 3 程序代码
    • 3.1 C语言
    • 3.2 C++
    • 3.3 Python
    • 3.4 JavaScript
    • 3.5 PHP
  • 4 参考文献
  • 5 外部链接

处理器数组的排序

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

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

Batcher奇偶归并排序

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

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

程序代码

C语言

void odd_even_sort(int arr, int len) {
	int odd_even, i;
	int temp;
	int sorted = 0;
	while (!sorted) {
		sorted = 1;
		for (odd_even = 0; odd_even < 2; odd_even++)
			for (i = odd_even; i < len - 1; i += 2)
				if (arri > arri + 1) {
					temp = arri;
					arri = arri + 1;
					arri + 1 = temp;
					sorted = 0;
				}
	}
}

C++

template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void odd_even_sort(T arr, int len) {
	int odd_even, i;
	bool sorted = false;
	while (!sorted) {
		sorted = true;
		for (odd_even = 0; odd_even < 2; odd_even++)
			for (i = odd_even; i < len - 1; i += 2)
				if (arri > arri + 1) {
					swap(arri, arri + 1);
					sorted = false;
				}
	}
}

Python

# 假设已有列表a等待排序
while True:
    sorted = True
    # 处理奇-偶对
    for i in xrange(1, len(a)-1, 2):
        if ai > ai+1:
           ai, ai+1 = ai+1, ai # 交换
           sorted = False
    # 处理偶-奇对
    for i in xrange(0, len(a)-1, 2):
        if ai > ai+1:
           ai, ai+1 = ai+1, ai # 交换
           sorted = False
    if sorted:
        break

JavaScript

Array.prototype.odd_even_sort = function() {
	var odd_even, i;
	var temp;
	var sorted = 0;
	while (!sorted) {
		sorted = 1;
		for ( odd_even = 0; odd_even < 2; odd_even++)
			for ( i = odd_even; i < this.length - 1; i += 2)
				if (thisi > thisi + 1) {
					temp = thisi;
					thisi = thisi + 1;
					thisi + 1 = temp;
					sorted = 0;
				}
	}
	return this;
};

PHP

function swap(&$x, &$y) {
	$t = $x;
	$x = $y;
	$y = $t;
}
function odd_even_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
	$sorted = 0;
	while (!$sorted) {
		$sorted = 1;
		for ($odd_even = 0; $odd_even < 2; $odd_even++)
			for ($i = $odd_even; $i < count($arr) - 1; $i += 2)
				if ($arr$i > $arr$i + 1) {
					swap($arr$i, $arr$i + 1);
					$sorted = 0;
				}
	}
}

参考文献

  1. ^ Phillips, Malcolm. Array Sorting. [3 August 2011]. (Sort Techniques 原始内容 请检查|url=值 (帮助)存档于2011年10月28日). 
  2. ^ N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151).
  3. ^ S. Lakshmivarahan, S. K. Dhall, and L. L. Miller, Franz L. Alt and Marshall C. Yovits, 编, Parallel Sorting Algorithms, Advances in computers (Academic Press), 1984, 23: 295–351, ISBN 9780120121236 
  4. ^ Robert Sedgewick. Algorithms in Java, Parts 1-4 3rd. Addison-Wesley Professional. 2003: 454–464. ISBN 9780201361209. 
  5. ^ Allen Kent and James G. Williams. Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. 1993: 33–38. ISBN 9780824722821. 

外部链接


上一篇:Bogo排序
下一篇:比较排序
相关推荐