排序算法总结——冒泡排序与鸡尾酒排序
2020-12-13 03:46
标签：更新 break iss bool 有序 基础 交换排序 界定 ted 1、 冒泡排序 冒泡排序（bubble sort），是一种基础的交换排序。基本思想是，把相邻的元素两辆进行比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。 冒泡排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。由于该排序算法每一轮都要遍历所有元素，总共遍历（元素数量-1）轮，平均时间复杂度为O(n2)。 升级版1： 对于序列的后半部分已经是有序的情况，如果能判断出有序，并作出标记，那么剩下的几轮排序就不必执行了。利用bool变量isSorted作为标记，如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，则说明数列已然有序，直接跳出大循环。 升级版2： 界定序列有序区。在每一次排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。 测试代码： 2、 鸡尾酒排序（cocktail sort） 鸡尾酒排序法的元素比较和交换过程是双向的。在大部分元素已经有序的情况下，减少排序的次数。缺点就是代码量较大。时间复杂度也是O(n2)。 用一个特殊的测试案例： 排序算法总结——冒泡排序与鸡尾酒排序 标签：更新 break iss bool 有序 基础 交换排序 界定 ted 原文地址：https://www.cnblogs.com/wyr-123-wky/p/11087389.htmlclass 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 1; ++i)
{
for (int j = 0; j 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 i)
cout " ";
cout endl;
}
class Solution
{
public:
void cocltail_sort(int* data, int length)
{
if (data == nullptr || length 0)
return;
int temp = 0;
for (int i = 0; i 2; ++i)
{
// 有序标志，每一轮的初始值都为true;
bool isSorted = false;
// 奇数轮，从左向右比较和变换
for (int j = i; j 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] 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 i)
cout " ";
cout endl;
}
上一篇：我县政府网站集群建设经验总结
下一篇：PHP显示中文乱码