当前位置:   article > 正文

八大排序——冒泡排序的优化算法及性能分析(C语言)_不同冒泡排序算法的后验分析

不同冒泡排序算法的后验分析

冒泡排序(Bubble Sort)

1、冒泡排序的思想:它重复地走访需要排序的数列,按照已经规定好的排序顺序,每一次比较相邻两个元素,如果他们的顺序错误就把他们交换过来。 直到没有再需要交换的元素,该数列就排序完成。

2、冒泡排序的算法运作(由小到大的排列顺序):

有一个数组a[10],用变量i表示它的下标(i从0开始)——

  1. 比较两个相邻元素a[i]和a[i+1],如果a[i]>a[i+1],就交换这两个数的位置;
  2. 重复执行第一步,直到比较到最后一对的时候(例:首次是a[8]和a[9],此 时,a[9]的值为该数组的最大值,这个值属于有序数列);
  3. 对所有元素(除了有序数列里的元素),重复执行第一步和第二步,每执行完一次,都会找到当前比较的数里最大的那个(有序数列就会增加一个);
  4. 随着参与比较的元素越来越少,最终没有任何一对元素需要比较的时候,排序完成。

 

3、传统的冒泡排序图示:

 

 

传统的冒泡排序的代码:

  1. int a[8]={3,2,5,8,4,7,6,9};
  2. for(int i=0;i<8;i++)//外层循环:要比较的次数;
  3. {
  4. for(int j=0;j<7-i;j++)内层循环:每次比较时,要比较的元素的范围;(这里就相当于j<n-i-1
  5. {
  6. if(a[j]>a[j+1])交换的三条语句
  7. {
  8. int temp=a[j];
  9. a[j]=a[j+1];
  10. a[j+1]=temp;
  11. }
  12. }
  13. }

4、优化1——定义一个flag,用来判断有没有进行交换,如果在某次内层循环中没有交换操作,就说明此时数组已经是有序了的,不用再进行判断,这样可以节省时间。

  1. int flag=1;
  2. for(int i=0;i<8&&flag;i++){
  3. flag=0;
  4. for(int j=0;j<7-i;j++){
  5. if(a[j]>a[j+1]){
  6. int temp=a[j];
  7. a[j]=a[j+1];
  8. a[j+1]=temp;
  9. flag=1;
  10. }
  11. }
  12. }

5、优化2——每一次交换记录最后一次交换的位置,为零的时候就停止。

  1. int i= 8 -1; //初始时,最后位置保持不变,相当于a.length-1
  2. while ( i ) {
  3. int pos= 0; //每趟开始时,无记录交换
  4. for (int j= 0; j< i; j++)
  5. if (a[j]> a[j+1]) {
  6. pos= j; //记录交换的位置
  7. int temp = a[j];
  8. a[j]=a[j+1];
  9. a[j+1]=temp;
  10. }
  11. i= pos; //为下一趟排序作准备
  12. }

 

6、优化3——鸡尾酒排序(Cocktail Sort)(又名:双向冒泡排序 (Bidirectional Bubble Sort)、波浪排序 (Ripple Sort)、摇曳排序 (Shuffle Sort)、飞梭排序 (Shuttle Sort) 和欢乐时光排序 (Happy Hour Sort)

原理:此算法以双向进行排序,鸡尾酒排序等于是冒泡排序的轻微变形

和传统冒泡的比较:不同的地方在于从低到高然后从高到低,而冒泡排序每次都是从低到高去比较序列里的每个元素。可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只能从一个方向进行比对,每次循环只移动一个项目

 

图解:


代码:

  1. public void cocktail_sort(int[] a){
  2. int left = 0, right = a.length-1;
  3. int temp;
  4. while(left<right){
  5. for(int i=left;i<right;i++){ //找到当前排序元素里最大的那个,放在右侧
  6. if(arr[i]>a[i+1]){
  7. temp = a[i];
  8. arr[i] = a[i+1] ;
  9. a[i+1] = temp;
  10. }
  11. }
  12. right--;
  13. for(int j=right;j>left;j--){//找到当前排序元素里最小的那个,放在左侧
  14. if(a[j-1]>a[j]){
  15. temp = a[j];
  16. a[i] = a[j+1] ;
  17. a[j+1] = temp;}
  18. }
  19. left++;
  20. }
  21. }

 

7、性能分析:

时间复杂度:冒泡排序在平均和最坏情况下的时间复杂度都是O(n^2),最好情况下都是O(n);

空间复杂度:O(1);

稳定性:冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不必再去交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/806070
推荐阅读
相关标签
  

闽ICP备14008679号