排序算法01—冒泡排序

一、原理

    比较两个相邻的元素，将值大的元素交换至右端。依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。

第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；

第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；

依次类推，每一趟比较次数-1；

简单的冒泡排序

/**
 * 简单的冒泡排序
 */
public class BubbleRank1 {

    public static void main(String[] args) {

        int[] array = {81, 51, 88, 15, 59, 20, 1, 50, 66, 77, 4};
        int n = array.length;

        // n-1 次排序过程
        for (int i = 0; i < n - 1; i++) {
            for (int j = 1; j < n - i; j++) {
                // 前面的数字大于后面的数字就交换
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        System.out.println("排序完：" + Arrays.toString(array));
    }
}

优化的冒泡排序

    如果对于一个本身有序的序列，或者序列后面一大部分都是有序的序列，上面的算法就会浪费很多的时间开销。可以考虑设置一个标志 flag，如果这一趟发生了交换则为 true，否则为 false。明显如果有一趟没有发生交换，说明排序已经完成。

/**
 * 优化冒泡排序
 */
public class BubbleRank2 {
    public static void main(String[] args) {
        int[] array = {81, 51, 88, 15, 59, 20, 1, 50, 66, 77, 4};
        int n = array.length;
        boolean flag = true;

        while (flag) {
            //每次开始排序前，都设置flag为未排序过
            flag = false;
            for (int i = 1; i < n; i++) {
                // 前面的数字大于后面的数字就交换
                if (array[i - 1] > array[i]) {
                    int temp = array[i - 1];
                    array[i - 1] = array[i];
                    array[i] = temp;
                    //表示交换过数据
                    flag = true;
                }
            }
            //减小一次排序的尾边界
            n--;
        }

        System.out.println("排序完：" + Arrays.toString(array));
    }
}

进一步优化的冒泡排序

    比如，现在有一个包含1000个数的数组，仅前面100个无序，后面900个都已排好序且都大于前面100个数字，那么在第一趟遍历后，最后发生交换的位置必定小于100，且这个位置之后的数据必定已经有序了，也就是这个位置以后的数据不需要再排序了，于是记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。如果是对于上面的冒泡排序算法2来说，虽然也只排序100次，但是前面的100次排序每次都要对后面的900个数据进行比较，而对于现在的排序算法3，只需要有一次比较后面的900个数据，之后就会设置尾边界，保证后面的900个数据不再被排序。

public class BubbleRank3 {

    public static void main(String[] args) {
        int[] array = {81, 51, 88, 15, 59, 20, 1, 50, 66, 77, 4};
        //flag用来记录最后交换的位置，也就是排序的尾边界
        int flag = array.length;
        //k用来记录遍历的尾边界
        int k;

        while (flag > 0) {
            k = flag;
            flag = 0;
            for (int i = 1; i < k; i++) {
                // 前面的数字大于后面的数字就交换
                if (array[i - 1] > array[i]) {
                    int temp = array[i - 1];
                    array[i - 1] = array[i];
                    array[i] = temp;

                    //表示交换过数据
                    //记录最新的尾边界
                    flag = i;
                }
            }
        }
        System.out.println("排序完：" + Arrays.toString(array));
    }
}