一个人至少拥有一个梦想,有一个理由去坚强

心若没有栖息的地方,到哪里都是在流浪

排序——冒泡排序

冒泡排序算法多次遍历数组,在每次遍历中连续比较相邻的元素,如果元素没有按照顺序排列,则互换它们的值。

冒泡排序需要遍历几次数组。在每次遍历中,比较连续相邻的元素。如果某一对元素是降序,则互换它们的值,否则,保持不变。由于较小的值像“气泡”一样逐渐浮向顶部,而较大的值逐渐沉向底部,所以称这种技术为冒泡排序或下沉排序。

第一次遍历后,最后一个元素为数组最大数。第二次遍历后,倒数第二个数为数组中第二大数。整个过程持续到所有元素都排好序。

(说明:下图中已经排好序的用斜体表示)

《排序——冒泡排序》

如上图所示,第一次遍历后,最大的值9放在数组末尾,第二次遍历后就不需要再考虑最后一个元素。因此,在第k次遍历后,不需要遍历最后k – 1个元素,因为它们已经是排好序了的。

下面是代码实现:

public class BubbleSort {
    public static void main(String[] args) {
        int[] list = {2, 3, 5, 4, 7, -1, 15, 20, 2};
        bubbleSort(list);
        for (int value : list) {
            System.out.print(value + " ");
        }
    }

    public static void bubbleSort(int[] list) {
        boolean needNextPass = true;
        for (int k = 1; k < list.length && needNextPass; k++) {

            needNextPass = false;
            for (int i = 0; i < list.length - k; i++) {
                needNextPass = false;
                if (list[i] > list[i + 1]) {
                    int temp = list[i];
                    list[i] = list[i + 1];
                    list[i + 1] = temp;

                    needNextPass = true; //仍然需要下一次遍历
                }
            }
        }
    }
}

运行结果:

《排序——冒泡排序》

在最佳情况下,冒泡排序算法只需要一次遍历就能确定数组已经排好序,不需要进行下一次排序。由于第一次排序的比较次数为n – 1,因此在最佳情况下,冒泡排序的时间复杂度为O(n).

在最差情况下,冒泡排序需要进行n – 1次遍历。第一次遍历需要n – 1次比较,第二次遍历需要n – 2次比较,以此类推,最后一次遍历需要1次比较。因此,比较的总数为:

(n – 1)+ (n – 2) + …. + 2 + 1

= (n – 1) * n / 2 = n^2/2 – n/2 = n / 2

= O(n^2)

在最差的情况下,冒泡排序时间为O(n^2)

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注