数据结构学习之冒泡算法

class ArrayBub{
private long[] a;
private int nElems;
public ArrayBub(int max) {
a = new long[max];
nElems = 0;
}
public void insert(long value) {
a[nElems] = value;
nElems++;
}
public void display() {
for (int j = 0; j < nElems; j++) {
System.out.print(a[j] + " ");
}
System.out.println(" ");
}
public void bubbleSort() {
int out;
int in;
for (out = nElems - 1; out > 1; out--) {
for (in = 0 ; in < out; in++) {
if (a[in] > a[in+1])
swap(in,in+1);
}
}
}
private void swap(int n1,int n2){
long temp = a[n1];
a[n1] = a[n2];
a[n2] = temp;
}
}
public class bubbleSort {
public static void main(String[] args) {
ArrayBub arr = new ArrayBub(100);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display();
arr.bubbleSort();
arr.display();
}
}

算法思路

将最大的数据项放在数组的最后面。

外层for循环的计数器out从数组的最后面开始，即out等于nElems-1，每经过一次out-1。下标大于out的都是已经排序好的，变量out在每完成一次内部循环（计数器减一）向左一位，一次算法就不用再处理那些排序好的数据。

内层for循环的计数器in从数组的最左边算起，内部循环体每次自增1，当等于out的时候结束循环。

第一次外层循环，out=9，进入内循环，比较a[0]和a[1]，然后两者间的较大值与a[2]比较，以此类推，一直比较到a[8]{这个理解很重要，因为并不会立刻比较到a[9]，下面有一个a[n+1]，故这里面就是最大为a[8]，然后让这个最大的a[8]去和a[9]比较，也可以理解为in实际上最大就是nElmes-2}这9个数，找出其中的最大数，然后放在a[9]的位置。

定义了一个数组类，主函数中创建了一个数组对象，通过圆点运算符来访问和调用它的数据和方法，在这个数组类中定义了一个insert()方法（用来对数组插入），一个display()方法（用来打印数据），一个bubbleSort()方法，就是本程序的核心，swap()方法用来实现bubbleSort()。

这里将方法全部定义在数组类中，是为了在主函数中不进行方法的编写，使得代码看起来更加简洁，这样容易维护。

冒泡算法的效率：

若数组中有N个数据项，则需要比较的次数为
N+(N-1)+(N-2)+…+1=N*(N-1)/2
忽略减一，且大O算法中不算常数，故需要O(N^2)时间级别。

最后

以上就是优雅纸鹤为你收集整理的数据结构学习之冒泡算法的全部内容，希望文章能够帮你解决数据结构学习之冒泡算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。