编写 Python 程序对奇偶排序或奇偶转换排序进行排序

在本教程中，我们将学习移位排序（transposition sort），也称为砖排序（brick sort）或奇偶排序（parity sort）。它是一种相对简单的排序算法，最初是为具有本地互连的并行处理器开发的。该算法类似于冒泡排序，并具有许多相似的特征。它旨在比较列表中所有奇数/偶数索引的相邻元素对，如果一对元素的顺序错误，则交换这些元素。然后对偶数/奇数索引重复此步骤。然后，它在奇数/偶数和偶数/奇数步骤之间交替进行，直到列表被排序。

让我们通过一个例子来更好地理解它。

假设我们有一个整数列表。我们需要将数字安排为偶数在前，奇数在后。因此，我们需要先放置偶数，然后再放置奇数。

如果给定的列表是 a [3, 7, 8, 2, 1, 9, 4, 6]，结果将是 [2, 4, 6, 8, 3, 7, 9]。我们将使用以下步骤来解决此问题 -

设置 i := 0 且 j := 0

当 j < 列表长度时

o 如果 list[j] 是偶数，则交换 list[i] 和 list[j]，并将 i 增加 1

o 将 j 增加 1

返回列表

让我们将上述解决方案实现为 Python 代码 -

示例 -

输出 -

Original list:
[4, 3, 5, 1, 2]
Sorted order is: [1, 2, 3, 4, 5]

Original list:
[15, 29, 100, 23, -14, 45, 178, 192, 246, -118, 0, 7]
Sorted order is: [-118, -14, 0, 7, 15, 23, 29, 45, 100, 178, 192, 246]

解释 -

在上面的代码中，我们创建了一个名为 parity_sort 的函数，它接受一个列表作为参数。在函数中，我们初始化了列表的长度，并使用了嵌套的 for 循环。外层 for 循环将运行到列表的长度，内层循环将从模 2 开始到列表末尾，并跳过列表中的两个元素。如果下一个元素小于前一个元素，则交换这两个元素。一旦列表排序完成，函数将返回排序后的列表。

我们也可以使用 while 循环来解决此问题。让我们理解以下示例。

示例 -

输出 -

Original list: [4, 3, 5, 1, 2]
Sorted order is: [4, 2, 5, 1, 3]
Original list: [15, 29, 100, 23, -14, 45, 178, 192, 246, -118, 0, 7]
Sorted order is: [100, -14, 178, 192, 246, -118, 0, 23, 29, 45, 15, 7]

结论

在本教程中，我们实现了奇偶排序或偶奇排序。我们可以使用 for 循环或 while 循环来解决此问题。这个问题可能会在技术面试中出现。