算法 排序算法 数据结构 奇偶排序（Odd-Even Sort）

奇偶排序（Odd-Even Sort）是一种基于比较的排序算法，它通过多轮迭代将数组中的奇数和偶数分别进行排序，最终将数组完全有序。这种排序算法通常用于并行计算或者多线程环境下，因为它可以将数组分成两个部分并同时进行排序，从而提高排序效率。

奇偶排序的基本思想如下：

将待排序数组分成奇数位和偶数位两部分。

当排序奇数位（数组下标Index为1，3，5，7……）：让arr[1]与arr[1+1]对比，arr[3]与arr[3+1]对比当排序偶数维(数组小标Index为0，2，4……)：让arr[0]与arr[0+1]对比，让arr[2]与arr[2+1]对比

分别对奇数位和偶数位进行排序，可以使用任何比较排序算法，如冒泡排序、快速排序等。重复上述步骤，直到数组完全有序。

例子：待排序序列{ 5, 2, 9, 1, 5, 6 }; 对奇数列和其相邻的偶数列进行排序：比较2与9，比较1与5。不进行交换操作。 对偶数列和其相邻的奇数列进行排序：比较5与2，9与1，5与6。进行两次交换操作。序列变为{2,5,1,9,5,6}。 对奇数列和其相邻的偶数列进行排序：比较5与1，9与5。进行两次交换操作。序列变为{2,1,5,5,9,6}。 对偶数列和其相邻的奇数列进行排序：比较2与1，5与5， 9与6。进行两次交换操作。序列变为{1,2,5,5,6,9}。 奇数列和偶数列都没有进行交换操作，排序完成。

在这个示例中，oddEvenSort 函数实现了奇偶排序算法，其中使用了冒泡排序来对奇数位和偶数位分别进行排序。通过多轮迭代，直到数组完全有序为止

#include

#include

using namespace std;

void oddEvenSort(int arr[], int size) {

bool sorted = false;

while (!sorted) {

sorted = true;

for (int i = 1; i < size - 1; i += 2) {

if (arr[i] > arr[i + 1]) {

swap(arr[i], arr[i + 1]); // 使用 swap 函数进行交换

sorted = false;

}

}

for (int i = 0; i < size - 1; i += 2) {

if (arr[i] > arr[i + 1]) {

swap(arr[i], arr[i + 1]); // 使用 swap 函数进行交换

sorted = false;

}

}

}

}

int main() {

int arr[] = {5, 2, 9, 1, 5, 6};

int size = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";

for (int i = 0; i < size; ++i) {

cout << arr[i] << " ";

}

cout << endl;

oddEvenSort(arr, size);

cout << "Sorted array: ";

for (int i = 0; i < size; ++i) {

cout << arr[i] << " ";

}

cout << endl;

return 0;

}

好文推荐