冒泡算法

一.摘要

什么是冒泡排序算法，如何使用冒泡排序算法？基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

二.封装

将一个数组的元素两两比较，将大的元素交换位置并逐渐“上浮”到右边

定义一个需要排序的数组：int num[]={4,6,2,5,8,9}

第一趟：找到数组{4,6,2,5,8,9}最大的元素并“上浮”到右边

指针位置为0，4和6比较，4小于6，不需要交换位置

无序数组,：{4,6,2,5,8,9}

指针位置为1，6和2比较，6大于2，交换位置

无序数组：{4,[2],[6],5,8,9}

指针位置为2：6和5比较，6大于5，交换位置

无序数组：{4,2,[5],[6],8,9}

指针位置为3，6和8比较，6小于8，不需要交换位置

无序数组：{4,2,5,6,8,9}

指针位置为4，8和9比较，8小于9，不需要交换位置

无序数组：{4,2,5,6,8,9}

第二趟：找到数组{4,2,5,6,8,9}最大的元素并“上浮”到右边

指针位置为0，4和2比较，4大于2，交换位置

无序数组：{[2],[4],5,6,8,9}

指针位置为1，4和5比较，4小于5，不需要交换位置

无序数组：{2,4,5,6,8,9}

指针位置为2，5和6比较，5小于6，不需要交换位置

无序数组：{2,4,5,6,8,9}

指针位置为3，6和8比较，6小于8，不需要交换位置

无序数组：{2,4,5,6,8,9}

指针位置为4，8和9比较，8小于9，不需要交换位置

无序数组：{2,4,5,6,8,9}

同理，程序依次执行

第三趟...

第四趟...

第五趟...

对于一个长度为N的数组，需要执行（N-1）趟，每一趟需要比较次数分别为：N-1,N-2,N-3...3,2,1

用C表示比较次数，用M表示移动次数

最坏的时间复杂度：一个逆序的数组

$C_{max}=\frac{[(n-1)+1](n-1)}2=\frac{n(n-1)}2=O(n^2)$

$M_{max}=\frac{3[(n-1)+1](n-1)}2=\frac{3n(n-1)}2=O(n^2)$

    int num[] = { 4, 6, 2, 5, 8, 9 };

    for (int i = 0; i < num.length-1; i++) {
        int tmp;// 临时变量
        for (int j = 0; j < num.length-1; j++) {
            if (num[j] > num[j + 1]) {
                tmp = num[j];
                num[j] = num[j + 1];
                num[j + 1] = tmp;
            }
        }
    }

    for (int i = 0; i < num.length; i++) {
        System.out.println("num[" + i + "]=" + num[i]);
    }

百度百科：冒泡排序

Java中的经典算法之冒泡排序(Bubble Sort)