首页 / 算法 / 排序算法总结——冒泡排序与鸡尾酒排序
排序算法总结——冒泡排序与鸡尾酒排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法总结——冒泡排序与鸡尾酒排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2549字,纯文字阅读大概需要4分钟。
内容图文
1、 冒泡排序
冒泡排序(bubble sort),是一种基础的交换排序。基本思想是,把相邻的元素两辆进行比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧相邻元素时,位置不变。
冒泡排序是一种稳定排序,值相等的元素并不会打乱原本的顺序。由于该排序算法每一轮都要遍历所有元素,总共遍历(元素数量-1)轮,平均时间复杂度为O(n2)。
升级版1:
对于序列的后半部分已经是有序的情况,如果能判断出有序,并作出标记,那么剩下的几轮排序就不必执行了。利用bool变量isSorted作为标记,如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,则说明数列已然有序,直接跳出大循环。
升级版2:
界定序列有序区。在每一次排序后,记录下来最后一次元素交换的位置,该位置即为无序数列的边界,再往后就是有序区了。
class Solution { public: void bubble_sort(int* data, int length) { if (data == nullptr || length <= 0) return; // 有序标志,每一轮的初始值都是true; bool isSorted = true; // 无序数列的边界,每次比较到这即停止 int sortBoard = length - 1; for (int i = 0; i < length - 1; ++i) { for (int j = 0; j < length - i - 1; ++j) { int temp = 0; if (data[j] > data[j + 1]) { temp = data[j + 1]; data[j + 1] = data[j]; data[j] = temp; // 因为有元素进行交换,所以不是有序的,标记变为false; isSorted = false; // 将无序数列的边界更新为最后一次交换元素的位置 sortBoard = j; } } if (isSorted) break; } } };
测试代码:
void test() { int data[] = { 5, 8, 6, 3, 9,2,1,7 }; int length = sizeof(data) / sizeof(int); Solution M; M.bubble_sort(data, length); for (int i = 0; i < length; ++i) cout << data[i] << " "; cout << endl; }
2、 鸡尾酒排序(cocktail sort)
鸡尾酒排序法的元素比较和交换过程是双向的。在大部分元素已经有序的情况下,减少排序的次数。缺点就是代码量较大。
class Solution { public: void cocltail_sort(int* data, int length) { if (data == nullptr || length <= 0) return; int temp = 0; for (int i = 0; i < length / 2; ++i) { // 有序标志,每一轮的初始值都为true; bool isSorted = false; // 奇数轮,从左向右比较和变换 for (int j = i; j < length - i - 1; ++j) { if (data[j] > data[j + 1]) { temp = data[j + 1]; data[j + 1] = data[j]; data[j] = temp; // 因为有元素交换,所以不是有序的,标记变为false isSorted = false; } } if (isSorted) break; // 偶数轮,将isSorted重新标记为true; isSorted = false; for (int j = length - i - 1; j > i; --j) { if (data[j] < data[j - 1]) { temp = data[j - 1]; data[j - 1] = data[j]; data[j] = temp; // 因为有元素交换,所以不是有序的,标记变为false isSorted = false; } } if (isSorted) break; } } };
用一个特殊的测试案例:
void test() { int data[] = { 2, 3, 4, 5, 6, 7, 8, 1 }; int length = sizeof(data) / sizeof(int); Solution M; M.cocltail_sort(data, length); for (int i = 0; i < length; ++i) cout << data[i] << " "; cout << endl; }
内容总结
以上是互联网集市为您收集整理的排序算法总结——冒泡排序与鸡尾酒排序全部内容,希望文章能够帮你解决排序算法总结——冒泡排序与鸡尾酒排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。