查看“︁奇偶排序”︁的源代码

{{noteTA|G1=IT}}
{{算法信息框
|class=[[排序算法]]
|image=[[File:Odd even sort animation.gif]]
|caption=使用奇偶排序法对一列随机数字进行排序的过程
|data=[[数组]]
|time=<math>\Theta(n^2)</math>
|space=
|optimal=不
}}
'''奇偶排序'''（{{lang-en|Odd–even sort}}），或'''奇偶换位排序'''、'''砖排序'''<ref>{{cite web|last=Phillips|first=Malcolm|title=Array Sorting|url=http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging Sort Techniques|accessdate=3 August 2011|deadurl=yes|archiveurl=https://web.archive.org/web/20111028201105/http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging|archivedate=2011年10月28日}}</ref>，是一种相对简单的[[排序算法]]，最初发明用于有本地互连的并行计算。这是与[[冒泡排序]]特点类似的一种[[比较排序]]。

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

== 处理器数组的排序 ==

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

该算法可以有效地延伸到每个处理器拥有多个值的情况。在Baudet–Stevenson奇偶合并分割算法中，每个处理器在每一步对自己所拥有的子数组进行排序，然后与邻居执行合并分割或换位合并。<ref>
{{cite
 | journal = Advances in computers
 | editors = Franz L. Alt and Marshall C. Yovits
 | title = Parallel Sorting Algorithms
 | author = S. Lakshmivarahan, S. K. Dhall, and L. L. Miller
 | volume = 23
 | publisher = Academic Press
 | pages = 295–351
 | isbn = 9780120121236
 | date = 1984
 | url = http://books.google.com/books?id=Mo2Q-TEwKGUC&pg=PA322
 }}</ref>

==Batcher奇偶归并排序==
[[Batcher归并网络|Batcher奇偶归并排序]]是一种相关但更有效率的排序算法，采用比较-交换和完美-洗牌操作。<ref>
{{cite book
 | title = Algorithms in Java, Parts 1-4
 | edition = 3rd
 | author = Robert Sedgewick
 | publisher = Addison-Wesley Professional
 | year = 2003
 | isbn = 9780201361209
 | pages = 454–464
 | url = http://books.google.com/books?id=hyvdUQUmf2UC&pg=PA455
 }}</ref>

Batcher的方法在拥有广泛互连的并行计算处理器上效率不错。<ref>
{{cite book
 | title = Encyclopedia of Computer Science and Technology: Supplement 14
 | author = Allen Kent and James G. Williams
 | publisher = CRC Press
 | year = 1993
 | isbn = 9780824722821
 | page = 33–38
 | url = http://books.google.com/books?id=F9Y4oZ9qZnYC&pg=PA33
 }}</ref>

==程式代碼==

===C语言===
<syntaxhighlight lang=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 (arr[i] > arr[i + 1]) {
					temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
					sorted = 0;
				}
	}
}
</syntaxhighlight>

===C++===
<syntaxhighlight lang=cpp>
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 (arr[i] > arr[i + 1]) {
					swap(arr[i], arr[i + 1]);
					sorted = false;
				}
	}
}
</syntaxhighlight>

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

===JavaScript===
<syntaxhighlight lang=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 (this[i] > this[i + 1]) {
					temp = this[i];
					this[i] = this[i + 1];
					this[i + 1] = temp;
					sorted = 0;
				}
	}
	return this;
};
</syntaxhighlight>
===PHP===
<syntaxhighlight lang=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;
				}
	}
}
</syntaxhighlight>

== 参考文献 ==

{{reflist}}

==外部連結==
{{排序算法表}}
{{算法}}

[[Category:排序算法]]
[[Category:带有代码示例的条目]]