排序算法：冒泡排序（Bubble Sort）

思路：
对一组乱序的数，自下而上两两进行比较交换，使较小的数上升，而较大的数下沉。

实现代码
<pre>
//value为待排序的数组
for(int i=0; i<value.length-1; i++) {
for(int j=value.length-1; j>i; j--) {
if(value[j-1] > value[j]) {
int tmp = value[j-1];
value[j-1] = value[j];
value[j] = tmp;
}
}
}
</pre>

前辈们提出的一些改进

1、设置一标志性变量flag,用于记录每趟排序中最后一次进行交换的位置。由于flag位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到flag位置即可。

改进代码
<pre>
//value为待排序的数组
int i = value.length - 1;//初始时,最后位置保持不变
while (i > 0) {
int flag = 0;
for (int j = 0; j < i; j++) {
if (value[j] > value[j + 1]) {
flag = j;//记录交换的位置
int tmp = value[j];
value[j] =value[j + 1];
value[j + 1] = tmp;
}
}
i = flag;//为下一趟排序作准备
}
</pre>

2、传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进代码
<pre>
//value为待排序的数组
int low = 0;
int high = value.length - 1;
int tmp, j;
while (low < high) {
for (j = low; j < high; ++j) {
if (value[j] > value[j+1]) {
tmp = value[j];
value[j]=value[j+1];
value[j+1]=tmp;
}
}
--high;//修改high值, 前移一位

for (j = high; j > low; --j) {
    if (value[j] < value[j-1]) {  
            tmp = value[j];
        value[j] = value[j-1];
        value[j-1] = tmp;
    }   
}
++low; //修改low值,后移一位  

}
</pre>

以上就是冒泡排序的基本实现思路和改进，为了更清楚的知道改进后对效率是否有较大的提升，我们进行如下实验。

随机生成一万个无序的含有一万个随机零到十万整数的数列，使用上面三种方法对其进行排序，分别记录比较次数和交换次数。

---

未经同意，不得转载。