算法之奇偶排序讲解

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

各位小伙伴们大家晚上好呀，今天讲解下排序中的奇偶排序，奇偶排序并没有在数据结构书中有专门的小节，但在考研893/895中都有出现过，而且都是作为大题出现，当然是一个必须要掌握的知识点了，下面就开始我们的讲解吧！

一、基本概念

奇偶排序是一种比较简单的排序，类似于冒泡排序，分为奇数列元素的排序和偶数列元素的排序。在实际中，常用于多处理器环境中。

二、算法思想

1. 处理待排序数组中奇数列的元素与其右侧相邻的元素进行比较，将较小的元素排列在前面；

2. 处理待排序数组偶数列的元素与其右侧相邻的元素进行比较，将较小的元素排列在前面；

3. 重复前面两步，直到排序序列有序为止。

三、代码实现

// 交换元素
void Swap(int *a, int *b) {// 需要使用指针操作
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
// 奇偶排序
void OddEvenSort(int A[], int n) {// 排序序列，待排序元素个数
    int i;
    bool flag;
    do {
        flag = false; // 标记本趟排序是否进行了元素交换
        for (i = 1; i < n; i += 2) //先扫描所有奇数项
            if (A[i] > A[i+1]) {   //比较相邻元素
                flag = true;       //标记交换过
                Swap(A[i], A[i+1] ); //交换
            }
        for (i = 0; i < n; i += 2) //再扫描所有偶数项
            if (A[i] > A[i+1]) {   //比较相邻元素
                flag = true;       //标记交换过
                Swap(A[i], A[i+1]);//交换
            }
    } while (flag);
}

四、总结

在第三部分代码中，flag用于标记本趟奇数和偶数排序是否进行了元素交换，如果没有进行元素交换，说明排序序列已经有序了，可以结束排序。奇偶排序虽然是分奇数列和偶数列依次进行排序，但是时间时间复杂度依然为O(n²)。重点是要掌握奇偶排序的思想，并可以根据算法思想写出代码。

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬