改进冒泡排序（循序渐进）
在文章中附上了所有代码，希望能对你有所帮助到你，喜欢的话就点个赞和关注吧，谢谢！
一下是基于普通冒泡排序的改进，编译的话是基于Linux系统的，如果是Windows等等的话可以直接复制代码用正常编译器编译运行就好啦，Linux编译命令行看不懂的话，可以进主页看看我后面发的gcc教程哦！
一：在原来的经典冒泡排序上如何改进使其减少占用的存储空间？
我发现这道题可以使用位运算，在思考过后发现用位运算确实可以减少一个中间变量的存储空间，改进代码如下：
#includevoid bubble_sort(int arr[], int len) { int i, j,ci_sum=0,tang_sum=0; for (i = 0; i < len - 1; i++){ for (j = 0; j < len - 1 - i; j++){ if (arr[j] > arr[j + 1]) { arr[j]=arr[j]^arr[j+1]; arr[j+1]=arr[j+1]^arr[j]; arr[j]=arr[j]^arr[j+1]; ci_sum++; }} tang_sum++; } printf("次数：%dn，趟数：%dn",ci_sum,tang_sum); } int main() { int arr[]={22, 34, 3, 32, 82, 55, 4, 50, 37, 5, 64, 35, 9, 70,100}; //int arr[]={3,4,5,9,22,32,34,35,37,50,55,64,70,82,100}; int len = (int) sizeof(arr) / sizeof(*arr); bubble_sort(arr, len);//冒泡排序 int i; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("n排序结束，n"); return 0; }
运行正常：（位运算看不懂的朋友，我主页也有先关的教程哦）
而如果按照我一开始的想法用指针的话就会非常地麻烦，因为用指针，一旦被存储地址的变量的值发生改变，后面所有调用到这个指针的值也会随着改变，所以还是位运算简单！
二：判断是否中途排序已完成从而提前结束排序（同时减少排序次数）
了解过冒泡排序都知道，它是一趟又一趟地两两比较的，有一个问题就是如果我的数组在中途就已经排好了，或者我的数组根本就是已经排好的，那么再慢慢地排就会浪费非常多的资源，所以要改进一下，我尝试了往排序算法中引入一个“观察员”用来监视数据的交换情况,如果某一趟排序中,数据序列中的数据元素已经没有交换了,我们就可以认为排序已经完成,不需要再进行剩下的比较，结合一的位运算尝试编写代码如下：
#includevoid bubble_sort(int arr[], int len) { int i, j,ci_sum=0,tang_sum=0,flag=1; for (i = 0; i < len - 1&&flag==1; i++){ flag=0; for (j = 0; j < len - 1 - i; j++){ if (arr[j] > arr[j + 1]) { arr[j]=arr[j]^arr[j+1]; arr[j+1]=arr[j+1]^arr[j]; arr[j]=arr[j]^arr[j+1]; ci_sum++; flag=1;//有交换 }} tang_sum++; } printf("次数：%dn，趟数：%dn",ci_sum,tang_sum); } int main() { int arr[]={22, 34, 3, 32, 82, 55, 4, 50, 37, 5, 64, 35, 9, 70,100}; //int arr[]={3,4,5,9,22,32,34,35,37,50,55,64,70,82,100}; int len = (int) sizeof(arr) / sizeof(*arr); bubble_sort(arr, len);//冒泡排序 int i; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("n排序结束，n"); return 0; }
其中flag就可以理解为我们的‘哨兵’（观察员）
运行效果：
可见使用同一个乱序的数组，该方法就已经可以节省了两次内部排序，和四趟循环，效果显著！
如果使用同一个已经有序的数组是什么效果？下面对比：
其实就是把我上面那个代码的乱序数组注释掉，把一个已经排好序的数组正常写入
有哨兵运行效果：
一次都不用排，直接可以输出；
无哨兵：
可见内部没有元素改动，但依然要循环14次
- 双向冒泡排序（定向冒泡排序）
第一种写法：
升序：从低到高遍历把大值换后面去，即如果arr[num-i]>arr[num-i+1],那么就交换这两个的值，然后再从高到低遍历把小值换前面去，即如果arr[num-i+1]>arr[num-i]，再交换这两个的值，不断循环上述过程即完成排序
类似于这样，然后再结合上面我们做的一、二，代码如下：
#includevoid bubble_sort(int arr[], int len) { int left = 0; // 初始化边界 int right = len - 1; int cishu=0,tangshu=0; while (left < right) { for (int i = left; i < right; i++)// 前半轮,就是将大元素放到后面，1----->num等 { if (arr[i] > arr[i + 1]) { arr[i]=arr[i]^arr[i+1]; arr[i+1]=arr[i+1]^arr[i]; arr[i]=arr[i]^arr[i+1]; cishu++; } } right--; for (int i = right; i > left; i--) // 后半轮,就是将小元素放到前面，num----->1等 { if (arr[i - 1] > arr[i]) { arr[i]=arr[i]^arr[i-1]; arr[i-1]=arr[i-1]^arr[i]; arr[i]=arr[i]^arr[i-1]; cishu++; } } left++; tangshu++; } printf("次数：%dn趟数：%dn",cishu,tangshu); } int main() { int arr[]={22, 34, 3, 32, 82, 55, 4, 50, 37, 5, 64, 35, 9, 70,100}; //int arr[]={3,4,5,9,22,32,34,35,37,50,55,64,70,82,100}; int len = (int) sizeof(arr) / sizeof(*arr); bubble_sort(arr, len);//冒泡排序 int i; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("n排序结束，n"); return 0; }
运行效果：
相较于有哨兵的都减少了3趟，对于没有哨兵的减少了7趟，效果是真的显著！
第二种理解：
假设我们有num个元素，那么我们排序过程可以按下列过程理解：
1.遍历[num--------->1]位置.(我这里的num至1不是索引哈，只是数学上的位置，如果是索引应改为num-1--------->0)从底部(num位置)往上查找最小的值,并把最小值放到第1位置.
2.遍历[2--------->num]位置,从第2个位置往底部查找最大值,并把最大值放到第num位置.
3.遍历[num-1------>2]位置,从第num-1位置往上查找最小值,并把最小值放在第2位置.
4.遍历[3-------->num-1]位置,从第2个位置往底部查找最大值,并把最大值放到第num-1位置
我后面会再更一期这章噢，这部分代码会放在下一章，请前往我的主页查看噢，同时预计在下一章我还会改进上面代码比如加入“哨兵”等等，在下一章我也会补充一下c语言判断数组最大最小元素的方法，位运算等等，点个赞支持一下呗！
