C++ 中通过交换相邻的奇偶对能得到的最小数

目标是重新排列给定数字的数字，以生成最小的可能数字，同时确保相邻数字表示偶数-奇数对。这在 C++ 中被称为“交换相邻偶数-奇数对”问题。

1. 冒泡排序方法
2. 贪心法

1. 冒泡排序方法

冒泡排序是一种流行且易于理解的排序算法，可有效解决各种排序问题。当用于识别通过交换相邻偶数-奇数对可以获得的最小数字时，冒泡排序方法提供了一个简单的解决方案。

使用此方法，我们从左到右查看数字的数字。我们迭代地遍历数字，比较相邻的对。如果相邻的对（偶数后跟奇数）顺序错误，我们交换它们以纠正顺序。重复此过程，直到不再需要交换以确保相邻数字形成偶数-奇数对。

算法步骤

步骤 1： 输入一个未排序的数字数组。

步骤 2： 创建一个循环，重复遍历数组，直到每个元素都排序。

步骤 3： 在循环中遍历数组中的每对相邻元素。

步骤 4： 验证每对中第一个元素是奇数，第二个元素是偶数。如果为 true，则交换元素。

步骤 5： 将刚刚交换的元素与数组中它之前的元素进行比较。如果需要，用较小的元素替换之前交换的元素。

步骤 6： 重复该过程，直到每对都经过验证和排序。

步骤 7： 如果在任何迭代期间没有执行任何交换，则数组已排序，并且可以终止循环。

步骤 8： 排序过程完成后，打印排序后的数组。

示例

让我们举一个例子来说明在 C++ 中使用冒泡排序方法交换相邻偶数-奇数对问题。

输出

 
Please enter the number of elements: 8
Enter the elements separated by space: 7 2 5 9 10 12 8 1
1 5 7 9 2 8 10 12   

说明

此 C++ 代码使用冒泡排序方法对整数数组进行排序，该方法确保相同奇偶性的整数保持相同的相对顺序，并且偶数-奇数对按升序排序。BubbleSort 函数根据指定条件迭代地交换数组中的相邻元素。该方法在每次迭代中根据相邻元素是否形成偶数-奇数对或具有相同奇偶性但顺序错误来执行交换。如果在迭代期间没有进行任何交换，则 swapped 标志表示数组已经排序，这通过跳出循环优化了排序过程。

之后，主函数要求用户输入数组的元素和元素数量，使用 BubbleSort 排序数组，并打印排序后的数组。

2. 贪心方法

• 从数字最左边的数字开始。
• 从左到右遍历数字的数字。
• 如果前一个数字是偶数，后一个数字是奇数，则交换数字。
• 重复此过程，直到到达数字的末尾或不再有可用的交换。
• 通过交换相邻的偶数-奇数对，生成的数字将是最小的可能数字。

示例

让我们举一个例子来说明在 C++ 中使用贪心方法交换相邻偶数-奇数对问题。

输出

 
Please enter the number: 2145367
The smallest number after swapping the adjacent even-odd pairs is: 2145637   

说明

此 C++ 代码交换给定数字（以字符串表示）中的相邻偶数-奇数对，以尝试发现最小的可能数字。smallestNumberSwappingPairs 函数遍历字符串，找到偶数索引处的偶数数字和奇数索引处的奇数数字。为了保持偶数-奇数配对，如果找到这样的对，它会交换这些数字。之后，主函数提示用户输入一个数字；它运行 smallestNumberSwappingPairs 函数来交换相邻的偶数-奇数对，以获得最小的可能数字。之后，打印结果。总的来说，该代码有效地使用交换方法来最小化数字，同时保持偶数-奇数对的顺序。