数据结构排序-冒泡排序

数据结构排序----冒泡排序
冒泡排序的原理:依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。
　　由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。（百度文库）

下面是代码的实现：
  
    测试数组：

    int[] a = { 6, 4, 3, 7, 9, 15, 1, 85, 67, 43 };
    第一种，也是最简单，同时也是最消耗资源的，代码如下

public static int[] sort1Asc(int ap[]) {int k = 0;int b = 0;int ac = 0;for (int i = 0; i < ap.length; i++) {k = 0;for (int j = 0; j < ap.length - 1; j++) {ac++;if (ap[j] > ap[j + 1]) {b++;k = ap[j];ap[j] = ap[j + 1];ap[j + 1] = k;}}}System.out.println("交换次数为：" + b);System.out.println("总共循环次数：" + ac);return ap;}

  
           执行结果：
              交换次数为：12
              总共循环次数：90
   第二种，减少总共循环次数（数据量大的时候很节约性能）。根据冒泡排序的原理，我们可以知道，当外层循环执行完一次的时候，其中一个值的位置可定时固定了，也就是他已经排序号了，所以在以后的排序中，我们就不需要访问他了，这样就可以减少一半的循环次数，我们知道，主要的排序效果是由内层循环做的，所以目标就是减少二次循环次数，下面是具体代码：

public static int[] sortAsc(int ap[]) {int k = 0;int b = 0;int ac = 0;for (int i = 0; i < ap.length; i++) {k = 0;//重点，控制二次循环的次数，因为最后i为，已经排好序了，所以就不需要再访问了for (int j = 0; j < ap.length - i - 1; j++) {ac++;if (ap[j] > ap[j + 1]) {b++;k = ap[j];ap[j] = ap[j + 1];ap[j + 1] = k;}}}System.out.println("交换次数为：" + b);System.out.println("总共循环次数：" + ac);return ap;}

   测试结果：

         交换次数为：12
         总共循环次数：45
  正如你看到的，交换次数没有改变，但是总共循环次数减少一半。下面我们继续研究

   第三种 减少总共循环次数的基础上，再减少交换次数，我们同新建一个变量，把每次的最小或者最大的位置保存下来，然后等内层循环执行结束，后在进行交换，这种方法主要是指定外层循环的位置为我们的参考值，内层循环的所有比较都是和他进行比较的。当内层循环结束后，如果需要交换，我们才进行交换。下面看代码：

     

public static int[] sort2Asc(int ap[]) {int k = 0;int b = 0;int ac = 0;int c = 0;for (int i = 0; i < ap.length; i++) {k = i;for ([color=red]int j =i+1[/color]; j < ap.length ; j++) {ac++;if (ap[k] > ap[j]) {k= j;}}if(k!=i){b++;c = ap[k];ap[k] = ap[i];ap[i] = c;}}System.out.println("交换次数为：" + b);System.out.println("总共循环次数：" + ac);return ap;}

测试结果：
   交换次数为：6
   总共循环次数：45
正如你想到的，交换次数减少了很多，而且总共循环次数也改变了。

我现在对冒泡算法的学习，就学到这里了，如果那么大牛，有更好的办法，可以讨论共同学习

      

查看更多 下一篇