冒泡排序原理

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过多次遍历待排序的元素，比较相邻元素的大小，并交换它们直到整个序列有序。冒泡排序的基本思想是将较大的元素逐渐“浮”到数组的右端，而较小的元素逐渐“沉”到数组的左端。其基本原理如下：

1. 从数组的第一个元素开始，比较相邻的两个元素。
2. 如果前一个元素大于后一个元素（升序排序），则交换它们的位置。
3. 步骤1和步骤2，直到遍历整个数组。
4. 上步骤，每次遍历都将最大的元素“冒泡”到数组的末尾。
5. 复以上步骤，但不包括已排序的最大元素，直到整个数组排序完成。

冒泡排序的java代码

package com.datastructure;

class ArrayBub {
    private long[] a;
    private int nElems;

    public ArrayBub(int max) { //constructor
        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, in;
        for (out = nElems - 1; out > 1; out--) {  //outer loop (backward)
            for (in = 0; in < out; in++) {        //inner loop(forward)
                if (a[in] > a[in + 1]) {          //out of order?
                    swap(in, in + 1);        //swap them
                }
            }
        }
    }

    private void swap(int one, int two) {
        long temp = a[one];
        a[one] = a[two];
        a[two] = temp;
    }
}

public class bubbleSort {
    public static void main(String[] args) {
        int maxSize = 100;
        ArrayBub arr;
        arr = new ArrayBub(maxSize);
        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);
        System.out.println("原始数组：");
        arr.display();
        System.out.println("排序后数组：");
        arr.bubbleSort();
        arr.display();
    }
}

冒泡排序的效率

由于冒泡排序的这两个操作都和2N2成正比，因此其总效率可以表示为(2)O(N2)。这意味着，对于包含N个元素的数列，冒泡排序需要大约2N2次操作来完成排序。这种算法的时间复杂度是二次的，意味着随着输入规模的增加，其运行时间会显著增加，因此在实际应用中，当处理大量数据时，冒泡排序并不是最高效的选择。