// 冒泡改进优化利用flag-pos-双向排序.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//2024年4月9日
#include <iostream>
using namespace std;
void bubblesort(int a[],int len)
{
int i = 0; int n = 0; int k = len - 1;
//n记录前面n个有序的数，k记录一趟排序最后一次交换的位置
int flag = 0;//标志位，使用前记得赋初值
int pos1 = 0,pos2=0; //pos1记录正向排序最后交换的位置，pos2记录反向排序最后的位置，其实可以只用一个变量pos
//因为k=pos1,n=pos2,可以仔细观察pos1和pos2的作用范围
int temp = 0;
//for (int i = 0; i < len - 1; i++)//确定排序的趟数,考虑i可以等于n吗？
//for (int i = n; i < len - 1; i++)//确定排序的趟数,考虑i可以等于n吗？n位前面n个有序的数
/* 设置一标志性变量pos, 用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位, 故在进行下一趟排序时只要扫描到pos位置即可。
因为k=pos1,n=pos2,可以仔细观察pos1和pos2的作用范围；这样可以减少每轮排序需要比较的元素数量，提高排序效率。*/
//n记录前面n个有序的数，k记录一趟排序最后一次交换的位置
for (int i = n; i <k; i++)//进行正向排序，从前往后找，k记录最后一次交换的位置
{
pos1 = 0, flag = 0;//进行一趟排序，重新为pos1和flag赋初值，如果逆序则修改pos1和flag
//flag标志位，使用前记得赋初值，因为前一趟排序中如果逆序flag=1（因为flag在前一趟排序中可能被更改）
for (int j = n; j < k; j++) {//进行正向排序，从前往后找
if (a[j]>a[j + 1]) {//逆序交换
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = 1;//修改标志位，没有交换flag=0
pos1 = j;//在每次比较过程中，如果满足交换条件则交换，并将当前最大值的索引位置标记出来
}
}
for (int count = 0; count < len; count++)//test
cout << a[count];
cout << endl; std::cout << "Hello World!\n";//test
k = pos1;//k记录一趟排序最后一次交换的位置
if (flag == 0)//一趟排序没有交换，以后不需要排序
{
return;
}
flag = 0; pos2 = 0;//进行一趟排序，重新为pos2和flag赋初值，如果逆序则修改pos2和flag
for (int j = k; j >n; j--) {//进行反向排序，从后往前找
if (a[j] < a[j - 1]) {//逆序交换
temp = a[j-1];
a[j - 1] = a[j];
a[j] = temp;
flag = 1;//修改标志位
pos2 = j - 1;//记录交换位置，在每次比较过程中，如果满足交换条件则交换，并将当前最大值的索引位置标记出来
}
}
for (int count = 0; count < len; count++)//test
cout << a[count];
cout << endl; std::cout << "kkkkkkkkkk!\n";//test
n=pos2;//n记录最后一次交换的位置
if (flag == 0)//一趟排序没有交换，以后不需要排序
{
return;
}
}
//for(int count=0;count<len;count++)//test
// cout << a[count];
}
int main()
{
int a[] = {1,2,5,7,4,3,6,0};
int len = 8;
bubblesort(a,len);
//for (int count = 0; count < len; count++)//test
// cout << a[count];
std::cout << "Hello World!\n";
}
// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单
// 入门使用技巧:
// 1. 使用解决方案资源管理器窗口添加/管理文件
// 2. 使用团队资源管理器窗口连接到源代码管理
// 3. 使用输出窗口查看生成输出和其他消息
// 4. 使用错误列表窗口查看错误
// 5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
// 6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
/*冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，
也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
尽管冒泡排序对于小型数据集合可能足够有效，但是对于大型数据集合，它的效率则相对较低。因此，针对冒泡排序的改进算法应运而生。以下是一些常见的改进方法：
1. 设置一标志性变量pos, 用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位, 故在进行下一趟排序时只要扫描到pos位置即可。
这样可以减少每轮排序需要比较的元素数量，提高排序效率。（在程序中k=pos1，n=pos2）
2. 双向冒泡排序（鸡尾酒排序，Cocktail Sort）：在冒泡排序的基础上，增加了一个从右向左的冒泡过程。即先从左向右进行一次冒泡排序，然后从右向左进行一次冒泡排序。
如此反复进行，直到排序完成。这种改进后的冒泡排序效率更高。
3. 带标记的冒泡排序：在每次比较过程中，如果满足交换条件则交换，并将当前最大值的索引位置标记出来。当一趟排序结束后，将未标记的最大值放到序列的最后。
通过这种方式，一趟排序下来，可以得到一个最大的元素，同时其他元素相对有序。然后对剩余的n - 1个元素继续进行带标记的冒泡排序，直到所有元素都排序完毕。
这些改进算法在一定程度上提高了冒泡排序的效率，但仍然无法与一些更高效的排序算法（如快速排序、归并排序等）相媲美。在实际应用中，应根据具体场景和需求选择合适的排序算法。*/
