算法之奇偶排序讲解
【摘要】 🎈 作者:Linux猿
🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
🎈 作者: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(n2)。重点是要掌握奇偶排序的思想,并可以根据算法思想写出代码。
CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
欢迎小伙伴们点赞👍、收藏⭐、留言💬
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)