排序之冒泡排序
程序员文章站
2022-05-12 17:55:46
...
冒泡排序
该排序通过将数组嵌套循环,
将相邻的两个对象进行比较,正序排序为例,如果a[0]的对象大于a[1]的对象,
则将两个对象位置交换,将小的对象置前,直到数组结束,排序的过程中每次循环时,指针始终
指向是当前最大的对象,将次对象与后面的对象相比较,当小于后一位对象时,置换,指针依然指向
当前最大的对象。当一次循环结束时,已将最大的对象移至
数组尾部。以此类推完成排序。
class Sort{
private long[] a;
private int nElement;
public Sort(long[] array){
this.a = array;
}
public static void main(String[] args) {
long[] array = new long[]{5,3,1,7,9,2,0};
Sort b = new Sort(array);
b.bubbleSort();
System.out.println(b);
}
public void bubbleSort(){
int out,in;
int step = 0;
System.out.println("bubble---");
for(out = a.length -1 ; out > 0; out --){
for(in = 0; in < out; in++){
if(a[in+1] < a[in]){
long temp = a[in];
a[in] = a[in+1];
a[in+1] = temp;
step++;
}
}
}
System.out.println(step);
}
public String toString(){
StringBuilder b = new StringBuilder();
for(long l : a){
b.append(l);
b.append(",");
}
return b.toString();
}
}
例:
对数组 {5,3,1,7,9,2,0} 进行排序 a[0] > a[1]
loop1:3,5,1,7,9,2,0, 将前两个对象比较,a[0] 和 a[1] 位置对换,此时数组的指针a[1]
loop2: 3,1,5,7,9,2,0, 进行比较,a[1] > a[2] 继续将大对象置后。
loop3: 3,1,5,7,9,2,0, 第三次比较,a[2] < a[3] 位置没有调换,指针继续向后移,依然指向当前最大的对象。
loop4 3,1,5,7,9,2,0,
loop5: 3,1,5,7,2,9,0,
loop6: 3,1,5,7,2,0,9, 第一轮循环结束,最大的对象已经移至最后一位,
此数组用了 21 次比较 (N*(N-1)/2) 完成 排序,置换操作13次。
内层每循环一次,指针都向后移动一位,当前后两个对象大小不符条件时,发生对换,
指针始终指向的是当前最大的对象。
(注意,内层循环终止位置 应该截止到已完成排序的位置。)
下一篇: 交换排序--冒泡排序