冒泡排序的原理:依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第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
正如你想到的，交换次数减少了很多，而且总共循环次数也改变了。
(责任编辑：捉蛋网-刷机)
|
